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.