15.4.773  src/lib/graph/graph-topological-sort.pkg

## graph-topological-sort.pkg
#
# This module computes a topological sort of a graph
#
# -- Allen Leung

# Compiled by:
#     src/lib/graph/graphs.lib

stipulate
    package odg =  oop_digraph;                                         # oop_digraph           is from   src/lib/graph/oop-digraph.pkg
herein

    package   graph_topological_sort
    : (weak)  Graph_Topological_Sort                                    # Graph_Topological_Sort        is from   src/lib/graph/graph-topological-sort.api
    {
        # Topological sort:
        #
        fun topological_sort (odg::DIGRAPH graph) roots
            = 
            dfs''(roots,[])
            where 
                visited = rw_vector_of_one_byte_unts::make_rw_vector (graph.capacity (), 0u0);

                next    = graph.next;

                fun dfs (n, list)
                    =
                    if  (rw_vector_of_one_byte_unts::get (visited, n) != 0u0)
                         list;
                    else
                         rw_vector_of_one_byte_unts::set (visited, n, 0u1);
                         dfs'(n, next n, list);
                    fi

                also
                fun dfs'(x,[],      list) =>   x ! list;
                    dfs'(x, n ! ns, list) =>   dfs'(x, ns, dfs (n, list));
                end 

                also
                fun dfs''([], list)     => list;
                    dfs''(n ! ns, list) => dfs''(ns, dfs (n, list));
                end;
            end;
    };
end;