Module OpamSolver
module Action : sig
type package = OpamTypes.package
type t = package OpamTypes.action
val compare : t -> t -> int
val hash : t -> int
val equal : t -> t -> bool
val to_string : t -> string
end
module ActionGraph : 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 = OpamTypes.package OpamTypes.action
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
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
.
type g = t
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.
module Topological : sig
val fold : V.t -> 'a -> 'a -> t -> 'a -> 'a
val iter : V.t -> unit -> t -> unit
end
module Parallel : sig
module G : sig
type t = t
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 = vertex
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
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 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_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 iter_vertex : V.t -> unit -> t -> unit
val iter_succ : V.t -> unit -> t -> V.t -> unit
val has_cycle : t -> bool
val scc_list : t -> V.t list list
val string_of_vertex : V.t -> string
end
val iter : int -> G.t -> pre:G.V.t -> unit -> child:G.V.t -> unit -> post:G.V.t -> unit -> unit
val iter_l : int -> G.vertex list -> pre:G.V.t -> unit -> child:G.V.t -> unit -> post:G.V.t -> unit -> unit
val map_reduce : int -> G.t -> map:G.V.t -> 'a -> merge:'a -> 'a -> 'a -> init:'a -> 'a
val map_reduce_l : int -> G.vertex list -> map:G.V.t -> 'a -> merge:'a -> 'a -> 'a -> init:'a -> 'a
val create : G.V.t list -> G.t
exception Cyclic of G.V.t list list
end
end
val empty_universe : OpamTypes.universe
val string_of_request : OpamTypes.atom OpamTypes.request -> string
Convert a request to a string
val stats : solution -> OpamTypes.stats
Compute statistics about a solution
val new_packages : solution -> OpamTypes.package_set
Return the new packages in the solution
val string_of_stats : OpamTypes.stats -> string
Pretty-printing of statistics
val solution_is_empty : solution -> bool
Is the solution empty ?
val delete_or_update : solution -> bool
Does the solution implies deleting or updating a package
val print_solution : messages:OpamTypes.package -> string list -> rewrite:OpamTypes.package -> OpamTypes.package -> solution -> unit
Display a solution
val cudf_versions_map : OpamTypes.universe -> OpamTypes.package_set -> int OpamPackage.Map.t
Computes an opam->cudf version map from a set of package
val resolve : ?verbose:bool -> OpamTypes.universe -> requested:OpamTypes.name_set -> orphans:OpamTypes.package_set -> OpamTypes.atom OpamTypes.request -> (solution, OpamCudf.conflict) OpamTypes.result
Given a description of packages, return a solution preserving the
consistency of the initial description.
val installable : OpamTypes.universe -> OpamTypes.package_set
Keep only the packages that are installable.
val dependencies : depopts:bool -> ?build:bool -> ?test:bool -> ?doc:bool -> installed:bool -> ?unavailable:bool -> OpamTypes.universe -> OpamTypes.package_set -> OpamTypes.package list
Return the topological sort of the transitive dependency closures
of a collection of packages.
val reverse_dependencies : depopts:bool -> ?build:bool -> ?test:bool -> ?doc:bool -> installed:bool -> ?unavailable:bool -> OpamTypes.universe -> OpamTypes.package_set -> OpamTypes.package list
Same as
dependencies
but for reverse dependencies