## Topological Sort in Erlang

From: "andrew cooke" <andrew@...>

Date: Thu, 19 Apr 2007 01:47:25 -0400 (CLT)

This uses the monad library described at
http://www.acooke.org/cute/MonadsinEr0.html

Some variables/functions:
- gr_get_out returns a list of edges for the named node in the graph
- repeat_app is repeat using lists:append for joining
- drop pulls the final result out of the monad
- the initial function bootstraps with an initial set of edges

Personally, I am surprised how clean this is.  When I wrote the monad code
I hadn't even considered tree-like program flow.  Note that Graph is
actually constant throughout.

Andrew

top_sort(Name, Graph) ->
drop([], [],
repeat_app(
fun top_sort/1,
({gr_get_out(Name, Graph), gb_sets:new(), Graph}))).

top_sort({[], _, _}) -> fail;
top_sort({[Head|Tail], Visited, Graph}) ->
case gb_sets:is_element(Head, Visited) of
% already visited - do nothing
true -> {empty, {Tail, Visited, Graph}};
% visit all children then add this node to the list
_ -> Visited2 = gb_sets:add_element(Head, Visited),
case repeat_app(fun top_sort/1,
{gr_get_out(Head, Graph), Visited2, Graph}) of
% this shouldn't happen
fail -> fail;
% no children, so we are at the end of a chain
{empty, {_, Visited3, Graph2}} ->
{[Head], {Tail, Visited3, Graph2}};
% append this node to the sorted children and continue
{Sorted, {_, Visited3, Graph2}} ->
{[Head|Sorted], {Tail, Visited3, Graph2}}
end
end.