Up

module Traverse

: sig

Graph traversal.

Dfs and Bfs

#
module type G = sig

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

#
val is_directed : bool
#
type t
#
module V : Sig.COMPARABLE
#
val iter_vertex : (V.t -> unit) -> t -> unit
#
val fold_vertex : (V.t -> 'a -> 'a) -> t -> 'a -> 'a
#
val iter_succ : (V.t -> unit) -> t -> V.t -> unit
#
val fold_succ : (V.t -> 'a -> 'a) -> t -> V.t -> 'a -> 'a
end
#
module Dfs : functor (G : G) -> sig

Depth-first search

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 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) -> 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) -> G.t -> unit

applies only a postfix function. Not tail-recursive.

Same thing, but for a single connected component (only prefix_component is tail-recursive)

#
val iter_component : ?pre:(G.V.t -> unit) -> ?post:(G.V.t -> unit) -> G.t -> G.V.t -> unit
#
val prefix_component : (G.V.t -> unit) -> G.t -> G.V.t -> unit
#
val postfix_component : (G.V.t -> unit) -> 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 : G.t -> iterator
#
val step : iterator -> iterator
#
val get : iterator -> G.V.t

Cycle detection

#
val has_cycle : G.t -> bool

has_cycle g checks for a cycle in g. Linear in time and space.

end
#
module Bfs : functor (G : G) -> sig

Breadth-first search

Classical big-step iterators

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

Step-by-step iterator

See module Dfs

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

Traversal with marking

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

#
module type GM = sig

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

#
type t
#
module V : sig
#
type t
end
#
val iter_vertex : (V.t -> unit) -> t -> unit
#
val iter_succ : (V.t -> unit) -> t -> V.t -> unit
#
module Mark : sig
#
val clear : t -> unit
#
val get : V.t -> int
#
val set : V.t -> int -> unit
end
end
#
module Mark : functor (G : GM) -> sig

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

#
val dfs : G.t -> unit

dfs g traverses g in depth-first search, marking all nodes.

#
val has_cycle : G.t -> bool

has_cycle g checks for a cycle in g. Modifies the marks. Linear time, constant space.

end
end