Up
# module Imperative

: sig

Imperative Graph Implementations.

#

module type S = sig

Signature of imperative graphs.

**Edges may be labeled or not**:

- Unlabeled: there is no label on edges
- Labeled: you have to provide a label implementation as a functor parameter.

**Vertices may be concrete or abstract**:

- Concrete: type of vertex labels and type of vertices are identified.
- Abstract: type of vertices is abstract (in particular it is not equal to type of vertex labels

**How to choose between concrete and abstract vertices for my graph
implementation**?

Usually, if you fall into one of the following cases, use abstract vertices:

- you cannot provide efficient comparison/hash functions for vertices; or
- you wish to get two different vertices with the same label.

In other cases, it is certainly easier to use concrete vertices.

end

#
## Bidirectional graphs

module Digraph : sig

Imperative Directed Graphs.

include S

Bidirectional graphs use more memory space (at worse the double) that standard concrete directional graphs. But accessing predecessors is in O(1) amortized instead of O(max(|V|,|E|)) and removing a vertex is in O(D*ln(D)) instead of O(|V|*ln(D)). D is the maximal degree of the graph.

end

#

module Matrix : sig

Imperative graphs implemented as adjacency matrices.

#

module type S = sig

Vertices are integers in `0..n-1`

.
A vertex label is the vertex itself.
Edges are unlabeled.

#

val make : int -> t

Creation. 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.

end

end

end