Module type Oug_graph.S


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

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
iter_succ g f calls f on each vertice and its successors as returned by Oug_graph.S.succ.
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.