Module Nonnegative.PersistentSource

Persistent graphs with negative-cycle prevention

Parameters

module G : Sig.P
module W : Sig.WEIGHT with type edge = G.E.t

Signature

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

A persistent graph is a graph.

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

Graph structure

Sourcetype t

Abstract type of graphs

Sourcemodule V = G.V

Vertices have type V.t and are labeled with type V.label (note that an implementation may identify the vertex with its label)

Sourcetype vertex = V.t
Sourcemodule E = G.E

Edges have type E.t and are labeled with type E.label. src (resp. dst) returns the origin (resp. the destination) of a given edge.

Sourcetype edge = E.t
Sourceval is_directed : bool

Is this an implementation of directed graphs?

Size functions

Sourceval is_empty : t -> bool
Sourceval nb_vertex : t -> int
Sourceval nb_edges : t -> int

Degree of a vertex

Sourceval out_degree : t -> vertex -> int

out_degree g v returns the out-degree of v in g.

Sourceval in_degree : t -> vertex -> int

in_degree g v returns the in-degree of v in g.

Membership functions

Sourceval mem_vertex : t -> vertex -> bool
Sourceval mem_edge : t -> vertex -> vertex -> bool
Sourceval mem_edge_e : t -> edge -> bool
Sourceval find_edge : t -> vertex -> vertex -> edge

find_edge g v1 v2 returns the edge from v1 to v2 if it exists. Unspecified behaviour if g has several edges from v1 to v2.

Sourceval find_all_edges : t -> vertex -> vertex -> edge list

find_all_edges g v1 v2 returns all the edges from v1 to v2.

  • since ocamlgraph 1.8

Successors and predecessors

You should better use iterators on successors/predecessors (see Section "Vertex iterators").

Sourceval succ : t -> vertex -> vertex list

succ g v returns the successors of v in g.

Sourceval pred : t -> vertex -> vertex list

pred g v returns the predecessors of v in g.

Labeled edges going from/to a vertex

Sourceval succ_e : t -> vertex -> edge list

succ_e g v returns the edges going from v in g.

Sourceval pred_e : t -> vertex -> edge list

pred_e g v returns the edges going to v in g.

Graph iterators

Sourceval iter_vertex : (vertex -> unit) -> t -> unit

Iter on all vertices of a graph.

Sourceval fold_vertex : (vertex -> 'a -> 'a) -> t -> 'a -> 'a

Fold on all vertices of a graph.

Sourceval iter_edges : (vertex -> vertex -> unit) -> t -> unit

Iter on all edges of a graph. Edge label is ignored.

Sourceval fold_edges : (vertex -> vertex -> 'a -> 'a) -> t -> 'a -> 'a

Fold on all edges of a graph. Edge label is ignored.

Sourceval iter_edges_e : (edge -> unit) -> t -> unit

Iter on all edges of a graph.

Sourceval fold_edges_e : (edge -> 'a -> 'a) -> t -> 'a -> 'a

Fold on all edges of a graph.

Sourceval map_vertex : (vertex -> vertex) -> t -> t

Map on all vertices of a graph.

The current implementation requires the supplied function to be injective. Said otherwise, map_vertex cannot be used to contract a graph by mapping several vertices to the same vertex. To contract a graph, use instead create, add_vertex, and add_edge.

Vertex iterators

Each iterator iterator f v g iters f to the successors/predecessors of v in the graph g and raises Invalid_argument if v is not in g. It is the same for functions fold_* which use an additional accumulator.

<b>Time complexity for ocamlgraph implementations:</b> operations on successors are in O(1) amortized for imperative graphs and in O(ln(|V|)) for persistent graphs while operations on predecessors are in O(max(|V|,|E|)) for imperative graphs and in O(max(|V|,|E|)*ln|V|) for persistent graphs.

iter/fold on all successors/predecessors of a vertex.

Sourceval iter_succ : (vertex -> unit) -> t -> vertex -> unit
Sourceval iter_pred : (vertex -> unit) -> t -> vertex -> unit
Sourceval fold_succ : (vertex -> 'a -> 'a) -> t -> vertex -> 'a -> 'a
Sourceval fold_pred : (vertex -> 'a -> 'a) -> t -> vertex -> 'a -> 'a

iter/fold on all edges going from/to a vertex.

Sourceval iter_succ_e : (edge -> unit) -> t -> vertex -> unit
Sourceval fold_succ_e : (edge -> 'a -> 'a) -> t -> vertex -> 'a -> 'a
Sourceval iter_pred_e : (edge -> unit) -> t -> vertex -> unit
Sourceval fold_pred_e : (edge -> 'a -> 'a) -> t -> vertex -> 'a -> 'a
Sourceval empty : t

The empty graph.

Sourceval add_vertex : t -> vertex -> t

add_vertex g v adds the vertex v to the graph g. Just return g if v is already in g.

Sourceval remove_vertex : t -> vertex -> t

remove g v removes the vertex v from the graph g (and all the edges going from v in g). Just return g if v is not in g.

<b>Time complexity for ocamlgraph implementations:</b> O(|V|*ln(|V|)) for unlabeled graphs and O(|V|*max(ln(|V|),D)) for labeled graphs. D is the maximal degree of the graph.

Sourceval add_edge : t -> vertex -> vertex -> t

add_edge g v1 v2 adds an edge from the vertex v1 to the vertex v2 in the graph g. Add also v1 (resp. v2) in g if v1 (resp. v2) is not in g. Just return g if this edge is already in g.

Sourceval add_edge_e : t -> edge -> t

add_edge_e g e adds the edge e in the graph g. Add also E.src e (resp. E.dst e) in g if E.src e (resp. E.dst e) is not in g. Just return g if e is already in g.

Sourceval remove_edge : t -> vertex -> vertex -> t

remove_edge g v1 v2 removes the edge going from v1 to v2 from the graph g. If the graph is labelled, all the edges going from v1 to v2 are removed from g. Just return g if this edge is not in g.

Sourceval remove_edge_e : t -> edge -> t

remove_edge_e g e removes the edge e from the graph g. Just return g if e is not in g.

Sourceexception 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)