Module Graph__Traverse.Dfs
Depth-first search
Parameters
Signature
Classical big-step iterators
val iter : ?pre:(G.V.t -> unit) -> ?post:(G.V.t -> unit) -> G.t -> unit
iter pre post g
visits all nodes ofg
in depth-first search, applyingpre
to each visited node before its successors, andpost
after them. Each node is visited exactly once. Not tail-recursive.
Classical folds
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.
Cycle detection
val has_cycle : G.t -> bool
has_cycle g
checks for a cycle ing
. Linear in time and space.