tsort

function tsort( graph ) --> order, err

Description

Returns a linear ordering of the nodes in graph. It works only for directed acyclic graphs. The implemention of the topological sorting is using a depth-first search implementations.

Parameters

graph

The graph that should be ordered.

Return Values

order

The linear ordering of graph as array table or nil if the graph contains cycles.

err

nil or a message if the graph contains cycles.

Code

--ZFUNC-tsort-v1
local function tsort( graph ) --> order, err
   local order = {}

   local know = {}
   for node in pairs( graph ) do
      if not know[ node ] then
         local seen = {}
         local stack = {}
         table.insert( stack, node )
         while #stack > 0 do
            local current_node = stack[ #stack ]
            if know[ current_node ] then
               table.remove( stack )
            else
               seen[ current_node ] = true
               local added = false
               for next_node in pairs( graph[ current_node ] ) do
                  if not know[ next_node ] then
                     if seen[ next_node ] then
                        return nil, "Graph contains a cycle."
                     end
                     added = true
                     table.insert( stack, next_node )
                  end
               end
               if not added then
                  table.remove( stack )
                  know[ current_node ] = true
                  table.insert( order, 1, current_node )
               end
            end
         end
      end
   end

   return order
end

return tsort

Examples

local t = require( "taptest" )
local addedge = require( "addedge" )
local buildgraph = require( "buildgraph" )
local occurasc = require( "occurasc" )
local tsort = require( "tsort" )

local edges = {
   { "a", "x" },
   { "x", "c" },
   { "x", "z" },
   { "c", "z" }
}
local g = buildgraph( {}, edges )
-- a --> x --> c
--       \      \
--        -----> --> z
local order, err = tsort( g )

t( occurasc( order, "a", "x", "c", "z" ), true )
t( err, nil )

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

g = buildgraph( { "a", "b", "c" }, {} )
addedge( g, "a", "b" )
addedge( g, "a", "c" )
addedge( g, "b", "c" )
-- a ----------> c
--  \         /
--   --> b -->
order, err = tsort( g )
t( occurasc( order, "a", "b", "c" ), true )
t( err, nil )

t()

Inspired by

See Also