module Make_with_map (P : Map.OrderedType) (Edge : Map.OrderedType) : S with type key = P.t and type edge_data = Edge.t
This is a convenient functor using the
Map module of the standard library
to build the
Stog_graph.GMap module required by
Stog_graph.Make from the
P parameter.
| Parameters: |
P |
: |
Map.OrderedType
|
Edge |
: |
Map.OrderedType
|
|
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
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
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
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
Stog_graph.S.succ.
val iter_pred : t ->
(key -> (key * edge_data) list -> unit) ->
unit
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.