package opam-solver

You can search for identifiers within the package.

in-package search v0.2.0

On This Page

Parameters
Signature

Solver library for opam 2.5

Install

dune-project

Dependency

opam.ocaml.org Readme Edit opam file Versions (32)

Authors

Maintainers

O

opam-devel@lists.ocaml.org

Sources

2.5.0.tar.gz

md5=79d057547b7114e31334bc4f556bc541

sha512=707b652997bae086003c4164029ed40a68e9c465b4ce1731d0f8ccc0a496c5b6d9011e45bc2b6f73e56d316e54bce7c82becb83bd7de4fa53b0795ad7ae7032a

doc/opam-solver/OpamActionGraph/Make/index.html

Module `OpamActionGraph.Make`Source

Parameters

module A : ACTION

Signature

Sourcetype package = A.package

include OpamParallel.GRAPH with type V.t = package OpamTypes.action

include Graph.Sig.I
  with type E.label = OpamParallel.dependency_label
  with type V.t = package OpamTypes.action

An imperative graph is a graph.

include Graph.Sig.G
  with type E.label = OpamParallel.dependency_label
  with type V.t = package OpamTypes.action

Graph structure

Sourcetype t

Abstract type of graphs

module V : Graph.Sig.VERTEX with type t = package OpamTypes.action

Vertices have type V.t and are labeled with type V.label (note that an implementation may identify the vertex with its label)

Sourcetype vertex = V.t

module E : 
  Graph.Sig.EDGE
    with type vertex = vertex
    with type label = OpamParallel.dependency_label

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.

Sourcetype edge = E.t

Sourceval is_directed : bool

Is this an implementation of directed graphs?

Size functions

Sourceval is_empty : t -> bool

Sourceval nb_vertex : t -> int

Sourceval nb_edges : t -> int

Degree of a vertex

Sourceval 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.

Sourceval 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.

Membership functions

Sourceval mem_vertex : t -> vertex -> bool

Sourceval mem_edge : t -> vertex -> vertex -> bool

Sourceval mem_edge_e : t -> edge -> bool

Sourceval 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.

Sourceval find_all_edges : t -> vertex -> vertex -> edge list

find_all_edges g v1 v2 returns all the edges from v1 to v2.

since ocamlgraph 1.8

Successors and predecessors

You should better use iterators on successors/predecessors (see Section "Vertex iterators").

Sourceval succ : t -> vertex -> vertex list

succ g v returns the successors of v in g.

raises Invalid_argument
if v is not in g.

Sourceval pred : t -> vertex -> vertex list

pred g v returns the predecessors of v in g.

raises Invalid_argument
if v is not in g.

Labeled edges going from/to a vertex

Sourceval 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.

Sourceval 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.

Graph iterators

Sourceval iter_vertex : (vertex -> unit) -> t -> unit

Iter on all vertices of a graph.

Sourceval fold_vertex : (vertex -> 'a -> 'a) -> t -> 'a -> 'a

Fold on all vertices of a graph.

Sourceval iter_edges : (vertex -> vertex -> unit) -> t -> unit

Iter on all edges of a graph. Edge label is ignored.

Sourceval fold_edges : (vertex -> vertex -> 'a -> 'a) -> t -> 'a -> 'a

Fold on all edges of a graph. Edge label is ignored.

Sourceval iter_edges_e : (edge -> unit) -> t -> unit

Iter on all edges of a graph.

Sourceval fold_edges_e : (edge -> 'a -> 'a) -> t -> 'a -> 'a

Fold on all edges of a graph.

Sourceval map_vertex : (vertex -> vertex) -> t -> t

Map on all vertices of a graph.

The current implementation requires the supplied function to be injective. Said otherwise, map_vertex cannot be used to contract a graph by mapping several vertices to the same vertex. To contract a graph, use instead create, add_vertex, and add_edge.

Vertex iterators

Each iterator iterator f v g iters f to the successors/predecessors of v in the graph g and raises Invalid_argument if v is not in g. It is the same for functions fold_* which use an additional accumulator.

