Parameter Persistent.1-G
A persistent graph is a graph.
include Sig.G
module V : Sig.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 : 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.
val empty : t
The empty graph.
val add_vertex : t -> vertex -> t
add_vertex g v
adds the vertexv
to the graphg
. Just returng
ifv
is already ing
.
val remove_vertex : t -> vertex -> t
remove g v
removes the vertexv
from the graphg
(and all the edges going fromv
ing
). Just returng
ifv
is not ing
.<b>Time complexity for ocamlgraph implementations:</b> O(|V|*ln(|V|)) for unlabeled graphs and O(|V|*max(ln(|V|),D)) for labeled graphs. D is the maximal degree of the graph.
val add_edge : t -> vertex -> vertex -> t
add_edge g v1 v2
adds an edge from the vertexv1
to the vertexv2
in the graphg
. Add alsov1
(resp.v2
) ing
ifv1
(resp.v2
) is not ing
. Just returng
if this edge is already ing
.
val add_edge_e : t -> edge -> t
add_edge_e g e
adds the edgee
in the graphg
. Add alsoE.src e
(resp.E.dst e
) ing
ifE.src e
(resp.E.dst e
) is not ing
. Just returng
ife
is already ing
.