package ocamlgraph
Common signature for all graphs.
Graph structure
Vertices have type V.t
and are labeled with type V.label
(note that an implementation may identify the vertex with its label)
type vertex = V.t
Edges have type E.t
and are labeled with type E.label
. src
(resp. dst
) returns the origin (resp. the destination) of a given edge.
type edge = E.t
Size functions
val is_empty : t -> bool
val nb_vertex : t -> int
val nb_edges : t -> int
Degree of a vertex
Membership functions
find_edge g v1 v2
returns the edge from v1
to v2
if it exists. Unspecified behaviour if g
has several edges from v1
to v2
.
find_all_edges g v1 v2
returns all the edges from v1
to v2
.
Successors and predecessors
You should better use iterators on successors/predecessors (see Section "Vertex iterators").
Labeled edges going from/to a vertex
Graph iterators
Iter on all edges of a graph. Edge label is ignored.
Fold 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.
iter/fold on all successors/predecessors of a vertex.
iter/fold on all edges going from/to a vertex.