module Traversal (A : A) : sig .. end
In a graph traversal, each node is numbered (first node visited: 0,
second node: 1, ...), has eventually a parent (the ndoe from which it
was discovered, the starting node(s) of the traversal are their own
parent, the parent information thus induces a forest), and a distance
information (the length of parent chain up to a source node).
type
|
nb : int; |
|
dist : int; |
|
parent : int; |
}
type
}
val non_vertex : int
val visit_nb : t -> int -> int
val visited : t -> int -> bool
Has vertex been visited.
val parent : t -> int -> int
val dist : t -> int -> int
Distance from root.
val nb_visited : t -> int
val nb_nodes : t -> int
Total number of nodes (including non-visited nodes).
exception Found of int
val last_visited : t -> int
val order : t -> int Traversal.A.t
Visited nodes in traversal order.
val iter_path : (int -> 'a) -> t -> int -> int -> unit
Iterate on u, parent(u), ..., v if v is ancestor of u, and
up to the root of the tree containing u otherwise.
val fold_path : (int -> 'a -> 'a) -> t -> int -> int -> 'a -> 'a
val path_rev : t -> int -> int -> int list
val path : t -> int -> int -> int list
val make : int -> t
val set : t -> int -> int -> int -> int -> unit