Module Pack.Graph
Undirected imperative graphs with edges and vertices labeled with integer.
Graph structure
module V : sig ... end
Vertices
type vertex
= V.t
module E : sig ... end
Edges
type edge
= E.t
Graph constructors and destructors
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.
- since
- ocamlgraph 1.4
val copy : t -> t
copy g
returns a copy ofg
. Vertices and edges (and eventually marks, see moduleMark
) are duplicated.
val add_vertex : t -> V.t -> unit
add_vertex g v
adds the vertexv
from the graphg
. Do nothing ifv
is already ing
.
val remove_vertex : t -> V.t -> unit
remove g v
removes the vertexv
from the graphg
(and all the edges going fromv
ing
). Do nothing ifv
is not ing
.
val add_edge : t -> V.t -> V.t -> unit
add_edge g v1 v2
adds an edge from the vertexv1
to the vertexv2
in the graphg
. Add alsov1
(resp.v2
) ing
ifv1
(resp.v2
) is not ing
. Do nothing if this edge is already ing
.
val add_edge_e : t -> E.t -> unit
add_edge_e g e
adds the edgee
in the graphg
. Add alsoE.src e
(resp.E.dst e
) ing
ifE.src e
(resp.E.dst e
) is not ing
. Do nothing ife
is already ing
.
val remove_edge : t -> V.t -> V.t -> unit
remove_edge g v1 v2
removes the edge going fromv1
tov2
from the graphg
. Do nothing if this edge is not ing
.- raises Invalid_argument
if
v1
orv2
are not ing
.
val remove_edge_e : t -> E.t -> unit
remove_edge_e g e
removes the edgee
from the graphg
. Do nothing ife
is not ing
.- raises Invalid_argument
if
E.src e
orE.dst e
are not ing
.
module Mark : sig ... end
Vertices contains integers marks, which can be set or used by some algorithms (see for instance module
Marking
below)
Size functions
Membership functions
Successors and predecessors of a vertex
val succ : t -> V.t -> V.t list
succ g v
returns the successors ofv
ing
.- raises Invalid_argument
if
v
is not ing
.
val pred : t -> V.t -> V.t list
pred g v
returns the predecessors ofv
ing
.- raises Invalid_argument
if
v
is not ing
.
Graph iterators
Vertex iterators
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
.
Basic operations
val find_vertex : t -> int -> V.t
vertex g i
returns a vertex of labeli
ing
. The behaviour is unspecified ifg
has several vertices with labeli
. 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 ofg
(as a new graph). Loops (i.e. edges from a vertex to itself) are added only ifreflexive
istrue
(default isfalse
).
val add_transitive_closure : ?reflexive:bool -> t -> t
add_transitive_closure ?reflexive g
replacesg
by its transitive closure. Meaningless for persistent implementations (then acts astransitive_closure
).
val transitive_reduction : ?reflexive:bool -> t -> t
transitive_reduction ?reflexive g
returns the transitive reduction ofg
(as a new graph). Loops (i.e. edges from a vertex to itself) are removed only ifreflexive
istrue
(default isfalse
).
val replace_by_transitive_reduction : ?reflexive:bool -> t -> t
replace_by_transitive_reduction ?reflexive g
replacesg
by its transitive reduction. Meaningless for persistent implementations (then acts astransitive_reduction
).
val mirror : t -> t
mirror g
returns a new graph which is the mirror image ofg
: each edge fromu
tov
has been replaced by an edge fromv
tou
. For undirected graphs, it simply returns a copy ofg
.
val complement : t -> t
complement g
builds a new graph which is the complement ofg
: each edge present ing
is not present in the resulting graph and vice-versa. Edges of the returned graph are unlabeled.
Traversal
module Dfs : sig ... end
Depth-first search
module Bfs : sig ... end
Breadth-first search
module Marking : sig ... end
Graph traversal with marking
module Coloring : sig ... end
Coloring
Graph generators
module Classic : sig ... end
Classic graphs
module Rand : sig ... end
Random graphs
module Components : sig ... end
Strongly connected components
Classical algorithms
val shortest_path : t -> V.t -> V.t -> E.t list * int
Dijkstra's shortest path algorithm. Weights are the labels.
val bellman_ford : t -> V.t -> E.t list
bellman_ford g v
finds a negative cycle fromv
, and returns it, or raisesNot_found
if there is no such cycle
module PathCheck : sig ... end
Path checking
module Topological : sig ... end
Topological order
Input / Output
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