module Concrete: functor (
V
:
Sig.COMPARABLE
) ->
Sig.I
with type V.t = V.t and type V.label = V.t and type E.t = V.t * V.t
and type E.label = unit
Imperative Unlabeled Graphs.
include Sig.G
An imperative graph is a graph.
val create : ?size:int -> unit -> t
create ()
returns an empty graph. Optionally, a size can be
given, which should be on the order of the expected number of
vertices that will be in the graph (for hash tables-based
implementations). The graph grows as needed, so size
is
just an initial guess.
val clear : t -> unit
Remove all vertices and edges from the given graph.
Since ocamlgraph 1.4
val copy : t -> t
copy g
returns a copy of g
. Vertices and edges (and eventually
marks, see module Mark
) are duplicated.
val add_vertex : t -> vertex -> unit
add_vertex g v
adds the vertex v
to the graph g
.
Do nothing if v
is already in g
.
val remove_vertex : t -> vertex -> unit
remove g v
removes the vertex
v
from the graph
g
(and all the edges going from
v
in
g
).
Do nothing if
v
is not in
g
.
Time complexity for ocamlgraph implementations:
O(|V|*ln(D)) for unlabeled graphs and O(|V|*D) for
labeled graphs. D is the maximal degree of the graph.
val add_edge : t -> vertex -> vertex -> unit
add_edge g v1 v2
adds an edge from the vertex v1
to the vertex v2
in the graph g
.
Add also v1
(resp. v2
) in g
if v1
(resp. v2
) is not in g
.
Do nothing if this edge is already in g
.
val add_edge_e : t -> edge -> unit
add_edge_e g e
adds the edge e
in the graph g
.
Add also E.src e
(resp. E.dst e
) in g
if E.src e
(resp. E.dst
e
) is not in g
.
Do nothing if e
is already in g
.
val remove_edge : t -> vertex -> vertex -> unit
remove_edge g v1 v2
removes the edge going from v1
to v2
from the
graph g
. If the graph is labelled, all the edges going from v1
to
v2
are removed from g
.
Do nothing if this edge is not in g
.
Raises Invalid_argument
if v1
or v2
are not in g
.
val remove_edge_e : t -> edge -> unit
remove_edge_e g e
removes the edge e
from the graph g
.
Do nothing if e
is not in g
.
Raises Invalid_argument
if E.src e
or E.dst e
are not in g
.