Up
# module Topological

: sig

Topological order.

This functor provides functions which allow iterating over a graph in
topological order. Cycles in graphs are allowed. Specification is the
following:
if vertex `x`

is visited before vertex `y`

then either there is a path from `x`

to `y`

,
or there is no path from `y`

to `x`

.
In the particular case of a DAG, this simplifies to:
if there is an edge from `x`

to `y`

, then `x`

is visited before `y`

.

#

Functor providing topological iterators over a graph.

#

val fold : (G.V.t -> 'a -> 'a) -> G.t -> 'a -> 'a

`fold action g seed`

allows iterating over the graph `g`

in topological order. `action node accu`

is called repeatedly,
where `node`

is the node being visited, and `accu`

is the result of
the `action`

's previous invocation, if any, and `seed`

otherwise.
If `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)

end

#

Provide the same features than Make, except that the resulting
topological ordering is stable according to vertices comparison: if two
vertices `v1`

and `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.

end

end