Module Graph
module Sig : sig
module type VERTEX = sig
Signature for vertices.
type t
val compare : t -> t -> int
val hash : t -> int
val equal : t -> t -> bool
type label
val create : label -> t
val label : t -> label
end
module type EDGE = sig
Signature for edges.
type t
val compare : t -> t -> int
type vertex
val src : t -> vertex
Edge origin.
val dst : t -> vertex
Edge destination.
type label
val create : vertex -> label -> vertex -> t
create v1 l v2 creates an edge from v1 to v2 with label l
val label : t -> label
Get the label of an edge.
end
module type G = sig
Common signature for all graphs.
type t
Abstract type of graphs
module V : VERTEX
Vertices have type
V.t and are labeled with type V.label
(note that an implementation may identify the vertex with its
label)
type vertex = V.t
module E : sig
Edges have type
E.t and are labeled with type E.label.
src (resp. dst) returns the origin (resp. the destination) of a
given edge.
type t
val compare : t -> t -> int
type vertex = vertex
val src : t -> vertex
Edge origin.
val dst : t -> vertex
Edge destination.
type label
val create : vertex -> label -> vertex -> t
create v1 l v2 creates an edge from v1 to v2 with label l
val label : t -> label
Get the label of an edge.
end
type edge = E.t
val is_directed : bool
Is this an implementation of directed graphs?
val is_empty : t -> bool
val nb_vertex : t -> int
val nb_edges : t -> int
val out_degree : t -> vertex -> int
out_degree g v returns the out-degree of v in g.
Raises
Invalid_argument if v is not in g.
val in_degree : t -> vertex -> int
in_degree g v returns the in-degree of v in g.
Raises
Invalid_argument if v is not in g.
val mem_vertex : t -> vertex -> bool
val mem_edge : t -> vertex -> vertex -> bool
val mem_edge_e : t -> edge -> bool
val find_edge : t -> vertex -> vertex -> edge
find_edge g v1 v2 returns the edge from v1 to v2 if it exists.
Unspecified behaviour if g has several edges from v1 to v2.
Raises
Not_found if no such edge exists.
val find_all_edges : t -> vertex -> vertex -> edge list
val succ : t -> vertex -> vertex list
succ g v returns the successors of v in g.
Raises
Invalid_argument if v is not in g.
val pred : t -> vertex -> vertex list
pred g v returns the predecessors of v in g.
Raises
Invalid_argument if v is not in g.
val succ_e : t -> vertex -> edge list
succ_e g v returns the edges going from v in g.
Raises
Invalid_argument if v is not in g.
val pred_e : t -> vertex -> edge list
pred_e g v returns the edges going to v in g.
Raises
Invalid_argument if v is not in g.
val iter_vertex : vertex -> unit -> t -> unit
Iter on all vertices of a graph.
val fold_vertex : vertex -> 'a -> 'a -> t -> 'a -> 'a
Fold on all vertices of a graph.
val iter_edges : vertex -> vertex -> unit -> t -> unit
Iter on all edges of a graph. Edge label is ignored.
val fold_edges : vertex -> vertex -> 'a -> 'a -> t -> 'a -> 'a
Fold on all edges of a graph. Edge label is ignored.
val iter_edges_e : edge -> unit -> t -> unit
Iter on all edges of a graph.
val fold_edges_e : edge -> 'a -> 'a -> t -> 'a -> 'a
Fold on all edges of a graph.
val map_vertex : vertex -> vertex -> t -> t
Map on all vertices of a graph.
val iter_succ : vertex -> unit -> t -> vertex -> unit
val iter_pred : vertex -> unit -> t -> vertex -> unit
val fold_succ : vertex -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val fold_pred : vertex -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val iter_succ_e : edge -> unit -> t -> vertex -> unit
val fold_succ_e : edge -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val iter_pred_e : edge -> unit -> t -> vertex -> unit
val fold_pred_e : edge -> 'a -> 'a -> t -> vertex -> 'a -> 'a
end
module type P = sig
Signature for persistent (i.e. immutable) graph.
type t
Abstract type of graphs
module V : VERTEX
Vertices have type
V.t and are labeled with type V.label
(note that an implementation may identify the vertex with its
label)
type vertex = V.t
module E : sig
Edges have type
E.t and are labeled with type E.label.
src (resp. dst) returns the origin (resp. the destination) of a
given edge.
type t
val compare : t -> t -> int
type vertex = vertex
val src : t -> vertex
Edge origin.
val dst : t -> vertex
Edge destination.
type label
val create : vertex -> label -> vertex -> t
create v1 l v2 creates an edge from v1 to v2 with label l
val label : t -> label
Get the label of an edge.
end
type edge = E.t
val is_directed : bool
Is this an implementation of directed graphs?
val is_empty : t -> bool
val nb_vertex : t -> int
val nb_edges : t -> int
val out_degree : t -> vertex -> int
out_degree g v returns the out-degree of v in g.
Raises
Invalid_argument if v is not in g.
val in_degree : t -> vertex -> int
in_degree g v returns the in-degree of v in g.
Raises
Invalid_argument if v is not in g.
val mem_vertex : t -> vertex -> bool
val mem_edge : t -> vertex -> vertex -> bool
val mem_edge_e : t -> edge -> bool
val find_edge : t -> vertex -> vertex -> edge
find_edge g v1 v2 returns the edge from v1 to v2 if it exists.
Unspecified behaviour if g has several edges from v1 to v2.
Raises
Not_found if no such edge exists.
val find_all_edges : t -> vertex -> vertex -> edge list
val succ : t -> vertex -> vertex list
succ g v returns the successors of v in g.
Raises
Invalid_argument if v is not in g.
val pred : t -> vertex -> vertex list
pred g v returns the predecessors of v in g.
Raises
Invalid_argument if v is not in g.
val succ_e : t -> vertex -> edge list
succ_e g v returns the edges going from v in g.
Raises
Invalid_argument if v is not in g.
val pred_e : t -> vertex -> edge list
pred_e g v returns the edges going to v in g.
Raises
Invalid_argument if v is not in g.
val iter_vertex : vertex -> unit -> t -> unit
Iter on all vertices of a graph.
val fold_vertex : vertex -> 'a -> 'a -> t -> 'a -> 'a
Fold on all vertices of a graph.
val iter_edges : vertex -> vertex -> unit -> t -> unit
Iter on all edges of a graph. Edge label is ignored.
val fold_edges : vertex -> vertex -> 'a -> 'a -> t -> 'a -> 'a
Fold on all edges of a graph. Edge label is ignored.
val iter_edges_e : edge -> unit -> t -> unit
Iter on all edges of a graph.
val fold_edges_e : edge -> 'a -> 'a -> t -> 'a -> 'a
Fold on all edges of a graph.
val map_vertex : vertex -> vertex -> t -> t
Map on all vertices of a graph.
val iter_succ : vertex -> unit -> t -> vertex -> unit
val iter_pred : vertex -> unit -> t -> vertex -> unit
val fold_succ : vertex -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val fold_pred : vertex -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val iter_succ_e : edge -> unit -> t -> vertex -> unit
val fold_succ_e : edge -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val iter_pred_e : edge -> unit -> t -> vertex -> unit
val fold_pred_e : edge -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val empty : t
The empty graph.
val add_vertex : t -> vertex -> t
add_vertex g v adds the vertex v to the graph g.
Just return g if v is already in g.
val remove_vertex : t -> vertex -> t
Time complexity for ocamlgraph implementations: O(|V|*ln(|V|)) for unlabeled graphs and O(|V|*max(ln(|V|),D)) for labeled graphs. D is the maximal degree of the graph.
remove g v removes the vertex v from the graph g
(and all the edges going from v in g).
Just return g if v is not in g.Time complexity for ocamlgraph implementations: O(|V|*ln(|V|)) for unlabeled graphs and O(|V|*max(ln(|V|),D)) for labeled graphs. D is the maximal degree of the graph.
val add_edge : t -> vertex -> vertex -> t
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.
Just return g if this edge is already in g.
val add_edge_e : t -> edge -> t
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.
Just return g if e is already in g.
val remove_edge : t -> vertex -> vertex -> t
remove_edge g v1 v2 removes the edge going from v1 to v2 from the
graph g. If the graph is labelled, all the edges going from v1 to
v2 are removed from g.
Just return g if this edge is not in g.
Raises
Invalid_argument if v1 or v2 are not in g.
val remove_edge_e : t -> edge -> t
remove_edge_e g e removes the edge e from the graph g.
Just return g if e is not in g.
Raises
Invalid_argument if E.src e or E.dst e are not in g.
end
module type I = sig
Signature for imperative (i.e. mutable) graphs.
type t
Abstract type of graphs
module V : VERTEX
Vertices have type
V.t and are labeled with type V.label
(note that an implementation may identify the vertex with its
label)
type vertex = V.t
module E : sig
Edges have type
E.t and are labeled with type E.label.
src (resp. dst) returns the origin (resp. the destination) of a
given edge.
type t
val compare : t -> t -> int
type vertex = vertex
val src : t -> vertex
Edge origin.
val dst : t -> vertex
Edge destination.
type label
val create : vertex -> label -> vertex -> t
create v1 l v2 creates an edge from v1 to v2 with label l
val label : t -> label
Get the label of an edge.
end
type edge = E.t
val is_directed : bool
Is this an implementation of directed graphs?
val is_empty : t -> bool
val nb_vertex : t -> int
val nb_edges : t -> int
val out_degree : t -> vertex -> int
out_degree g v returns the out-degree of v in g.
Raises
Invalid_argument if v is not in g.
val in_degree : t -> vertex -> int
in_degree g v returns the in-degree of v in g.
Raises
Invalid_argument if v is not in g.
val mem_vertex : t -> vertex -> bool
val mem_edge : t -> vertex -> vertex -> bool
val mem_edge_e : t -> edge -> bool
val find_edge : t -> vertex -> vertex -> edge
find_edge g v1 v2 returns the edge from v1 to v2 if it exists.
Unspecified behaviour if g has several edges from v1 to v2.
Raises
Not_found if no such edge exists.
val find_all_edges : t -> vertex -> vertex -> edge list
val succ : t -> vertex -> vertex list
succ g v returns the successors of v in g.
Raises
Invalid_argument if v is not in g.
val pred : t -> vertex -> vertex list
pred g v returns the predecessors of v in g.
Raises
Invalid_argument if v is not in g.
val succ_e : t -> vertex -> edge list
succ_e g v returns the edges going from v in g.
Raises
Invalid_argument if v is not in g.
val pred_e : t -> vertex -> edge list
pred_e g v returns the edges going to v in g.
Raises
Invalid_argument if v is not in g.
val iter_vertex : vertex -> unit -> t -> unit
Iter on all vertices of a graph.
val fold_vertex : vertex -> 'a -> 'a -> t -> 'a -> 'a
Fold on all vertices of a graph.
val iter_edges : vertex -> vertex -> unit -> t -> unit
Iter on all edges of a graph. Edge label is ignored.
val fold_edges : vertex -> vertex -> 'a -> 'a -> t -> 'a -> 'a
Fold on all edges of a graph. Edge label is ignored.
val iter_edges_e : edge -> unit -> t -> unit
Iter on all edges of a graph.
val fold_edges_e : edge -> 'a -> 'a -> t -> 'a -> 'a
Fold on all edges of a graph.
val map_vertex : vertex -> vertex -> t -> t
Map on all vertices of a graph.
val iter_succ : vertex -> unit -> t -> vertex -> unit
val iter_pred : vertex -> unit -> t -> vertex -> unit
val fold_succ : vertex -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val fold_pred : vertex -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val iter_succ_e : edge -> unit -> t -> vertex -> unit
val fold_succ_e : edge -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val iter_pred_e : edge -> unit -> t -> vertex -> unit
val fold_pred_e : edge -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val create : ?size:int -> unit -> t
create () returns 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
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 -> vertex -> unit
add_vertex g v adds the vertex v to the graph g.
Do nothing if v is already in g.
val remove_vertex : t -> vertex -> unit
Time complexity for ocamlgraph implementations: O(|V|*ln(D)) for unlabeled graphs and O(|V|*D) for labeled graphs. D is the maximal degree of the graph.
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.Time complexity for ocamlgraph implementations: O(|V|*ln(D)) for unlabeled graphs and O(|V|*D) for labeled graphs. D is the maximal degree of the graph.
val add_edge : t -> vertex -> vertex -> 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 -> edge -> 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 -> vertex -> vertex -> unit
remove_edge g v1 v2 removes the edge going from v1 to v2 from the
graph g. If the graph is labelled, all the edges going from v1 to
v2 are removed from g.
Do nothing if this edge is not in g.
Raises
Invalid_argument if v1 or v2 are not in g.
val remove_edge_e : t -> edge -> unit
remove_edge_e g e removes the edge e from the graph g.
Do nothing if e is not in g.
Raises
Invalid_argument if E.src e or E.dst e are not in g.
end
module type MARK = sig
Signature for marks on vertices.
type graph
Type of graphs.
type vertex
Type of graph vertices.
val clear : graph -> unit
clear g sets all the marks to 0 for all the vertices of g.
val get : vertex -> int
Mark value (in O(1)).
val set : vertex -> int -> unit
Set the mark of the given vertex.
end
module type IM = sig
Signature for imperative graphs with marks on vertices.
type t
Abstract type of graphs
module V : VERTEX
Vertices have type
V.t and are labeled with type V.label
(note that an implementation may identify the vertex with its
label)
type vertex = V.t
module E : sig
Edges have type
E.t and are labeled with type E.label.
src (resp. dst) returns the origin (resp. the destination) of a
given edge.
type t
val compare : t -> t -> int
type vertex = vertex
val src : t -> vertex
Edge origin.
val dst : t -> vertex
Edge destination.
type label
val create : vertex -> label -> vertex -> t
create v1 l v2 creates an edge from v1 to v2 with label l
val label : t -> label
Get the label of an edge.
end
type edge = E.t
val is_directed : bool
Is this an implementation of directed graphs?
val is_empty : t -> bool
val nb_vertex : t -> int
val nb_edges : t -> int
val out_degree : t -> vertex -> int
out_degree g v returns the out-degree of v in g.
Raises
Invalid_argument if v is not in g.
val in_degree : t -> vertex -> int
in_degree g v returns the in-degree of v in g.
Raises
Invalid_argument if v is not in g.
val mem_vertex : t -> vertex -> bool
val mem_edge : t -> vertex -> vertex -> bool
val mem_edge_e : t -> edge -> bool
val find_edge : t -> vertex -> vertex -> edge
find_edge g v1 v2 returns the edge from v1 to v2 if it exists.
Unspecified behaviour if g has several edges from v1 to v2.
Raises
Not_found if no such edge exists.
val find_all_edges : t -> vertex -> vertex -> edge list
val succ : t -> vertex -> vertex list
succ g v returns the successors of v in g.
Raises
Invalid_argument if v is not in g.
val pred : t -> vertex -> vertex list
pred g v returns the predecessors of v in g.
Raises
Invalid_argument if v is not in g.
val succ_e : t -> vertex -> edge list
succ_e g v returns the edges going from v in g.
Raises
Invalid_argument if v is not in g.
val pred_e : t -> vertex -> edge list
pred_e g v returns the edges going to v in g.
Raises
Invalid_argument if v is not in g.
val iter_vertex : vertex -> unit -> t -> unit
Iter on all vertices of a graph.
val fold_vertex : vertex -> 'a -> 'a -> t -> 'a -> 'a
Fold on all vertices of a graph.
val iter_edges : vertex -> vertex -> unit -> t -> unit
Iter on all edges of a graph. Edge label is ignored.
val fold_edges : vertex -> vertex -> 'a -> 'a -> t -> 'a -> 'a
Fold on all edges of a graph. Edge label is ignored.
val iter_edges_e : edge -> unit -> t -> unit
Iter on all edges of a graph.
val fold_edges_e : edge -> 'a -> 'a -> t -> 'a -> 'a
Fold on all edges of a graph.
val map_vertex : vertex -> vertex -> t -> t
Map on all vertices of a graph.
val iter_succ : vertex -> unit -> t -> vertex -> unit
val iter_pred : vertex -> unit -> t -> vertex -> unit
val fold_succ : vertex -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val fold_pred : vertex -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val iter_succ_e : edge -> unit -> t -> vertex -> unit
val fold_succ_e : edge -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val iter_pred_e : edge -> unit -> t -> vertex -> unit
val fold_pred_e : edge -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val create : ?size:int -> unit -> t
create () returns 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
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 -> vertex -> unit
add_vertex g v adds the vertex v to the graph g.
Do nothing if v is already in g.
val remove_vertex : t -> vertex -> unit
Time complexity for ocamlgraph implementations: O(|V|*ln(D)) for unlabeled graphs and O(|V|*D) for labeled graphs. D is the maximal degree of the graph.
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.Time complexity for ocamlgraph implementations: O(|V|*ln(D)) for unlabeled graphs and O(|V|*D) for labeled graphs. D is the maximal degree of the graph.
val add_edge : t -> vertex -> vertex -> 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 -> edge -> 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 -> vertex -> vertex -> unit
remove_edge g v1 v2 removes the edge going from v1 to v2 from the
graph g. If the graph is labelled, all the edges going from v1 to
v2 are removed from g.
Do nothing if this edge is not in g.
Raises
Invalid_argument if v1 or v2 are not in g.
val remove_edge_e : t -> edge -> unit
remove_edge_e g e removes the edge e from the graph g.
Do nothing if e is not in g.
Raises
Invalid_argument if E.src e or E.dst e are not in g.
module Mark : sig
Mark on vertices.
Marks can be used if you want to store some information on vertices:
it is more efficient to use marks than an external table.
type graph = t
type vertex = vertex
val clear : graph -> unit
clear g sets all the marks to 0 for all the vertices of g.
val get : vertex -> int
Mark value (in O(1)).
val set : vertex -> int -> unit
Set the mark of the given vertex.
end
end
module type ANY_TYPE = sig
Signature with only an abstract type.
type t
end
module type ORDERED_TYPE = sig
Signature equivalent to
Set.OrderedType.
type t
val compare : t -> t -> int
end
module type ORDERED_TYPE_DFT = sig
Signature equivalent to
Set.OrderedType with a default value.
type t
val compare : t -> t -> int
val default : t
end
module type HASHABLE = sig
Signature equivalent to
Hashtbl.HashedType.
type t
val hash : t -> int
val equal : t -> t -> bool
end
module type COMPARABLE = sig
Signature merging ORDERED_TYPE and HASHABLE.
type t
val compare : t -> t -> int
val hash : t -> int
val equal : t -> t -> bool
end
end
module Sig_pack : sig
module type S = sig
Signature gathering an imperative graph signature and all algorithms.
Vertices and edges are labeled with integers.
type t
abstract type of graphs
module V : sig
Vertices
type t
val compare : t -> t -> int
val hash : t -> int
val equal : t -> t -> bool
type label = int
val create : label -> t
val label : t -> label
end
type vertex = V.t
module E : sig
Edges
type t
val compare : t -> t -> int
val src : t -> V.t
val dst : t -> V.t
type label = int
val create : V.t -> label -> V.t -> t
create v1 l v2 creates an edge from v1 to v2 with label l
val label : t -> label
type vertex = V.t
end
type edge = 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
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.
Raises
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.
Raises
Invalid_argument if E.src e or E.dst e are not in g.
module Mark : sig
Vertices contains integers marks, which can be set or used by some
algorithms (see for instance module
Marking below)
type graph = t
type vertex = V.t
val clear : t -> unit
clear g sets all marks to 0 from all the vertives of g.
val get : V.t -> int
val set : V.t -> int -> unit
end
val is_empty : t -> bool
val nb_vertex : t -> int
val nb_edges : t -> int
val out_degree : t -> V.t -> int
out_degree g v returns the out-degree of v in g.
Raises
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.
Raises
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.
Raises
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.
Raises
Invalid_argument if v is not in g.
val succ_e : t -> V.t -> E.t list
succ_e g v returns the edges going from v in g.
Raises
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.
Raises
Invalid_argument if v is not in g.
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
val iter_edges_e : E.t -> unit -> t -> unit
val fold_edges_e : E.t -> 'a -> 'a -> t -> 'a -> 'a
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
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
Depth-first search
val iter : ?pre:V.t -> unit -> ?post:V.t -> unit -> t -> unit
iter pre post g visits all nodes of g in depth-first search,
applying pre to each visited node before its successors,
and post after them. Each node is visited exactly once.
val prefix : V.t -> unit -> t -> unit
applies only a prefix function
val postfix : V.t -> unit -> t -> unit
applies only a postfix function
val iter_component : ?pre:V.t -> unit -> ?post:V.t -> unit -> t -> V.t -> unit
val prefix_component : V.t -> unit -> t -> V.t -> unit
val postfix_component : V.t -> unit -> t -> V.t -> unit
val has_cycle : t -> bool
end
module Bfs : sig
Breadth-first search
val iter : V.t -> unit -> t -> unit
val iter_component : V.t -> unit -> t -> V.t -> unit
end
module Marking : sig
Graph traversal with marking
val dfs : t -> unit
val has_cycle : t -> bool
end
module Classic : sig
Classic graphs
val divisors : int -> t
divisors n builds the graph of divisors.
Vertices are integers from 2 to n. i is connected to j if
and only if i divides j.
Raises
Invalid_argument is n < 2.
val de_bruijn : int -> t
de_bruijn n builds the de Bruijn graph of order n.
Vertices are bit sequences of length n (encoded as their
interpretation as binary integers). The sequence xw is connected
to the sequence wy for any bits x and y and any bit sequence
w of length n-1.
Raises
Invalid_argument is n < 1 or n > Sys.word_size-1.
val vertex_only : int -> t
vertex_only n builds a graph with n vertices and no edge.
val full : ?self:bool -> int -> t
full n builds a graph with n vertices and all possible edges.
The optional argument self indicates if loop edges should be added
(default value is true).
end
module Rand : sig
Random graphs
val graph : ?loops:bool -> v:int -> e:int -> unit -> t
random v e generates a random with v vertices and e edges.
val labeled : V.t -> V.t -> E.label -> ?loops:bool -> v:int -> e:int -> unit -> t
random_labeled f is similar to random except that edges are
labeled using function f
val gnp : ?loops:bool -> v:int -> prob:float -> unit -> t
gnp v prob generates a random graph with v vertices and
where each edge is selected with probality prob (G(n,p) model)
val gnp_labeled : V.t -> V.t -> E.label -> ?loops:bool -> v:int -> prob:float -> unit -> t
gnp_labeled add_edge v prob is similar to gnp except that
edges are labeled using function f
end
module Components : sig
Strongly connected components
val scc : t -> (int * V.t -> int)
strongly connected components
val scc_array : t -> V.t list array
val scc_list : t -> V.t list list
end
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 : t -> V.t -> V.t -> (E.t -> int * int)
Goldberg 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
Path checking
type path_checker
val create : t -> path_checker
val check_path : path_checker -> V.t -> V.t -> bool
end
module Topological : sig
Topological order
val fold : V.t -> 'a -> 'a -> t -> 'a -> 'a
val iter : V.t -> unit -> t -> unit
val fold_stable : V.t -> 'a -> 'a -> t -> 'a -> 'a
val iter_stable : V.t -> unit -> t -> unit
end
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_file : t -> string -> unit
end
end
module Dot_ast : sig
type id =
| Ident of string
| Number of string
| String of string
| Html of string
type attr = (id * id option) list
type compass_pt =
| N
| Ne
| E
| Se
| S
| Sw
| W
| Nw
type port =
| PortId of id * compass_pt option
| PortC of compass_pt
type node_id = (id * port option)
type subgraph =
| SubgraphId of id
| SubgraphDef of id option * stmt list
type node =
| NodeId of node_id
| NodeSub of subgraph
type stmt =
| Node_stmt of node_id * attr list
| Edge_stmt of node * node list * attr list
| Attr_graph of attr list
| Attr_node of attr list
| Attr_edge of attr list
| Equal of id * id
| Subgraph of subgraph
type file = {
strict : bool;
digraph : bool;
id : id option;
stmts : stmt list;
}
end
module Unionfind : sig
module type HashedOrderedType = sig
type t
val equal : t -> t -> bool
val hash : t -> int
val compare : t -> t -> int
end
module type S = sig
type elt
type t
val init : elt list -> t
val find : elt -> t -> elt
val union : elt -> elt -> t -> unit
end
end
module Heap : sig
module type Ordered = sig
type t
val compare : t -> t -> int
end
exception EmptyHeap
module type FunctionalSig = sig
type elt
type t
val empty : t
val add : elt -> t -> t
val maximum : t -> elt
val remove : t -> t
val iter : elt -> unit -> t -> unit
val fold : elt -> 'a -> 'a -> t -> 'a -> 'a
end
end
module Bitv : sig
type t
val create : int -> bool -> t
val init : int -> int -> bool -> t
val set : t -> int -> bool -> unit
val get : t -> int -> bool
val length : t -> int
val max_length : int
val copy : t -> t
val append : t -> t -> t
val concat : t list -> t
val sub : t -> int -> int -> t
val fill : t -> int -> int -> bool -> unit
val blit : t -> int -> t -> int -> int -> unit
val iter : bool -> unit -> t -> unit
val map : bool -> bool -> t -> t
val iteri : int -> bool -> unit -> t -> unit
val mapi : int -> bool -> bool -> t -> t
val fold_left : 'a -> bool -> 'a -> 'a -> t -> 'a
val fold_right : bool -> 'a -> 'a -> t -> 'a -> 'a
val foldi_left : 'a -> int -> bool -> 'a -> 'a -> t -> 'a
val foldi_right : int -> bool -> 'a -> 'a -> t -> 'a -> 'a
val gray_iter : t -> unit -> int -> unit
val bw_and : t -> t -> t
val bw_or : t -> t -> t
val bw_xor : t -> t -> t
val bw_not : t -> t
val shiftl : t -> int -> t
val shiftr : t -> int -> t
val all_zeros : t -> bool
val all_ones : t -> bool
val to_string : t -> string
val of_string : string -> t
val to_list : t -> int list
val of_list : int list -> t
val of_list_with_length : int list -> int -> t
val of_int_s : int -> t
val to_int_s : t -> int
val of_int_us : int -> t
val to_int_us : t -> int
val unsafe_set : t -> int -> bool -> unit
val unsafe_get : t -> int -> bool
end
module Version : sig
val version : string
val date : string
end
module Util : sig
TODO: functor:ocamlgraph.1.8.5/ocamlgraph/Graph.Util.OTProductTODO: functor:ocamlgraph.1.8.5/ocamlgraph/Graph.Util.HTProductTODO: functor:ocamlgraph.1.8.5/ocamlgraph/Graph.Util.CMPProductTODO: functor:ocamlgraph.1.8.5/ocamlgraph/Graph.Util.DataV
end
module Blocks : sig
val first_value_for_cpt_vertex : int
val max_cpt : int -> int -> int
val after_unserialization : int -> unit
module type HM = sig
Common signature to an imperative/persistent association table
type 'a return
type 'a t
type key
val create : ?size:int -> unit -> 'a t
val create_from : 'a t -> 'a t
val empty : 'a return
val clear : 'a t -> unit
val is_empty : 'a t -> bool
val add : key -> 'a -> 'a t -> 'a t
val remove : key -> 'a t -> 'a t
val mem : key -> 'a t -> bool
val find : key -> 'a t -> 'a
val find_and_raise : key -> 'a t -> string -> 'a
find_and_raise k t s is equivalent to find k t but
raises Invalid_argument s when find k t raises Not_found
val iter : key -> 'a -> unit -> 'a t -> unit
val map : key -> 'a -> (key * 'a) -> 'a t -> 'a t
val fold : key -> 'a -> 'b -> 'b -> 'a t -> 'b -> 'b
val copy : 'a t -> 'a t
end
end
module Persistent : sig
module type S = sig
Signature of persistent graphs.
TODO: functor:ocamlgraph.1.8.5/ocamlgraph/Graph.Persistent.ConcreteTODO: functor:ocamlgraph.1.8.5/ocamlgraph/Graph.Persistent.AbstractTODO: functor:ocamlgraph.1.8.5/ocamlgraph/Graph.Persistent.ConcreteLabeledTODO: functor:ocamlgraph.1.8.5/ocamlgraph/Graph.Persistent.AbstractLabeled
end
module Digraph : sig
Persistent Directed Graphs.
TODO: functor:ocamlgraph.1.8.5/ocamlgraph/Graph.Persistent.Digraph.ConcreteTODO: functor:ocamlgraph.1.8.5/ocamlgraph/Graph.Persistent.Digraph.AbstractTODO: functor:ocamlgraph.1.8.5/ocamlgraph/Graph.Persistent.Digraph.ConcreteLabeledTODO: functor:ocamlgraph.1.8.5/ocamlgraph/Graph.Persistent.Digraph.AbstractLabeledTODO: functor:ocamlgraph.1.8.5/ocamlgraph/Graph.Persistent.Digraph.ConcreteBidirectionalTODO: functor:ocamlgraph.1.8.5/ocamlgraph/Graph.Persistent.Digraph.ConcreteBidirectionalLabeled
end
module Graph : S
Persistent Undirected Graphs.
end
module Imperative : sig
module type S = sig
Signature of imperative graphs.
TODO: functor:ocamlgraph.1.8.5/ocamlgraph/Graph.Imperative.ConcreteTODO: functor:ocamlgraph.1.8.5/ocamlgraph/Graph.Imperative.AbstractTODO: functor:ocamlgraph.1.8.5/ocamlgraph/Graph.Imperative.ConcreteLabeledTODO: functor:ocamlgraph.1.8.5/ocamlgraph/Graph.Imperative.AbstractLabeled
end
module Digraph : sig
Imperative Directed Graphs.
TODO: functor:ocamlgraph.1.8.5/ocamlgraph/Graph.Imperative.Digraph.ConcreteTODO: functor:ocamlgraph.1.8.5/ocamlgraph/Graph.Imperative.Digraph.AbstractTODO: functor:ocamlgraph.1.8.5/ocamlgraph/Graph.Imperative.Digraph.ConcreteLabeledTODO: functor:ocamlgraph.1.8.5/ocamlgraph/Graph.Imperative.Digraph.AbstractLabeledTODO: functor:ocamlgraph.1.8.5/ocamlgraph/Graph.Imperative.Digraph.ConcreteBidirectionalTODO: functor:ocamlgraph.1.8.5/ocamlgraph/Graph.Imperative.Digraph.ConcreteBidirectionalLabeled
end
module Graph : S
Imperative Undirected Graphs.
module Matrix : sig
Imperative graphs implemented as adjacency matrices.
module type S = sig
type t
Abstract type of graphs
module V : sig
Vertices have type
V.t and are labeled with type V.label
(note that an implementation may identify the vertex with its
label)
type t = int
val compare : t -> t -> int
val hash : t -> int
val equal : t -> t -> bool
type label = int
val create : label -> t
val label : t -> label
end
type vertex = V.t
module E : sig
Edges have type
E.t and are labeled with type E.label.
src (resp. dst) returns the origin (resp. the destination) of a
given edge.
type t = (int * int)
val compare : t -> t -> int
type vertex = vertex
val src : t -> vertex
Edge origin.
val dst : t -> vertex
Edge destination.
type label
val create : vertex -> label -> vertex -> t
create v1 l v2 creates an edge from v1 to v2 with label l
val label : t -> label
Get the label of an edge.
end
type edge = E.t
val is_directed : bool
Is this an implementation of directed graphs?
val is_empty : t -> bool
val nb_vertex : t -> int
val nb_edges : t -> int
val out_degree : t -> vertex -> int
out_degree g v returns the out-degree of v in g.
Raises
Invalid_argument if v is not in g.
val in_degree : t -> vertex -> int
in_degree g v returns the in-degree of v in g.
Raises
Invalid_argument if v is not in g.
val mem_vertex : t -> vertex -> bool
val mem_edge : t -> vertex -> vertex -> bool
val mem_edge_e : t -> edge -> bool
val find_edge : t -> vertex -> vertex -> edge
find_edge g v1 v2 returns the edge from v1 to v2 if it exists.
Unspecified behaviour if g has several edges from v1 to v2.
Raises
Not_found if no such edge exists.
val find_all_edges : t -> vertex -> vertex -> edge list
val succ : t -> vertex -> vertex list
succ g v returns the successors of v in g.
Raises
Invalid_argument if v is not in g.
val pred : t -> vertex -> vertex list
pred g v returns the predecessors of v in g.
Raises
Invalid_argument if v is not in g.
val succ_e : t -> vertex -> edge list
succ_e g v returns the edges going from v in g.
Raises
Invalid_argument if v is not in g.
val pred_e : t -> vertex -> edge list
pred_e g v returns the edges going to v in g.
Raises
Invalid_argument if v is not in g.
val iter_vertex : vertex -> unit -> t -> unit
Iter on all vertices of a graph.
val fold_vertex : vertex -> 'a -> 'a -> t -> 'a -> 'a
Fold on all vertices of a graph.
val iter_edges : vertex -> vertex -> unit -> t -> unit
Iter on all edges of a graph. Edge label is ignored.
val fold_edges : vertex -> vertex -> 'a -> 'a -> t -> 'a -> 'a
Fold on all edges of a graph. Edge label is ignored.
val iter_edges_e : edge -> unit -> t -> unit
Iter on all edges of a graph.
val fold_edges_e : edge -> 'a -> 'a -> t -> 'a -> 'a
Fold on all edges of a graph.
val map_vertex : vertex -> vertex -> t -> t
Map on all vertices of a graph.
val iter_succ : vertex -> unit -> t -> vertex -> unit
val iter_pred : vertex -> unit -> t -> vertex -> unit
val fold_succ : vertex -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val fold_pred : vertex -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val iter_succ_e : edge -> unit -> t -> vertex -> unit
val fold_succ_e : edge -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val iter_pred_e : edge -> unit -> t -> vertex -> unit
val fold_pred_e : edge -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val create : ?size:int -> unit -> t
create () returns 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
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 -> vertex -> unit
add_vertex g v adds the vertex v to the graph g.
Do nothing if v is already in g.
val remove_vertex : t -> vertex -> unit
Time complexity for ocamlgraph implementations: O(|V|*ln(D)) for unlabeled graphs and O(|V|*D) for labeled graphs. D is the maximal degree of the graph.
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.Time complexity for ocamlgraph implementations: O(|V|*ln(D)) for unlabeled graphs and O(|V|*D) for labeled graphs. D is the maximal degree of the graph.
val add_edge : t -> vertex -> vertex -> 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 -> edge -> 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 -> vertex -> vertex -> unit
remove_edge g v1 v2 removes the edge going from v1 to v2 from the
graph g. If the graph is labelled, all the edges going from v1 to
v2 are removed from g.
Do nothing if this edge is not in g.
Raises
Invalid_argument if v1 or v2 are not in g.
val remove_edge_e : t -> edge -> unit
remove_edge_e g e removes the edge e from the graph g.
Do nothing if e is not in g.
Raises
Invalid_argument if E.src e or E.dst e are not in g.
val make : int -> t
Creation. graphs are not resizeable: size is given at creation time.
Thus
make must be used instead of create.
end
module Digraph : S
Imperative Directed Graphs implemented with adjacency matrices.
module Graph : S
Imperative Undirected Graphs implemented with adjacency matrices.
end
end
module Delaunay : sig
module type CCC = sig
Delaunay triangulation is available for any CCC system in the sense
of Knuth's ``Axioms and Hulls''
type point
val ccw : point -> point -> point -> bool
The counterclockwise relation
ccw p q r states that the
circle through points (p,q,r) is traversed counterclockwise
when we encounter the points in cyclic order p,q,r,p,... *
val in_circle : point -> point -> point -> point -> bool
The relation
in_circle p q r s states that s lies
inside the circle (p,q,r) if ccw p q r is true, or outside that
circle if ccw p q r is false.
end
module type Triangulation = sig
The result of triangulation is an abstract value of type
triangulation.
Then one can iterate over all edges of the triangulation.
module S : CCC
type triangulation
val triangulate : S.point array -> triangulation
triangulate a computes the Delaunay triangulation of a set of
points, given as an array a. If N is the number of points
(that is Array.length a), then the running time is $O(N \log N)$
on the average and $O(N^2)$ on the worst-case. The space used is
always $O(N)$.
val iter : S.point -> S.point -> unit -> triangulation -> unit
iter f t iterates over all edges of the triangulation t.
f u v is called once for each undirected edge (u,v).
val fold : S.point -> S.point -> 'a -> 'a -> triangulation -> 'a -> 'a
val iter_triangles : S.point -> S.point -> S.point -> unit -> triangulation -> unit
end
module IntPoints : sig
Points with integer coordinates
type point = (int * int)
val ccw : point -> point -> point -> bool
The counterclockwise relation
ccw p q r states that the
circle through points (p,q,r) is traversed counterclockwise
when we encounter the points in cyclic order p,q,r,p,... *
val in_circle : point -> point -> point -> point -> bool
The relation
in_circle p q r s states that s lies
inside the circle (p,q,r) if ccw p q r is true, or outside that
circle if ccw p q r is false.
end
module Int : sig
Delaunay triangulation with integer coordinates
module S : sig
Points with integer coordinates
type point = (int * int)
val ccw : point -> point -> point -> bool
The counterclockwise relation
ccw p q r states that the
circle through points (p,q,r) is traversed counterclockwise
when we encounter the points in cyclic order p,q,r,p,... *
val in_circle : point -> point -> point -> point -> bool
The relation
in_circle p q r s states that s lies
inside the circle (p,q,r) if ccw p q r is true, or outside that
circle if ccw p q r is false.
end
type triangulation
val triangulate : S.point array -> triangulation
triangulate a computes the Delaunay triangulation of a set of
points, given as an array a. If N is the number of points
(that is Array.length a), then the running time is $O(N \log N)$
on the average and $O(N^2)$ on the worst-case. The space used is
always $O(N)$.
val iter : S.point -> S.point -> unit -> triangulation -> unit
iter f t iterates over all edges of the triangulation t.
f u v is called once for each undirected edge (u,v).
val fold : S.point -> S.point -> 'a -> 'a -> triangulation -> 'a -> 'a
val iter_triangles : S.point -> S.point -> S.point -> unit -> triangulation -> unit
end
module FloatPoints : sig
Points with floating point coordinates
type point = (float * float)
val ccw : point -> point -> point -> bool
The counterclockwise relation
ccw p q r states that the
circle through points (p,q,r) is traversed counterclockwise
when we encounter the points in cyclic order p,q,r,p,... *
val in_circle : point -> point -> point -> point -> bool
The relation
in_circle p q r s states that s lies
inside the circle (p,q,r) if ccw p q r is true, or outside that
circle if ccw p q r is false.
end
module Float : sig
Delaunay triangulation with floating point coordinates
module S : sig
Points with floating point coordinates
type point = (float * float)
val ccw : point -> point -> point -> bool
The counterclockwise relation
ccw p q r states that the
circle through points (p,q,r) is traversed counterclockwise
when we encounter the points in cyclic order p,q,r,p,... *
val in_circle : point -> point -> point -> point -> bool
The relation
in_circle p q r s states that s lies
inside the circle (p,q,r) if ccw p q r is true, or outside that
circle if ccw p q r is false.
end
type triangulation
val triangulate : S.point array -> triangulation
triangulate a computes the Delaunay triangulation of a set of
points, given as an array a. If N is the number of points
(that is Array.length a), then the running time is $O(N \log N)$
on the average and $O(N^2)$ on the worst-case. The space used is
always $O(N)$.
val iter : S.point -> S.point -> unit -> triangulation -> unit
iter f t iterates over all edges of the triangulation t.
f u v is called once for each undirected edge (u,v).
val fold : S.point -> S.point -> 'a -> 'a -> triangulation -> 'a -> 'a
val iter_triangles : S.point -> S.point -> S.point -> unit -> triangulation -> unit
end
end
module Builder : sig
module type S = sig
module G : Sig.G
val empty : unit -> G.t
val copy : G.t -> G.t
val add_vertex : G.t -> G.V.t -> G.t
val add_edge : G.t -> G.V.t -> G.V.t -> G.t
val add_edge_e : G.t -> G.E.t -> G.t
val remove_vertex : G.t -> G.V.t -> G.t
val remove_edge : G.t -> G.V.t -> G.V.t -> G.t
val remove_edge_e : G.t -> G.E.t -> G.t
end
module type INT = sig
module G : sig
type t
Abstract type of graphs
module V : sig
Vertices have type
V.t and are labeled with type V.label
(note that an implementation may identify the vertex with its
label)
type t
val compare : t -> t -> int
val hash : t -> int
val equal : t -> t -> bool
type label = int
val create : label -> t
val label : t -> label
end
type vertex = V.t
module E : sig
Edges have type
E.t and are labeled with type E.label.
src (resp. dst) returns the origin (resp. the destination) of a
given edge.
type t
val compare : t -> t -> int
type vertex = vertex
val src : t -> vertex
Edge origin.
val dst : t -> vertex
Edge destination.
type label
val create : vertex -> label -> vertex -> t
create v1 l v2 creates an edge from v1 to v2 with label l
val label : t -> label
Get the label of an edge.
end
type edge = E.t
val is_directed : bool
Is this an implementation of directed graphs?
val is_empty : t -> bool
val nb_vertex : t -> int
val nb_edges : t -> int
val out_degree : t -> vertex -> int
out_degree g v returns the out-degree of v in g.
Raises
Invalid_argument if v is not in g.
val in_degree : t -> vertex -> int
in_degree g v returns the in-degree of v in g.
Raises
Invalid_argument if v is not in g.
val mem_vertex : t -> vertex -> bool
val mem_edge : t -> vertex -> vertex -> bool
val mem_edge_e : t -> edge -> bool
val find_edge : t -> vertex -> vertex -> edge
find_edge g v1 v2 returns the edge from v1 to v2 if it exists.
Unspecified behaviour if g has several edges from v1 to v2.
Raises
Not_found if no such edge exists.
val find_all_edges : t -> vertex -> vertex -> edge list
val succ : t -> vertex -> vertex list
succ g v returns the successors of v in g.
Raises
Invalid_argument if v is not in g.
val pred : t -> vertex -> vertex list
pred g v returns the predecessors of v in g.
Raises
Invalid_argument if v is not in g.
val succ_e : t -> vertex -> edge list
succ_e g v returns the edges going from v in g.
Raises
Invalid_argument if v is not in g.
val pred_e : t -> vertex -> edge list
pred_e g v returns the edges going to v in g.
Raises
Invalid_argument if v is not in g.
val iter_vertex : vertex -> unit -> t -> unit
Iter on all vertices of a graph.
val fold_vertex : vertex -> 'a -> 'a -> t -> 'a -> 'a
Fold on all vertices of a graph.
val iter_edges : vertex -> vertex -> unit -> t -> unit
Iter on all edges of a graph. Edge label is ignored.
val fold_edges : vertex -> vertex -> 'a -> 'a -> t -> 'a -> 'a
Fold on all edges of a graph. Edge label is ignored.
val iter_edges_e : edge -> unit -> t -> unit
Iter on all edges of a graph.
val fold_edges_e : edge -> 'a -> 'a -> t -> 'a -> 'a
Fold on all edges of a graph.
val map_vertex : vertex -> vertex -> t -> t
Map on all vertices of a graph.
val iter_succ : vertex -> unit -> t -> vertex -> unit
val iter_pred : vertex -> unit -> t -> vertex -> unit
val fold_succ : vertex -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val fold_pred : vertex -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val iter_succ_e : edge -> unit -> t -> vertex -> unit
val fold_succ_e : edge -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val iter_pred_e : edge -> unit -> t -> vertex -> unit
val fold_pred_e : edge -> 'a -> 'a -> t -> vertex -> 'a -> 'a
end
val empty : unit -> G.t
val copy : G.t -> G.t
val add_vertex : G.t -> G.V.t -> G.t
val add_edge : G.t -> G.V.t -> G.V.t -> G.t
val add_edge_e : G.t -> G.E.t -> G.t
val remove_vertex : G.t -> G.V.t -> G.t
val remove_edge : G.t -> G.V.t -> G.V.t -> G.t
val remove_edge_e : G.t -> G.E.t -> G.t
end
end
module Classic : sig
module type S = sig
type graph
val divisors : int -> graph
divisors n builds the graph of divisors.
Vertices are integers from 2 to n. i is connected to j if
and only if i divides j.
Raises
Invalid_argument is n < 2.
val de_bruijn : int -> graph
de_bruijn n builds the de Bruijn graph of order n.
Vertices are bit sequences of length n (encoded as their
interpretation as binary integers). The sequence xw is connected
to the sequence wy for any bits x and y and any bit sequence
w of length n-1.
Raises
Invalid_argument is n < 1 or n > Sys.word_size-1.
val vertex_only : int -> graph
vertex_only n builds a graph with n vertices and no edge.
val full : ?self:bool -> int -> graph
full n builds a graph with n vertices and all possible edges.
The optional argument self indicates if loop edges should be added
(default value is true).
end
end
module Rand : sig
module type S = sig
type graph
type vertex
type edge_label
val graph : ?loops:bool -> v:int -> e:int -> unit -> graph
graph v e generates a random graph with exactly v vertices
and e edges. Vertices are labeled with 0 ... v-1.
The boolean loops indicates whether loops are allowed;
default value is no loop (false).
Raises
Invalid_argument if e exceeds the maximal number of edges.
val labeled : vertex -> vertex -> edge_label -> ?loops:bool -> v:int -> e:int -> unit -> graph
labeled f is similar to graph except that edges are labeled
using function f.
Raises
Invalid_argument if there are too many edges.
val random_few_edges : loops:bool -> v:int -> e:int -> graph
val random_many_edges : loops:bool -> v:int -> e:int -> graph
val gnp : ?loops:bool -> v:int -> prob:float -> unit -> graph
random graph using the G(n,p) model.
gnp v prob generates a random graph with exactly v vertices
and where each edge is selected with probability prob
val gnp_labeled : vertex -> vertex -> edge_label -> ?loops:bool -> v:int -> prob:float -> unit -> graph
gnp_labeled add_edge v e is similar to gnp except that edges
are labeled using function f.
end
module Planar : sig
module type S = sig
type graph
val graph : ?loops:bool -> xrange:(int * int) -> yrange:(int * int) -> prob:float -> int -> graph
graph xrange yrange prob v
generates a random planar graph with exactly v vertices.
Vertices are labeled with integer coordinates, randomly distributed
according to xrange and yrange.
Edges are built as follows: the full Delaunay triangulation is
constructed and then each edge is discarded with probabiblity prob
(which should lie in 0..1). In particular prob = 0.0 gives the
full triangulation.
Edges are labeled with the (rounded) Euclidean distance between
the two vertices.
The boolean loops indicates whether loops are allowed;
default value is no loop (false).
end
end
end
module Oper : sig
module type S = sig
type g
val transitive_closure : ?reflexive:bool -> g -> g
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 -> g -> g
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 -> g -> g
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 -> g -> g
replace_by_transitive_reduction ?reflexive g replaces g by its
transitive reduction. Meaningless for persistent implementations
(then acts as transitive_reduction).
val mirror : g -> g
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 g.
Note: Vertices are shared between g and mirror g; you may need to
make a copy of g before using mirror
val complement : g -> g
complement g returns 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 : g -> g -> g
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 : g -> g -> g
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.
end
end
module Components : sig
module type G = sig
Minimal graph signature required by Make.
Sub-signature of Sig.G.
type t
module V : Sig.COMPARABLE
val iter_vertex : V.t -> unit -> t -> unit
val iter_succ : V.t -> unit -> t -> V.t -> unit
end
end
module Path : sig
module type G = sig
Minimal graph signature for Dijkstra's algorithm.
Sub-signature of Sig.G.
type t
module V : Sig.COMPARABLE
module E : sig
type t
type label
val label : t -> label
val src : t -> V.t
val dst : t -> V.t
end
val iter_vertex : V.t -> unit -> t -> unit
val iter_succ : V.t -> unit -> t -> V.t -> unit
val iter_succ_e : E.t -> unit -> t -> V.t -> unit
val fold_edges_e : E.t -> 'a -> 'a -> t -> 'a -> 'a
val nb_vertex : t -> int
end
module type WEIGHT = sig
Signature for edges' weights.
type label
Type for labels of graph edges.
type t
Type of edges' weights.
val weight : label -> t
Get the weight of an edge.
val compare : t -> t -> int
Weights must be ordered.
val add : t -> t -> t
Addition of weights.
val zero : t
Neutral element for add.
end
end
module Nonnegative : sig
module type WEIGHT = sig
Signature for edges' weights.
type label
Type for labels of graph edges.
type t
Type of edges' weights.
val weight : label -> t
Get the weight of an edge.
val compare : t -> t -> int
Weights must be ordered.
val add : t -> t -> t
Addition of weights.
val zero : t
Neutral element for add.
end
end
module Traverse : sig
module type G = sig
Minimal graph signature for Dfs and Bfs.
Sub-signature of Sig.G.
val is_directed : bool
type t
module V : Sig.COMPARABLE
val iter_vertex : V.t -> unit -> t -> unit
val fold_vertex : V.t -> 'a -> 'a -> t -> 'a -> 'a
val iter_succ : V.t -> unit -> t -> V.t -> unit
val fold_succ : V.t -> 'a -> 'a -> t -> V.t -> 'a -> 'a
end
module type GM = sig
Minimal graph signature for graph traversal with marking.
Sub-signature of Sig.IM.
type t
module V : sig
type t
end
val iter_vertex : V.t -> unit -> t -> unit
val iter_succ : V.t -> unit -> t -> V.t -> unit
module Mark : sig
val clear : t -> unit
val get : V.t -> int
val set : V.t -> int -> unit
end
end
end
module Coloring : sig
module type G = sig
Minimal graph signature for Make.
Sub-signature of Sig.G.
val is_directed : bool
type t
val nb_vertex : t -> int
module V : Sig.COMPARABLE
val out_degree : t -> V.t -> int
val iter_vertex : V.t -> unit -> t -> unit
val fold_vertex : V.t -> 'a -> 'a -> t -> 'a -> 'a
val iter_succ : V.t -> unit -> t -> V.t -> unit
val fold_succ : V.t -> 'a -> 'a -> t -> V.t -> 'a -> 'a
end
module type GM = sig
Minimal graph signature for Mark.
Sub-signature of Sig.IM.
val is_directed : bool
type t
val nb_vertex : t -> int
module V : Sig.COMPARABLE
val out_degree : t -> V.t -> int
val iter_vertex : V.t -> unit -> t -> unit
val fold_vertex : V.t -> 'a -> 'a -> t -> 'a -> 'a
val iter_succ : V.t -> unit -> t -> V.t -> unit
val fold_succ : V.t -> 'a -> 'a -> t -> V.t -> 'a -> 'a
module Mark : sig
val get : V.t -> int
val set : V.t -> int -> unit
end
end
end
module Topological : sig
module type G = sig
Minimal graph signature to provide.
Sub-signature of Sig.G.
type t
module V : Sig.COMPARABLE
val iter_vertex : V.t -> unit -> t -> unit
val iter_succ : V.t -> unit -> t -> V.t -> unit
end
end
module Kruskal : sig
module type G = sig
Minimal graph signature for Kruskal.
Sub-signature of Sig.G.
type t
module V : Sig.COMPARABLE
module E : sig
type t
type label
val label : t -> label
val dst : t -> V.t
val src : t -> V.t
end
val fold_vertex : V.t -> 'a -> 'a -> t -> 'a -> 'a
val iter_edges_e : E.t -> unit -> t -> unit
end
module type UNIONFIND = sig
Signature of union-find.
type elt
type t
val init : elt list -> t
val find : elt -> t -> elt
val union : elt -> elt -> t -> unit
end
end
module Flow : sig
module type FLOW = sig
Signature for edges' flow.
type t
Type of edges.
type label
Type of labels on edges.
val max_capacity : label -> t
val min_capacity : label -> t
val flow : label -> t
val add : t -> t -> t
val sub : t -> t -> t
val zero : t
val compare : t -> t -> int
end
module type G_GOLDBERG = sig
Minimal graph signature for Goldberg.
Sub-signature of Sig.G.
type t
module V : Sig.COMPARABLE
module E : sig
type t
type label
val src : t -> V.t
val dst : t -> V.t
val label : t -> label
end
val nb_vertex : t -> int
val iter_vertex : V.t -> unit -> t -> unit
val iter_edges_e : E.t -> unit -> t -> unit
val fold_succ_e : E.t -> 'a -> 'a -> t -> V.t -> 'a -> 'a
val fold_pred_e : E.t -> 'a -> 'a -> t -> V.t -> 'a -> 'a
end
module type G_FORD_FULKERSON = sig
Minimal digraph signature for Ford-Fulkerson.
Sub-signature of Sig.G.
type t
module V : Sig.HASHABLE
module E : sig
type t
type label
val src : t -> V.t
val dst : t -> V.t
val label : t -> label
end
val iter_succ_e : E.t -> unit -> t -> V.t -> unit
val iter_pred_e : E.t -> unit -> t -> V.t -> unit
end
end
module Prim : sig
module type WEIGHT = sig
type label
type t
val weight : label -> t
val compare : t -> t -> int
val add : t -> t -> t
val zero : t
end
module type G = sig
type t
module V : Sig.COMPARABLE
module E : sig
type t
type label
val label : t -> label
val dst : t -> V.t
val src : t -> V.t
val compare : t -> t -> int
end
val iter_vertex : V.t -> unit -> t -> unit
val iter_edges_e : E.t -> unit -> t -> unit
val iter_succ_e : E.t -> unit -> t -> V.t -> unit
end
end
module Dominator : sig
exception Unreachable
module type G = sig
type t
module V : Sig.COMPARABLE
val pred : t -> V.t -> V.t list
val succ : t -> V.t -> V.t list
val fold_vertex : V.t -> 'a -> 'a -> t -> 'a -> 'a
val iter_vertex : V.t -> unit -> t -> unit
val nb_vertex : t -> int
val create : ?size:int -> unit -> t
val add_edge : t -> V.t -> V.t -> unit
end
end
module Graphviz : sig
type color = int
type color_with_transparency = int32
The two least significant bytes encode the transparency information;
the six most signification are the standard RGB color
val color_to_color_with_transparency : color -> color_with_transparency
type arrow_style = TODO: a
module type ATTRIBUTES = sig
The
ATTRIBUTES module type defines the interface for the engines.
type graph
Attributes of graphs.
type vertex
Attributes of vertices.
type edge
Attributes of edges.
type subgraph = {
sg_name : string; (* Box name. *)
sg_attributes : vertex list; (* Box attributes. *)
sg_parent : string option; (* Nested subgraphs. *)
}
Attributes of (optional) boxes around vertices.
end
module CommonAttributes : sig
The
CommonAttributes module defines attributes for graphs, vertices and
edges that are available in the two engines, dot and neato.
type graph = TODO: a
Attributes of graphs.
type vertex = TODO: a
Attributes of vertices.
type edge = TODO: a
Attributes of edges.
end
module DotAttributes : sig
DotAttributes extends CommonAttributes and implements ATTRIBUTES.
type graph = TODO: a
Attributes of graphs. They include all common graph attributes and
several specific ones. All attributes described in the "dot User's
Manual, February 4, 2002" are handled, excepted: clusterank, color,
compound, labeljust, labelloc, ordering, rank, remincross, rotate,
searchsize and style.
type vertex = TODO: a
Attributes of nodes. They include all common node attributes and
several specific ones. All attributes described in the "dot User's
Manual, February 4, 2002" are handled, excepted: bottomlabel, group,
shapefile and toplabel.
type edge = TODO: a
Attributes of edges. They include all common edge attributes and
several specific ones. All attributes described in the "dot User's
Manual, February 4, 2002" are handled, excepted: lhead and ltail.
type subgraph = {
sg_name : string;
sg_attributes : vertex list;
sg_parent : string option;
}
Subgraphs have a name and some vertices.
end
module type GraphWithDotAttrs = sig
Graph module with dot attributes
type t
Abstract type of graphs
module V : Sig.VERTEX
Vertices have type
V.t and are labeled with type V.label
(note that an implementation may identify the vertex with its
label)
type vertex = V.t
module E : sig
Edges have type
E.t and are labeled with type E.label.
src (resp. dst) returns the origin (resp. the destination) of a
given edge.
type t
val compare : t -> t -> int
type vertex = vertex
val src : t -> vertex
Edge origin.
val dst : t -> vertex
Edge destination.
type label
val create : vertex -> label -> vertex -> t
create v1 l v2 creates an edge from v1 to v2 with label l
val label : t -> label
Get the label of an edge.
end
type edge = E.t
val is_directed : bool
Is this an implementation of directed graphs?
val is_empty : t -> bool
val nb_vertex : t -> int
val nb_edges : t -> int
val out_degree : t -> vertex -> int
out_degree g v returns the out-degree of v in g.
Raises
Invalid_argument if v is not in g.
val in_degree : t -> vertex -> int
in_degree g v returns the in-degree of v in g.
Raises
Invalid_argument if v is not in g.
val mem_vertex : t -> vertex -> bool
val mem_edge : t -> vertex -> vertex -> bool
val mem_edge_e : t -> edge -> bool
val find_edge : t -> vertex -> vertex -> edge
find_edge g v1 v2 returns the edge from v1 to v2 if it exists.
Unspecified behaviour if g has several edges from v1 to v2.
Raises
Not_found if no such edge exists.
val find_all_edges : t -> vertex -> vertex -> edge list
val succ : t -> vertex -> vertex list
succ g v returns the successors of v in g.
Raises
Invalid_argument if v is not in g.
val pred : t -> vertex -> vertex list
pred g v returns the predecessors of v in g.
Raises
Invalid_argument if v is not in g.
val succ_e : t -> vertex -> edge list
succ_e g v returns the edges going from v in g.
Raises
Invalid_argument if v is not in g.
val pred_e : t -> vertex -> edge list
pred_e g v returns the edges going to v in g.
Raises
Invalid_argument if v is not in g.
val iter_vertex : vertex -> unit -> t -> unit
Iter on all vertices of a graph.
val fold_vertex : vertex -> 'a -> 'a -> t -> 'a -> 'a
Fold on all vertices of a graph.
val iter_edges : vertex -> vertex -> unit -> t -> unit
Iter on all edges of a graph. Edge label is ignored.
val fold_edges : vertex -> vertex -> 'a -> 'a -> t -> 'a -> 'a
Fold on all edges of a graph. Edge label is ignored.
val iter_edges_e : edge -> unit -> t -> unit
Iter on all edges of a graph.
val fold_edges_e : edge -> 'a -> 'a -> t -> 'a -> 'a
Fold on all edges of a graph.
val map_vertex : vertex -> vertex -> t -> t
Map on all vertices of a graph.
val iter_succ : vertex -> unit -> t -> vertex -> unit
val iter_pred : vertex -> unit -> t -> vertex -> unit
val fold_succ : vertex -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val fold_pred : vertex -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val iter_succ_e : edge -> unit -> t -> vertex -> unit
val fold_succ_e : edge -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val iter_pred_e : edge -> unit -> t -> vertex -> unit
val fold_pred_e : edge -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val graph_attributes : t -> DotAttributes.graph list
val default_vertex_attributes : t -> DotAttributes.vertex list
val vertex_name : V.t -> string
val vertex_attributes : V.t -> DotAttributes.vertex list
val default_edge_attributes : t -> DotAttributes.edge list
val edge_attributes : E.t -> DotAttributes.edge list
val get_subgraph : V.t -> DotAttributes.subgraph option
The box (if exists) which the vertex belongs to. Boxes with same
names are not distinguished and so they should have the same
attributes.
end
module NeatoAttributes : sig
type graph = TODO: a
Attributes of graphs. They include all common graph attributes and
several specific ones. All attributes described in the "Neato User's
manual, April 10, 2002" are handled.
type vertex = TODO: a
Attributes of nodes. They include all common node attributes and
several specific ones. All attributes described in the "Neato User's
manual, April 10, 2002" are handled.
type edge = TODO: a
Attributes of edges. They include all common edge attributes and
several specific ones. All attributes described in the "Neato User's
manual, April 10, 2002" are handled.
type subgraph = {
sg_name : string;
sg_attributes : vertex list;
sg_parent : string option;
}
Subgraphs have a name and some vertices.
end
end
module Gml : sig
type value =
| Int of int
| Float of float
| String of string
| List of value_list
type value_list = (string * value) list
module type G = sig
Signature for graph required by Print.
Sub-signature of Sig.G.
module V : sig
type t
val hash : t -> int
val equal : t -> t -> bool
type label
val label : t -> label
end
module E : sig
type t
type label
val src : t -> V.t
val dst : t -> V.t
val label : t -> label
end
type t
val iter_vertex : V.t -> unit -> t -> unit
val iter_edges_e : E.t -> unit -> t -> unit
end
end
module Dot_lexer : sig
val keyword : string -> Dot_parser.token
end
module Pack : sig
module Digraph : Sig_pack.S
Directed imperative graphs with edges and vertices labeled with integer.
module Graph : Sig_pack.S
Undirected imperative graphs with edges and vertices labeled with
integer.
end
module Gmap : sig
module type V_SRC = sig
Signature for the source graph.
type t
module V : Sig.HASHABLE
val fold_vertex : V.t -> 'a -> 'a -> t -> 'a -> 'a
end
module type V_DST = sig
Signature for the destination graph.
type t
type vertex
val empty : unit -> t
val add_vertex : t -> vertex -> t
end
module type E_SRC = sig
Signature for the source graph.
type t
module E : Sig.ORDERED_TYPE
val fold_edges_e : E.t -> 'a -> 'a -> t -> 'a -> 'a
end
module type E_DST = sig
Signature for the destination graph.
type t
type edge
val empty : unit -> t
val add_edge_e : t -> edge -> t
end
end
module Minsep : sig
module type G = sig
Minimal signature for computing the minimal separators
type t
module V : Sig.COMPARABLE
val succ : t -> V.t -> V.t list
val iter_succ : V.t -> unit -> t -> V.t -> unit
val fold_succ : V.t -> 'a -> 'a -> t -> V.t -> 'a -> 'a
val iter_vertex : V.t -> unit -> t -> unit
val fold_vertex : V.t -> 'a -> 'a -> t -> 'a -> 'a
end
module type MINSEP = sig
module G : G
Implementation of a graph
module Vertex_Set : sig
Implementation of a set of vertex
type elt = G.V.t
type t
val empty : t
val is_empty : t -> bool
val mem : elt -> t -> bool
val add : elt -> t -> t
val singleton : elt -> t
val remove : elt -> t -> t
val union : t -> t -> t
val inter : t -> t -> t
val diff : t -> t -> t
val compare : t -> t -> int
val equal : t -> t -> bool
val subset : t -> t -> bool
val iter : elt -> unit -> t -> unit
val fold : elt -> 'a -> 'a -> t -> 'a -> 'a
val for_all : elt -> bool -> t -> bool
val exists : elt -> bool -> t -> bool
val filter : elt -> bool -> t -> t
val partition : elt -> bool -> t -> (t * t)
val cardinal : t -> int
val elements : t -> elt list
val min_elt : t -> elt
val max_elt : t -> elt
val choose : t -> elt
val split : elt -> t -> (t * bool * t)
val find : elt -> t -> elt
val of_list : elt list -> t
end
module VSetset : sig
Implementation of a set of
Vertex_Set
type elt = Vertex_Set.t
type t
val empty : t
val is_empty : t -> bool
val mem : elt -> t -> bool
val add : elt -> t -> t
val singleton : elt -> t
val remove : elt -> t -> t
val union : t -> t -> t
val inter : t -> t -> t
val diff : t -> t -> t
val compare : t -> t -> int
val equal : t -> t -> bool
val subset : t -> t -> bool
val iter : elt -> unit -> t -> unit
val fold : elt -> 'a -> 'a -> t -> 'a -> 'a
val for_all : elt -> bool -> t -> bool
val exists : elt -> bool -> t -> bool
val filter : elt -> bool -> t -> t
val partition : elt -> bool -> t -> (t * t)
val cardinal : t -> int
val elements : t -> elt list
val min_elt : t -> elt
val max_elt : t -> elt
val choose : t -> elt
val split : elt -> t -> (t * bool * t)
val find : elt -> t -> elt
val of_list : elt list -> t
end
val allminsep : G.t -> Vertex_Set.t list
allminsep g computes the list of all minimal separators of g.
val list_of_allminsep : G.t -> G.V.t list list
Less efficient that
allminsep
val set_of_allminsep : G.t -> VSetset.t
Less efficient that
allminsep
end
end
module Cliquetree : sig
TODO: functor:ocamlgraph.1.8.5/ocamlgraph/Graph.Cliquetree.CliqueTree
end
module Mcs_m : sig
module MaximalCardinalitySearch : sig
TODO: functor:ocamlgraph.1.8.5/ocamlgraph/Graph.Mcs_m.MaximalCardinalitySearch.PTODO: functor:ocamlgraph.1.8.5/ocamlgraph/Graph.Mcs_m.MaximalCardinalitySearch.I
end
end
module Md : sig
TODO: functor:ocamlgraph.1.8.5/ocamlgraph/Graph.Md.PTODO: functor:ocamlgraph.1.8.5/ocamlgraph/Graph.Md.I
end
module Strat : sig
module type G = sig
Signature for graphs
type t
module V : Sig.ORDERED_TYPE
type vertex = V.t
val mem_vertex : t -> vertex -> bool
val succ : t -> vertex -> vertex list
val fold_vertex : vertex -> 'a -> 'a -> t -> 'a -> 'a
val fold_succ : vertex -> 'a -> 'a -> t -> vertex -> 'a -> 'a
end
module type PLAYER = sig
Signature for graph add-ons: an initial vertex, final vertices
and membership of vertices to either true or false,
i.e. first or second player
type t
type vertex
val get_initial : t -> vertex
val is_final : t -> vertex -> bool
val turn : t -> vertex -> bool
end
module type STRAT = sig
Signature for strategies: for a given state, the strategy tells
which state to go to
type t
type vertex
val empty : t
val add : t -> vertex -> vertex -> t
val next : t -> vertex -> vertex
Raises
Invalid_argument if vertex's image is not defined
end
end
module Fixpoint : sig
module type G = sig
Minimal graph signature for work list algorithm
type t
module V : Sig.COMPARABLE
module E : sig
type t
val dst : t -> V.t
val src : t -> V.t
end
val fold_vertex : V.t -> 'a -> 'a -> t -> 'a -> 'a
val succ_e : t -> V.t -> E.t list
val pred_e : t -> V.t -> E.t list
val succ : t -> V.t -> V.t list
val pred : t -> V.t -> V.t list
end
type direction =
| Forward
| Backward (* Type of an analysis *)
module type Analysis = sig
type data
information stored at each vertex
type edge
type of edges of the underlying graph
type vertex
type of vertices of the underlying graph
type g
type of the underlying graph
val direction : direction
the direction of the analysis
val join : data -> data -> data
operation how to join data when paths meet
val equal : data -> data -> bool
predicate to determine the fixpoint
val analyze : edge -> data -> data
the actual analysis of one edge; provided the edge and the incoming
data, it needs to compute the outgoing data
end
end
module Leaderlist : sig
module type G = sig
Minimal graph signature for leader list algorithm
type t
module V : Sig.COMPARABLE
val fold_vertex : V.t -> 'a -> 'a -> t -> 'a -> 'a
val succ : t -> V.t -> V.t list
val pred : t -> V.t -> V.t list
end
end
module Contraction : sig
module type G = sig
Minimal graph signature for edge contraction algorithm
type t
module V : Sig.COMPARABLE
type vertex = V.t
module E : sig
type t
val compare : t -> t -> int
type vertex = vertex
val src : t -> vertex
Edge origin.
val dst : t -> vertex
Edge destination.
type label
val create : vertex -> label -> vertex -> t
create v1 l v2 creates an edge from v1 to v2 with label l
val label : t -> label
Get the label of an edge.
end
type edge = E.t
val empty : t
val add_edge_e : t -> edge -> t
val fold_edges_e : edge -> 'a -> 'a -> t -> 'a -> 'a
val fold_vertex : vertex -> 'a -> 'a -> t -> 'a -> 'a
end
end
module Graphml : sig
module type G = sig
Graph information required by Graphml
type t
type vertex
module E : sig
type t
val src : t -> vertex
val dst : t -> vertex
end
val is_directed : bool
val iter_vertex : vertex -> unit -> t -> unit
val iter_edges_e : E.t -> unit -> t -> unit
end
end
module Merge : sig
module type S = sig
type graph
type vertex
type edge
type edge_label
val merge_vertex : graph -> vertex list -> graph
If no element of
vl belongs to g then merge_vertex g (v::vl) is the
graph g. Otherwise the collection of vertices of merge_vertex g
(v::vl) is the collection of vertices of g from which all the elements
of vl were removed and to which v was added. Any edge of merge_vertex
g (v::vl) is an edge of g whose source (destination) was changed to v
if it belongs to vl. The function merge_vertex always returns a graph
with a smaller collection of vertices and a smaller collection of edges
(in the weak sense). However the labels appearing in merge_vertex g
v::vl are exactly the ones appearing in g.
val merge_edges_e : ?src:vertex -> ?dst:vertex -> graph -> edge list -> graph
If no element of
el belongs to g then merge_edges_e g (e::el) is the
graph g. Otherwise the collection of vertices of merge_edges_e g
(e::el) is precisely the collection of vertices of g from which the
sources and the destinations of all the elements of el were removed and
to which the vertices v and w were added. If dst was provided then
v is src otherwise it is the source of e. If dst was provided then
w is y otherwise it is the destination of e. The collection of edges
of merge_edges_e g e::el is precisely the collection of edges of g
from which all the elements of el were removed and to which an edge from
v to w sharing the label of e was added; the edges of g being
understood up to the fact their source and destination were updated. Note
v=w if and only if the source of some element of el matches the
destination of some element of el (possibly the same).
val merge_edges_with_label : ?src:vertex -> ?dst:vertex -> ?label:edge_label -> graph -> edge_label -> graph
The graph
merge_edges_with_label ?src ?tgt ?label g l is the graph
merge_edges_e ?src ?dst g el with el being the list of all edges of
g carrying the label l. If the optional value label is provided then
the edge to which all the elements of el are identified carries the
label label. Otherwise it carries the label l. In particular
merge_edges_with_label ?src ?tgt ?label g l is the graph g if and only
if there is at most one edge of g carrying the label l.
val merge_isolabelled_edges : graph -> graph
The graph
merge_isolabelled_edges g is obtained from g by
identifying two vertices when they are the sources (destinations) of two
edges sharing the same label. Therefore two distinct edges of the
returned graph cannot carry the same label. In particular if all the
edges share the same label then the returned graph is either empty (if
g is so) or a single vertex (if g has no edge and at least one
vertex) or a single vertex and a single edge (if g has both a vertex
and an edge). A label is carried by some edge of
merge_isolabelled_edges g if and only if it is carried by some edge of
g.
val merge_ends : ?strict:bool -> ?specified_vertex:vertex -> graph -> graph
A vertex
v of g is called an end if every edge of g arriving to v
also starts from v. It is called a strict end if no edge of g arrives
to it. The graph merge_ends g is the graph merge_vertex vl where vl
is the list of (strict) ends of g. The vertex substituted to the ends
can be specified.
val merge_starts : ?strict:bool -> ?specified_vertex:vertex -> graph -> graph
A vertex
v of g is called a start if every edge of g starting from
v also arrives to v. It is called a strict start if no edge of g
starts from it. The graph merge_starts g is the graph merge_vertex vl
where vl is the list of (strict) starts of g. The vertex substituted
to the starts can be specified.
val merge_scc : ?loop_killer:bool -> ?specified_vertex:vertex list -> vertex -> graph -> graph
The vertex of every strongly connected component are identified. If the
option
loop_killer is set to true then all the edges between identified
vertices are removed. The option specified_vertex allows to choose the
vertex that replaces the elements of a strongly connected component.
end
end