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.