package stog

  1. Overview
  2. Docs

Module Graph.Make_with_mapSource

This is a convenient functor using the Map module of the standard library to build the GMap module required by Make from the P parameter.

Parameters

Signature

Sourcetype key = P.t

The type of vertices

Sourcetype edge_data = Edge.t

The type of edge annotations

Sourcetype t

A graph

Sourceval create : unit -> t

Creating an empty graph.

Sourceval marshal : t -> string

Marshal the given graph.

Sourceval unmarshal : string -> t

Unmarshal.

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

Sourceval pred : t -> key -> (key * edge_data) list

Same as succ but returns the predecessors.

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

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

Sourceval rem_all : t -> (key * key) -> t

rem_all g (a, b) removes from graph g all edges from a to b.

Sourceval isolate : t -> key -> t

isolate g a removes all edges from and to vertice a.

Sourceval remove_node : t -> key -> t

remove_node g a removes the vertice a from the graph g.

Sourceval pred_roots : ?ignore_deps:edge_data list -> t -> key list

pred_roots g returns the list of vertices having no predecessor in the graph.

Sourceval succ_roots : t -> key list

Same as pred_roots but for vertices with no successor.

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

Sourceval recursive_preds : t -> ?pred:(edge_data -> bool) -> key -> key list

Same as recursive_succs but for predecessors.

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

Sourceval fold_succ : t -> (key -> (key * edge_data) list -> 'a -> 'a) -> 'a -> 'a
Sourceval fold_pred : t -> (key -> (key * edge_data) list -> 'a -> 'a) -> 'a -> 'a
Sourceval 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.

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

Same as iter_succ but with predecessors of each vertice.

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

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

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