module Digraph:Imperative Directed Graphs.sig
..end
include Imperative.S
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
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