This is a convenient functor using the
Map module of the standard library to build the
GMap module required by
Make from the
module P : Map.OrderedType
module Edge : Map.OrderedType
type key = P.t
The type of vertices
type edge_data = Edge.t
The type of edge annotations
val create : unit -> t
Creating an empty graph.
val marshal : t -> string
Marshal the given graph.
val unmarshal : string -> t
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
b. If the vertice does not exist in the graph, the empty list is returned.
add g (a, b, data) adds to the graph
g an edge from
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.
rem g (a, b) pred removes from graph
g the edges from
b whose annotations satisfy the given predicate
pred_roots g returns the list of vertices having no predecessor in the graph.
pred_roots but for vertices with no successor.
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.
recursive_succs but for predecessors.
reverse g return a graph where all edges of
g are reversed, i.e. each edge from
b is replaced by an edge from
a, keeping the associated edge annotations.
iter_succ g f calls f on each vertice and its successors as returned by
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.
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 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
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
y if there are various edges from
cost g x y function must return
None if there is no edge from
The algorithm used is described here: Djikstra.