This functor provides functions which allow iterating over a graph in
topological order. Cycles in graphs are allowed. Specification is the
x is visited before vertex
then either there is a path from
or there is no path from
In the particular case of a DAG, this simplifies to:
if there is an edge from
x is visited before
Functor providing topological iterators over a graph.
fold action g seed allows iterating over the graph
in topological order.
action node accu is called repeatedly,
node is the node being visited, and
accu is the result of
action's previous invocation, if any, and
g contains cycles, the order is unspecified inside the cycles and
every node in the cycles will be presented exactly once.
Not tail-recursive. Complexity: O(V+E)
Provide the same features than Make, except that the resulting
topological ordering is stable according to vertices comparison: if two
v2 are topologically equal,
v1 is presented first to
the iterator if and only if
G.V.compare v1 v2 <= 0. In particular, the
resulting order is not dependent on the provided hash function. This
property is not guaranteed by the functor Make. The counterpart is a less
efficient implementation: worst time complexity is O(E*V*ln(V)) instead of
O(E*V) (with E = number of edges and V = number of vertices.