module type S =This is the output signature of the functor creating a graph module.`sig`

..`end`

`type `

key

The type of vertices

`type `

edge_data

The type of edge annotations

`type `

t

A graph

`val create : ``unit -> t`

Creating an empty graph.

`val marshal : ``t -> string`

Marshal the given graph.

`val unmarshal : ``string -> t`

Unmarshal.

`val succ : ``t ->`

key -> (key * edge_data) list

`succ g a`

returns the successors of a vertice as a list of pairs
`(successor, edge annotation)`

. A vertice `b`

can appear more than once in the
list if there are edges with different annotations between `a`

and `b`

.
If the vertice does not exist in the graph, the empty list is returned.`val pred : ``t ->`

key -> (key * edge_data) list

Same as

`Oug_graph.S.succ`

but returns the predecessors.`val add : ``t ->`

key * key * edge_data -> t

`add g (a, b, data)`

adds to the graph `g`

an edge from `a`

to `b`

annotated with `data`

. The edge data comparison function is used
to know whether the same edge with the same annotation already exists. If so,
no new edge is added.`val rem : ``t ->`

key * key ->

(edge_data -> bool) -> t

`rem g (a, b) pred`

removes from graph `g`

the edges from `a`

to `b`

whose annotations satisfy the given predicate `pred`

.`val rem_all : ``t -> key * key -> t`

`rem_all g (a, b)`

removes from graph `g`

all edges from `a`

to `b`

.`val isolate : ``t -> key -> t`

`isolate g a`

removes all edges from and to vertice `a`

.`val remove_node : ``t -> key -> t`

`remove_node g a`

removes the vertice `a`

from the graph `g`

.`val pred_roots : ``?ignore_deps:edge_data list ->`

t -> key list

`pred_roots g`

returns the list of vertices having no predecessor in the graph.`val succ_roots : ``t -> key list`

Same as

`Oug_graph.S.pred_roots`

but for vertices with no successor.`val recursive_succs : ``t ->`

?pred:(edge_data -> bool) ->

key -> key list

`recursive_succs t key`

returns the list of all nodes "under" the given
one; the given predicate can be used to follow only some edges.`val recursive_preds : ``t ->`

?pred:(edge_data -> bool) ->

key -> key list

Same as

`Oug_graph.S.recursive_succs`

but for predecessors.`val reverse : ``t -> t`

`reverse g`

return a graph where all edges of `g`

are reversed, i.e. each
edge from `a`

to `b`

is replaced by an edge from `b`

to `a`

, keeping the
associated edge annotations.`val fold_succ : ``t ->`

(key ->

(key * edge_data) list -> 'a -> 'a) ->

'a -> 'a

`val fold_pred : ``t ->`

(key ->

(key * edge_data) list -> 'a -> 'a) ->

'a -> 'a

`val iter_succ : ``t ->`

(key -> (key * edge_data) list -> unit) ->

unit

`val iter_pred : ``t ->`

(key -> (key * edge_data) list -> unit) ->

unit

Same as

`Oug_graph.S.iter_succ`

but with predecessors of each vertice.`val dot_of_graph : ``?f_edge:(edge_data -> string * (string * string) list) ->`

f_node:(key -> string * string * (string * string) list) ->

t -> string

`dot_of_graph ~f_node g`

returns the graphviz code to represent the
given graph.`f_edge`

: can be specified to indicate a label and attribute from
an edge annotation.`f_node`

: is used to, from a vertice, return a unique id, a label
and attribute of a vertice.`val nodes_by_pred_order : ``t -> key list`

`nodes_by_pred_order g`

returns a sorted list of vertices. Vertices with
no predecessor are first in the list. If an edge exists from `a`

to `b`

,
then `a`

will be before `b`

in the list. Vertices beloning to a cycle
will not appear in the list.`val shortest_path : ``t ->`

(t ->

key * key -> (float * edge_data) option) ->

key * key ->

(key * edge_data * key) list

`shortest_path g cost (a, b)`

computes the shortest path from `a`

to `b`

according to the `cost`

function. This function must return a
stricly positive value and the edge edge annotation used to get
this value (it may be possible to have different costs to go from
`x`

to `y`

if there are various edges from `x`

to `y`

). The `cost g x y`

function must return `None`

if there is no edge from `x`

to `y`

.
The algorithm used is described here:
Djikstra.