Imperative Undirected Graphs implemented with adjacency matrices.
Vertices are integers in 0..n-1. A vertex label is the vertex itself. Edges are unlabeled.
include Sig.I
with type V.t = int
and type V.label = int
and type E.t = int * intAn imperative graph is a graph.
include Sig.G
with type V.t = int
with type V.label = int
with type E.t = int * intmodule V : Sig.VERTEX with type t = int with type label = intVertices 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.tEdges 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.tval is_empty : t -> boolval nb_vertex : t -> intval nb_edges : t -> intDegree of a vertex
out_degree g v returns the out-degree of v in g.
Invalid_argument if v is not in g.
in_degree g v returns the in-degree of v in g.
Invalid_argument if v is not in g.
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.
Not_found if no such edge exists.
find_all_edges g v1 v2 returns all the edges from v1 to v2.
You should better use iterators on successors/predecessors (see Section "Vertex iterators").
succ g v returns the successors of v in g.
Invalid_argument if v is not in g.
pred g v returns the predecessors of v in g.
Invalid_argument if v is not in g.
Labeled edges going from/to a vertex
succ_e g v returns the edges going from v in g.
Invalid_argument if v is not in g.
pred_e g v returns the edges going to v in g.
Invalid_argument if v is not in g.
Iter on all edges of a graph. Edge label is ignored.
Fold on all edges of a graph. Edge label is ignored.
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.
val create : ?size:int -> unit -> tcreate () 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 -> unitRemove all vertices and edges from the given graph.
copy g returns a copy of g. Vertices and edges (and eventually marks, see module Mark) are duplicated.
add_vertex g v adds the vertex v to the graph g. Do nothing if v is already in g.
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.
<b>Time complexity for ocamlgraph implementations:</b> O(|V|*ln(D)) for unlabeled graphs and O(|V|*D) for labeled graphs. D is the maximal degree of the graph.
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.
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.
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.
Invalid_argument if v1 or v2 are not in g.
val make : int -> tCreation. graphs are not resizeable: size is given at creation time. Thus make must be used instead of create.
Note: add_vertex and remove_vertex have no effect. clear only removes edges, not vertices.