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.

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

#
module Abstract : functor (V : Sig.ANY_TYPE) -> Sig.IM with type V.label = V.t and type E.label = unit

Abstract Imperative Unlabeled Graphs.

#
module ConcreteLabeled : functor (V : Sig.COMPARABLE) -> functor (E : Sig.ORDERED_TYPE_DFT) -> Sig.I with type V.t = V.t and type V.label = V.t and type E.t = V.t * E.t * V.t and type E.label = E.t

Imperative Labeled Graphs.

#
module AbstractLabeled : functor (V : Sig.ANY_TYPE) -> functor (E : Sig.ORDERED_TYPE_DFT) -> Sig.IM with type V.label = V.t and type E.label = E.t

Abstract Imperative Labeled Graphs.

end
#
module Digraph : sig

Imperative Directed Graphs.

include S

Bidirectional graphs

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.

#
module ConcreteBidirectional : 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, bidirectional graph.

#
module ConcreteBidirectionalLabeled : functor (V : Sig.COMPARABLE) -> functor (E : Sig.ORDERED_TYPE_DFT) -> Sig.I with type V.t = V.t and type V.label = V.t and type E.t = V.t * E.t * V.t and type E.label = E.t

Imperative Labeled and bidirectional graph.

end
#
module Graph : S

Imperative Undirected Graphs.

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

include Sig.I with type V.t = int and type V.label = int and type E.t = int * int
#
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
#
module Digraph : S

Imperative Directed Graphs implemented with adjacency matrices.

#
module Graph : S

Imperative Undirected Graphs implemented with adjacency matrices.

end
end