Module MultiGraph
module MultiGraph:Labeled Directed Multi-Graphs.sig
..end
This module provides both imperative and persistent implementations for
labeled directed multi-graphs (labeled directed graphs with multiple labeled
edges). The interfaces are inspired from the Sig
module of the Ocamlgraph
library.
This module is based on the following formal definition for labeled directed multi-graphs. Given a set L of vertex labels and a set K of edge labels, a labeled directed multi-graph (called multi-graph for short) is any 6-tuple G = (V, E, l, k, s, t) where:
- V is a finite set of vertices,
- E is a finite set of edges,
- l is a labeling function from V to L,
- k is a labeling function from E to K,
- s and t are functions from E to V mapping each edge to a source vertex s(e) and a target vertex t(e).
Observe that there may be multiple edges with the same end nodes and the same label in a labeled directed multi-graph. This contrasts with (standard) labeled directed graphs, where the set of edges is a subset of V × K × V.
On the contrary to labeled directed graphs, operations on edges (membership testing, addition and removal of edges) can be performed in labeled directed multi-graphs without equality tests over edge labels. Therefore the functors in this module can be applied on edge label types that are not equipped with equality or comparison functions (the Ocamlgraph library requires edge labels to be comparable).
The implementations provided in this module conform to the signature MultiGraph.G
.
In an implementation of this signature, all multi-graphs share the same
global set of (possible) vertices (type Vertex.t
) and the same global set
of (possible) edges (type Edge.t
). Equality, comparison and hash functions
on vertices and edges are provided in the corresponding modules Vertex
and
Edge
.
This module follows an aggressive approach for better performance. All
functions perform assertion checking on their arguments, specified in this
documentation by the Precondition tag. This assertion checking is
implemented with the assert
construct, and, hence, it is turned off by the
-noassert compiler option.
See also
module type G =sig
..end
module type P =sig
..end
module type I =sig
..end
module Persistent:sig
..end
module Imperative:sig
..end