isolatednodes

function isolatednodes( graph ) --> nodes

Description

Returns all nodes of graph that have no incoming and no outcoming edges.

Parameters

graph

The graph where the function looks for isolated nodes. The graph itself will not be modified.

Return Values

nodes

The isolated nodes of graph.

Code

--ZFUNC-isolatednodes-v1
local function isolatednodes( graph ) --> nodes
   local connected = {}
   for node, edges in pairs( graph ) do
      for other in pairs( edges ) do
         connected[ node ] = true
         connected[ other ] = true
      end
   end
   local nodes = {}
   for node in pairs( graph ) do
      if not connected[ node ] then
         table.insert( nodes, node )
      end
   end
   return nodes
end

return isolatednodes

Examples

local t = require( "tapered" )
local isolatednodes = require( "isolatednodes" )
-- util functions
local addedge = require( "addedge" )
local buildgraph = require( "buildgraph" )
local like = require( "like" )

local g = buildgraph( { "a", "b", "c", "x" }, {} )
t.ok( like( isolatednodes( g ), { "a", "b", "c", "x" } ) )

addedge( g, "a", "x" )
-- a --> x
-- [ b ] [ c ]
t.ok( like( isolatednodes( g ), { "b", "c" } ) )

addedge( g, "b", "c" )
-- a --> x
-- b --> c
t.ok( like( isolatednodes( g ), {} ) )

t.done()

See Also