buildgraph

function buildgraph( nodes, edges [, undirected] ) --> graph

Description

Creates a graph data structure with the defined nodes and edges. If the nodes from the edges are not existing creates the function the nodes in the graph. The edges are by default direct, with the optional undirected parameter is it possible to define it as undirected edge.

Parameters

nodes

The nodes for the graph.

edges

The edges that should be created.

undirected

Optional value that is by default false. Can be true to create undirected edges.

Return Values

graph

The created graph.

Code

--ZFUNC-buildgraph-v1
local function buildgraph( nodes, edges, undirected ) --> graph
   local graph = {}

   for _, node in ipairs( nodes ) do
      graph[ node ] = {}
   end

   for i, edge in ipairs( edges ) do
      local x = edge[ 1 ]
      graph[ x ] = graph[ x ] or {}
      local y = edge[ 2 ]
      graph[ y ] = graph[ y ] or {}
      graph[ x ][ y ] = true
      if undirected then
         graph[ y ][ x ] = true
      end
   end

   return graph
end

return buildgraph

Examples

local t = require( "taptest" )
local buildgraph = require( "buildgraph" )
local keys = require( "keys" )
local like = require( "like" )

local nodes = { "a", "b", "c", "d" }

local edges = {
   { "a", "b" },
   { "b", "c" },
   { "b", "d" },
   { "c", "e" }
}

local g = buildgraph( nodes, edges )
t( like( keys( g ), { "a", "b", "c", "d", "e" } ), true )
t( like( keys( g[ "a" ] ), { "b" } ), true )
t( like( keys( g[ "b" ] ), { "c", "d" } ), true )
t( like( keys( g[ "c" ] ), { "e" } ), true )
t( like( keys( g[ "d" ] ), {} ), true )
t( like( keys( g[ "e" ] ), {} ), true )

g = buildgraph( nodes, edges, false )
t( like( keys( g ), { "a", "b", "c", "d", "e" } ), true )
t( like( keys( g[ "a" ] ), { "b" } ), true )
t( like( keys( g[ "b" ] ), { "c", "d" } ), true )
t( like( keys( g[ "c" ] ), { "e" } ), true )
t( like( keys( g[ "d" ] ), {} ), true )
t( like( keys( g[ "e" ] ), {} ), true )

g = buildgraph( nodes, edges, true )
t( like( keys( g ), { "a", "b", "c", "d", "e" } ), true )
t( like( keys( g[ "a" ] ), { "b" } ), true )
t( like( keys( g[ "b" ] ), { "a", "c", "d" } ), true )
t( like( keys( g[ "c" ] ), { "b", "e" } ), true )
t( like( keys( g[ "d" ] ), { "b" } ), true )
t( like( keys( g[ "e" ] ), { "c" } ), true )

t()