# 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
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
table.insert( stack, next_node )
end
end
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 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 )

order, err = tsort( g )
t( order, nil )
t( err, "Graph contains a cycle." )

g = buildgraph( { "a", "b", "c" }, {} )