Module Graph.Traverse

Graph traversal.

Dfs and Bfs

In the modules below, the most meaningful functions are the iter/fold_component functions, where the starting point of the traversal is user-provided.

Functions iter/fold to traverse the whole graph are also provided, for convenience, and they proceed as follows: they run the user-provided iter/fold_vertex functions (from input module G) and, for each vertex not yet visited, start a new traversal from this vertex. In particular, each traversal is not necessarily started from a vertex without predecessors. Said otherwise, it is up to you to come up with an iter_vertex function that will identify suitable roots, e.g. vertices with no predecessors, if this is really what you want.

module type G = sig ... end

Minimal graph signature for Dfs and Bfs. Sub-signature of Sig.G.

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

Depth-first search

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

Breadth-first search

Traversal with marking

Provide a more efficient version of depth-first algorithm when graph vertices are marked.

module type GM = sig ... end

Minimal graph signature for graph traversal with marking. Sub-signature of Sig.IM.

module Mark (G : GM) : sig ... end

Graph traversal with marking. Only applies to imperative graphs with marks.