Module Imperative.Digraph
Imperative Directed Graphs.
include S
module Concrete : functor (V : Graph.Sig.COMPARABLE) -> Graph.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 : Graph.Sig.ANY_TYPE) -> Graph.Sig.IM with type V.label = V.t and type E.label = unit
Abstract Imperative Unlabeled Graphs.
module ConcreteLabeled : functor (V : Graph.Sig.COMPARABLE) -> functor (E : Graph.Sig.ORDERED_TYPE_DFT) -> Graph.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 : Graph.Sig.ANY_TYPE) -> functor (E : Graph.Sig.ORDERED_TYPE_DFT) -> Graph.Sig.IM with type V.label = V.t and type E.label = E.t
Abstract Imperative Labeled Graphs.
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 : Graph.Sig.COMPARABLE) -> Graph.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 : Graph.Sig.COMPARABLE) -> functor (E : Graph.Sig.ORDERED_TYPE_DFT) -> Graph.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.