leafnodes

function leafnodes( graph ) --> nodes

Description

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

Parameters

graph

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

Return Values

nodes

The leaf nodes of graph.

Code

--ZFUNC-leafnodes-v1
local function leafnodes( graph ) --> nodes
   --ZFUNC-isempty-v1
   local function isempty( tab )
      for _, v in pairs( tab ) do return false end
      return true
   end

   local parents = {}
   for node, edges in pairs( graph ) do
      for other in pairs( edges ) do
         local n = parents[ other ] or 0
         parents[ other ] = n+1
      end
   end
   local nodes = {}
   for node, edges in pairs( graph ) do
      if parents[ node ] == 1 and isempty( edges ) then
         table.insert( nodes, node )
      end
   end
   return nodes
end

return leafnodes

Examples

local t = require( "taptest" )
local addedge = require( "addedge" )
local buildgraph = require( "buildgraph" )
local leafnodes = require( "leafnodes" )
local like = require( "like" )

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

g = addedge( g, "a", "b" )
-- a --> b
-- [ c ] [ d ]
t( like( leafnodes( g ), { "b" } ), true )

g = addedge( g, "b", "c" )
-- a --> b --> c
-- [ d ]
t( like( leafnodes( g ), { "c" } ), true )

g = addedge( g, "b", "d" )
-- a --> b --> c
--        \
--         --> d
t( like( leafnodes( g ), { "c", "d" } ), true )

g = addedge( g, "d", "c" )
-- a --> b ---------> c
--        \         /
--         --> d -->
t( like( leafnodes( g ), {} ), true )

t()

See Also