C[omp]ute

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.