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.

#
module type G = sig

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

#
type t
#
module V : Sig.COMPARABLE
#
val iter_vertex : (V.t -> unit) -> t -> unit
#
val iter_succ : (V.t -> unit) -> t -> V.t -> unit
end
#
module Make : functor (G : G) -> sig

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)

#
val iter : (G.V.t -> unit) -> G.t -> unit

iter action calls action node repeatedly. Nodes are (again) presented to action in topological order. The order is the same as for fold.

end
#
module Make_stable : functor (G : sig
include G
#
val in_degree : t -> V.t -> int
end
) -> sig

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.

#
val fold : (G.V.t -> 'a -> 'a) -> G.t -> 'a -> 'a
#
val iter : (G.V.t -> unit) -> G.t -> unit
end
end