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( "taptest" )
local addedge = require( "addedge" )
local buildgraph = require( "buildgraph" )
local isolatednodes = require( "isolatednodes" )
local like = require( "like" )

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

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

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

t()

See Also