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 addedge = require( "addedge" )
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 )

addedge( g, "z", "a" ) -- adding circle a->x->z->a
order, err = tsort2d( g )
t( order, nil )
t( err, "Graph contains a cycle." )

t()

See Also