Module Graph.Topological

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.

module type G = sig ... end

Minimal graph signature to provide. Sub-signature of Sig.G.

module Make (G : G) : sig ... end

Functor providing topological iterators over a graph.

module Make_stable (G : sig ... end) : sig ... 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.