tsort2d

`function tsort2d( graph ) --> groups, err`

Description

Returns an two dimensional array table where at least one entry from [n+1] depent on the entries in [n]. Isolated nodes and sink nodes are stored at the end. It works only for directed acyclic graphs. The implementation is using a Kahn-like implementation.

Parameters

graph

The graph that should be ordered.

Return Values

groups

An two dimensional array table where at least one entry from [n+1] depent on the entries in [n].

err

nil or a message if the graph contains cycles.

Code

```--ZFUNC-tsort2d-v1
local function tsort2d( graph ) --> groups, err
--ZFUNC-transposegraph-v1
local function transposegraph( graph ) --> transpose
local transpose = {}
for node, edges in pairs( graph ) do
transpose[ node ] = transpose[ node ] or {}
for other in pairs( edges ) do
transpose[ other ] = transpose[ other ] or {}
transpose[ other ][ node ] = true
end
end
return transpose
end
--ZFUNC-deepcopy-v1
local function deepcopy( tab )
if type( tab ) ~= "table" then return tab end
local mt = getmetatable( tab )
local copy = {}
for k, v in pairs( tab ) do
if type( v ) == "table" then v = deepcopy( v ) end
copy[ k ] = v
end
setmetatable( copy, mt )
return copy
end
--ZFUNC-isfilled-v1
local function isfilled( tab )
for _, v in pairs( tab ) do return true end
return false
end
local groups = {}
local copy = deepcopy( graph )
local transpose = transposegraph( graph )
while isfilled( copy ) do
local group = {}
for node, edges in pairs( copy ) do
if not isfilled( edges ) then
table.insert( group, node )
end
end
for _, node in pairs( group ) do
copy[ node ] = nil
for parent in pairs( transpose[ node ] ) do
copy[ parent ][ node ] = nil
end
end
if not isfilled( group ) then
return nil, "Graph contains a cycle."
end
table.insert( groups, 1, group )
end
return groups
end

return tsort2d```

Examples

```local t = require( "taptest" )
local buildgraph = require( "buildgraph" )
local flatten = require( "flatten" )
local same = require( "same" )
local tsort2d = require( "tsort2d" )

local g = buildgraph( { "e" }, { { "a", "b" }, { "c", "d" } } )
-- a --> b
-- c --> d
-- [ e ]
local groups, err = tsort2d( g )
t( #groups, 2 )
table.sort( groups[ 1 ] )
table.sort( groups[ 2 ] )
t( same( flatten( groups ), { "a", "c", "b", "d", "e" } ), true )
t( err, nil )

local edges = {
{ "a", "x" },
{ "x", "c" },
{ "x", "z" },
{ "c", "z" }
}
g = buildgraph( {}, edges )
-- a --> x --> c
--       \      \
--        -----> --> z
groups, err = tsort2d( g )
t( #groups, 4 )
t( same( flatten( groups ), { "a", "x", "c", "z" } ), true )
t( err, nil )