Up

module Persistent

: sig

Persistent Graph Implementations.

#
module type S = sig

Signature of persistent 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.P 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

Persistent Unlabeled Graphs.

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

Abstract Persistent Unlabeled Graphs.

#
module ConcreteLabeled : functor (V : Sig.COMPARABLE) -> functor (E : Sig.ORDERED_TYPE_DFT) -> Sig.P 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

Persistent Labeled Graphs.

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

Abstract Persistent Labeled Graphs.

end
#
module Digraph : sig

Persistent Directed Graphs.

include S

Bidirectional graphs

Bidirectional graphs use more memory space (at worse the double) that standard concrete directional graphs. But accessing predecessors and removing a vertex are faster.

#
module ConcreteBidirectional : functor (V : Sig.COMPARABLE) -> Sig.P 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.P 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

Persistent Undirected Graphs.

end