sinknodes

function sinknodes( graph ) --> nodes

Description

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

Parameters

graph

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

Return Values

nodes

The sink nodes of graph.

Code

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

   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, edges in pairs( graph ) do
      if connected[ node ] and isempty( edges ) then
         table.insert( nodes, node )
      end
   end
   return nodes
end

return sinknodes

Examples

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

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

local g = buildgraph( nodes, {} )
t( like( sinknodes( g ), {} ), true )

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

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

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

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

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

t()

See Also