Imperative.Digraph
Imperative Directed Graphs.
include S
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.
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.
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.