stog 1.0.0 (latest) · OCaml Package

Making a graph module.

parameter M
is the module defining a map with a vertice as key.

parameter Edge
is the module defining the type of the edge annotations. The compare function is used when adding an edge, to prevent adding an edge from x to y when an edge with the same annotation already exists from x to y.

Parameters

module M : GMap

module Edge : Map.OrderedType

Signature

type key = M.key

The type of vertices

type edge_data = Edge.t

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 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 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 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 succ.

val iter_pred : t -> (key -> (key * edge_data) list -> unit) -> unit

Same as 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.

parameter f_node
is used to, from a vertice, return a unique id, a label and attribute of a vertice.

parameter f_edge
can be specified to indicate a label and attribute from an edge annotation.

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.

package stog

Parameters

Signature