module Graph:Sig_pack.S
Undirected imperative graphs with edges and vertices labeled with integer.
type
t
abstract type of graphs
module V:sig
..end
Vertices
typevertex =
V.t
module E:sig
..end
Edges
typeedge =
E.t
val is_directed : bool
is this an implementation of directed graphs?
val create : ?size:int -> unit -> t
Return an empty graph. Optionally, a size can be
given, which should be on the order of the expected number of
vertices that will be in the graph (for hash tables-based
implementations). The graph grows as needed, so size
is
just an initial guess.
val clear : t -> unit
Remove all vertices and edges from the given graph.
val copy : t -> t
copy g
returns a copy of g
. Vertices and edges (and eventually
marks, see module Mark
) are duplicated.
val add_vertex : t -> V.t -> unit
add_vertex g v
adds the vertex v
from the graph g
.
Do nothing if v
is already in g
.
val remove_vertex : t -> V.t -> unit
remove g v
removes the vertex v
from the graph g
(and all the edges going from v
in g
).
Do nothing if v
is not in g
.
val add_edge : t -> V.t -> V.t -> unit
add_edge g v1 v2
adds an edge from the vertex v1
to the vertex v2
in the graph g
.
Add also v1
(resp. v2
) in g
if v1
(resp. v2
) is not in g
.
Do nothing if this edge is already in g
.
val add_edge_e : t -> E.t -> unit
add_edge_e g e
adds the edge e
in the graph g
.
Add also E.src e
(resp. E.dst e
) in g
if E.src e
(resp. E.dst
e
) is not in g
.
Do nothing if e
is already in g
.
val remove_edge : t -> V.t -> V.t -> unit
remove_edge g v1 v2
removes the edge going from v1
to v2
from the
graph g
.
Do nothing if this edge is not in g
.
Invalid_argument
if v1
or v2
are not in g
.val remove_edge_e : t -> E.t -> unit
remove_edge_e g e
removes the edge e
from the graph g
.
Do nothing if e
is not in g
.
Invalid_argument
if E.src e
or E.dst e
are not in g
.module Mark:sig
..end
Vertices contains integers marks, which can be set or used by some
algorithms (see for instance module Marking
below)
val is_empty : t -> bool
val nb_vertex : t -> int
val nb_edges : t -> int
Degree of a vertex
val out_degree : t -> V.t -> int
out_degree g v
returns the out-degree of v
in g
.
Invalid_argument
if v
is not in g
.val in_degree : t -> V.t -> int
in_degree g v
returns the in-degree of v
in g
.
Invalid_argument
if v
is not in g
.val mem_vertex : t -> V.t -> bool
val mem_edge : t -> V.t -> V.t -> bool
val mem_edge_e : t -> E.t -> bool
val find_edge : t -> V.t -> V.t -> E.t
val find_all_edges : t -> V.t -> V.t -> E.t list
val succ : t -> V.t -> V.t list
succ g v
returns the successors of v
in g
.
Invalid_argument
if v
is not in g
.val pred : t -> V.t -> V.t list
pred g v
returns the predecessors of v
in g
.
Invalid_argument
if v
is not in g
.Labeled edges going from/to a vertex
val succ_e : t -> V.t -> E.t list
succ_e g v
returns the edges going from v
in g
.
Invalid_argument
if v
is not in g
.val pred_e : t -> V.t -> E.t list
pred_e g v
returns the edges going to v
in g
.
Invalid_argument
if v
is not in g
.iter/fold on all vertices/edges of a graph
val iter_vertex : (V.t -> unit) -> t -> unit
val iter_edges : (V.t -> V.t -> unit) -> t -> unit
val fold_vertex : (V.t -> 'a -> 'a) -> t -> 'a -> 'a
val fold_edges : (V.t -> V.t -> 'a -> 'a) -> t -> 'a -> 'a
val map_vertex : (V.t -> V.t) -> t -> t
map iterator on vertex
iter/fold on all labeled edges of a graph
val iter_edges_e : (E.t -> unit) -> t -> unit
val fold_edges_e : (E.t -> 'a -> 'a) -> t -> 'a -> 'a
Each iterator iterator f v g
iters f
to the successors/predecessors
of v
in the graph g
and raises Invalid_argument
if v
is not in
g
.
iter/fold on all successors/predecessors of a vertex.
val iter_succ : (V.t -> unit) -> t -> V.t -> unit
val iter_pred : (V.t -> unit) -> t -> V.t -> unit
val fold_succ : (V.t -> 'a -> 'a) -> t -> V.t -> 'a -> 'a
val fold_pred : (V.t -> 'a -> 'a) -> t -> V.t -> 'a -> 'a
iter/fold on all edges going from/to a vertex.
val iter_succ_e : (E.t -> unit) -> t -> V.t -> unit
val fold_succ_e : (E.t -> 'a -> 'a) -> t -> V.t -> 'a -> 'a
val iter_pred_e : (E.t -> unit) -> t -> V.t -> unit
val fold_pred_e : (E.t -> 'a -> 'a) -> t -> V.t -> 'a -> 'a
val find_vertex : t -> int -> V.t
vertex g i
returns a vertex of label i
in g
. The behaviour is
unspecified if g
has several vertices with label i
.
Note: this function is inefficient (linear in the number of vertices);
you should better keep the vertices as long as you create them.
val transitive_closure : ?reflexive:bool -> t -> t
transitive_closure ?reflexive g
returns the transitive closure
of g
(as a new graph). Loops (i.e. edges from a vertex to itself)
are added only if reflexive
is true
(default is false
).
val add_transitive_closure : ?reflexive:bool -> t -> t
add_transitive_closure ?reflexive g
replaces g
by its
transitive closure. Meaningless for persistent implementations
(then acts as transitive_closure
).
val transitive_reduction : ?reflexive:bool -> t -> t
transitive_reduction ?reflexive g
returns the transitive reduction
of g
(as a new graph). Loops (i.e. edges from a vertex to itself)
are removed only if reflexive
is true
(default is false
).
val replace_by_transitive_reduction : ?reflexive:bool -> t -> t
replace_by_transitive_reduction ?reflexive g
replaces g
by its
transitive reduction. Meaningless for persistent implementations
(then acts as transitive_reduction
).
val mirror : t -> t
mirror g
returns a new graph which is the mirror image of g
:
each edge from u
to v
has been replaced by an edge from v
to u
.
For undirected graphs, it simply returns a copy of g
.
val complement : t -> t
complement g
builds a new graph which is the complement of g
:
each edge present in g
is not present in the resulting graph and
vice-versa. Edges of the returned graph are unlabeled.
val intersect : t -> t -> t
intersect g1 g2
returns a new graph which is the intersection of g1
and g2
: each vertex and edge present in g1
*and* g2
is present
in the resulting graph.
val union : t -> t -> t
union g1 g2
returns a new graph which is the union of g1
and g2
:
each vertex and edge present in g1
*or* g2
is present in the
resulting graph.
module Dfs:sig
..end
Depth-first search
module Bfs:sig
..end
Breadth-first search
module Marking:sig
..end
Graph traversal with marking
module Classic:sig
..end
Classic graphs
module Rand:sig
..end
Random graphs
module Components:sig
..end
Strongly connected components
val shortest_path : t -> V.t -> V.t -> E.t list * int
Dijkstra's shortest path algorithm. Weights are the labels.
val ford_fulkerson : t ->
V.t -> V.t -> (E.t -> int) * int
Ford Fulkerson maximum flow algorithm
val goldberg_tarjan : t ->
V.t -> V.t -> (E.t -> int) * int
Goldberg-Tarjan maximum flow algorithm
val bellman_ford : t -> V.t -> E.t list
bellman_ford g v
finds a negative cycle from v
, and returns it,
or raises Not_found
if there is no such cycle
module PathCheck:sig
..end
Path checking
module Topological:sig
..end
Topological order
val spanningtree : t -> E.t list
Kruskal algorithm
val dot_output : t -> string -> unit
DOT output in a file
val display_with_gv : t -> unit
Displays the given graph using the external tools "dot" and "gv" and returns when gv's window is closed
val parse_gml_file : string -> t
val parse_dot_file : string -> t
val print_gml : Stdlib.Format.formatter -> t -> unit
val print_gml_file : t -> string -> unit