module Nonnegative

: sig

Weighted graphs without negative-cycles.

This graph maintains the invariant that it is free of such cycles that the total length of edges involving is negative. With introduction of those negative-cycles causes an inability to compute the shortest paths from arbitrary vertex. By using the graph modules defined here, introduction of such a cycle is automatically prevented.

module type WEIGHT = sig

Signature for edges' weights.

type label

Type for labels of graph edges.

type t

Type of edges' weights.

val weight : label -> t

Get the weight of an edge.

val compare : t -> t -> int

Weights must be ordered.

val add : t -> t -> t

Addition of weights.

val zero : t

Neutral element for add.

end

module Imperative : functor (G : Sig.IM) -> functor (W : WEIGHT with type label = G.E.label) -> sig

include Sig.IM with module V = G.V and module E = G.E

exception Negative_cycle of G.E.t list

end

module Persistent : functor (G : Sig.P) -> functor (W : WEIGHT with type label = G.E.label) -> sig

Persistent graphs with negative-cycle prevention

include Sig.P with module V = G.V and module E = G.E

exception Negative_cycle of G.E.t list

Exception NegativeCycle is raised whenever a negative cycle is introduced for the first time (either with add_edge or add_edge_e)

end