S (ocamlgraph.Graph.Imperative.S)

Module type Imperative.S

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
  (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
  (V : Sig.ANY_TYPE) : 
  Sig.IM with type V.label = V.t and type E.label = unit

Abstract Imperative Unlabeled Graphs.

module ConcreteLabeled
  (V : Sig.COMPARABLE)
  (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
  (V : Sig.ANY_TYPE)
  (E : Sig.ORDERED_TYPE_DFT) : 
  Sig.IM with type V.label = V.t and type E.label = E.t

Abstract Imperative Labeled Graphs.