Functor Traverse.Dfs


module Dfs: 
functor (G : G) -> sig .. end
Depth-first search
Parameters:
G : G


Classical big-step iterators


val iter : ?pre:(G.V.t -> unit) -> ?post:(G.V.t -> unit) -> Traverse.G.t -> unit
iter pre post g visits all nodes of g in depth-first search, applying pre to each visited node before its successors, and post after them. Each node is visited exactly once.
val prefix : (G.V.t -> unit) -> Traverse.G.t -> unit
applies only a prefix function; note that this function is more efficient than iter
val postfix : (G.V.t -> unit) -> Traverse.G.t -> unit
applies only a postfix function

Same thing, but for a single connected component
val iter_component : ?pre:(G.V.t -> unit) ->
?post:(G.V.t -> unit) -> Traverse.G.t -> G.V.t -> unit
val prefix_component : (G.V.t -> unit) -> Traverse.G.t -> G.V.t -> unit
val postfix_component : (G.V.t -> unit) -> Traverse.G.t -> G.V.t -> unit

Step-by-step iterator

This is a variant of the iterators above where you can move on step by step. The abstract type iterator represents the current state of the iteration. The step function returns the next state. In each state, function get returns the currently visited vertex. On the final state both get and step raises exception Exit.

Note: the iterator type is persistent (i.e. is not modified by the step function) and thus can be used in backtracking algorithms.

type iterator 
val start : Traverse.G.t -> iterator
val step : iterator -> iterator
val get : iterator -> G.V.t

Cycle detection


val has_cycle : Traverse.G.t -> bool
has_cycle g checks for a cycle in g. Linear in time and space.