<b>Time complexity for ocamlgraph implementations:</b> operations on successors are in O(1) amortized for imperative graphs and in O(ln(|V|)) for persistent graphs while operations on predecessors are in O(max(|V|,|E|)) for imperative graphs and in O(max(|V|,|E|)*ln|V|) for persistent graphs.

iter/fold on all successors/predecessors of a vertex.

Sourceval iter_succ : (vertex -> unit) -> t -> vertex -> unit

Sourceval iter_pred : (vertex -> unit) -> t -> vertex -> unit

Sourceval fold_succ : (vertex -> 'a -> 'a) -> t -> vertex -> 'a -> 'a

Sourceval fold_pred : (vertex -> 'a -> 'a) -> t -> vertex -> 'a -> 'a

iter/fold on all edges going from/to a vertex.

Sourceval iter_succ_e : (edge -> unit) -> t -> vertex -> unit

Sourceval fold_succ_e : (edge -> 'a -> 'a) -> t -> vertex -> 'a -> 'a

Sourceval iter_pred_e : (edge -> unit) -> t -> vertex -> unit

Sourceval fold_pred_e : (edge -> 'a -> 'a) -> t -> vertex -> 'a -> 'a

Sourceval 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.

Sourceval clear : t -> unit

Remove all vertices and edges from the given graph.

since ocamlgraph 1.4

Sourceval copy : t -> t

copy g returns a copy of g. Vertices and edges (and eventually marks, see module Mark) are duplicated.

Sourceval 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.

Sourceval remove_vertex : t -> vertex -> 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.

<b>Time complexity for ocamlgraph implementations:</b> O(|V|*ln(D)) for unlabeled graphs and O(|V|*D) for labeled graphs. D is the maximal degree of the graph.

Sourceval 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.

Sourceval 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.

Sourceval 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.

Sourceval 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.

include Graph.Oper.S with type g = t

Sourcetype g = t

Sourceval 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).

Sourceval transitive_reduction : ?reflexive:bool -> g -> g

transitive_reduction ?reflexive g returns the transitive reduction of g (as a new graph). This is a subgraph of g with the same transitive closure as g. When g is acyclic, its transitive reduction contains as few edges as possible and is unique. Loops (i.e. edges from a vertex to itself) are removed only if reflexive is true (default is false). Note: Only meaningful for directed graphs.

Sourceval 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).

Sourceval 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

Sourceval 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.

Sourceval 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.

Sourceval 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.

Sourcemodule Topological : sig ... end

Sourcemodule Parallel : OpamParallel.SIG with type G.t = t and type G.V.t = vertex

Sourcemodule Dot : sig ... end

Sourceval transitive_closure : ?reflexive:bool -> t -> unit

Sourceval build : V.t list -> E.t list -> t

Sourceval compare : t -> t -> int

Sourceval to_json : t OpamJson.encoder

Sourceval of_json : t OpamJson.decoder

Sourceval reduce : t -> t

Reduces a graph of atomic or concrete actions (only removals, installs and builds) by turning removal+install to reinstalls or up/down-grades, best for display. Dependency ordering won't be as accurate though, as there is no proper ordering of (reinstall a, reinstall b) if b depends on a. The resulting graph contains at most one action per package name.

There is no guarantee however that the resulting graph is acyclic.

Source

val explicit : 
  ?noop_remove:(package -> bool) ->
  sources_needed:(package -> package list) ->
  t ->
  t

Expand install actions, adding a build action preceding them. The argument noop_remove is a function that should return `true` for package where the `remove` action is known not to modify the filesystem (such as `conf-*` package). The argument sources_needed p is a function that should return packages list that require fetching same shared source (singleton when no source is shared), and an empty list if no fetching is required for that package (packages that do not require it are typically up-to-date pins or "in-place" builds).

Sourceval fold_descendants : (V.t -> 'a -> 'a) -> 'a -> t -> V.t -> 'a

Folds on all recursive successors of the given action, including itself, depth-first.