module Dfs: functor (
G
:
G
) ->
sig
.. end
Depth-first search
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.
Not tail-recursive.
val prefix : (G.V.t -> unit) -> Traverse.G.t -> unit
applies only a prefix function; note that this function is more
efficient than iter
and is tail-recursive.
val postfix : (G.V.t -> unit) -> Traverse.G.t -> unit
applies only a postfix function. Not tail-recursive.
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
type
iterator
(h, st, g) where h is the set of marked vertices and st the stack
invariant: the first element of st is not in h i.e. to be visited
val start : Traverse.G.t -> iterator
val step : iterator -> iterator
val get : iterator -> G.V.t
val has_cycle : Traverse.G.t -> bool
has_cycle g
checks for a cycle in g
. Linear in time and space.