Module Make.Tree
Graph structure
module V : Graph.Sig.VERTEX with type label = vertex
Vertices have type
V.t
and are labeled with typeV.label
(note that an implementation may identify the vertex with its label)
type vertex
= V.t
module E : Graph.Sig.EDGE with type vertex = vertex
Edges have type
E.t
and are labeled with typeE.label
.src
(resp.dst
) returns the origin (resp. the destination) of a given edge.
type edge
= E.t
Size functions
Membership functions
val mem_vertex : t -> vertex -> bool
val mem_edge : t -> vertex -> vertex -> bool
val mem_edge_e : t -> edge -> bool
val find_edge : t -> vertex -> vertex -> edge
find_edge g v1 v2
returns the edge fromv1
tov2
if it exists. Unspecified behaviour ifg
has several edges fromv1
tov2
.- raises Not_found
if no such edge exists.
Successors and predecessors
You should better use iterators on successors/predecessors (see Section "Vertex iterators").
val succ : t -> vertex -> vertex list
succ g v
returns the successors ofv
ing
.- raises Invalid_argument
if
v
is not ing
.
val pred : t -> vertex -> vertex list
pred g v
returns the predecessors ofv
ing
.- raises Invalid_argument
if
v
is not ing
.
Graph iterators
val iter_edges : (vertex -> vertex -> unit) -> t -> unit
Iter on all edges of a graph. Edge label is ignored.
Vertex iterators
Each iterator iterator f v g
iters f
to the successors/predecessors of v
in the graph g
and raises Invalid_argument
if v
is not in g
. It is the same for functions fold_*
which use an additional accumulator.
<b>Time complexity for ocamlgraph implementations:</b> operations on successors are in O(1) amortized for imperative graphs and in O(ln(|V|)) for persistent graphs while operations on predecessors are in O(max(|V|,|E|)) for imperative graphs and in O(max(|V|,|E|)*ln|V|) for persistent graphs.