Library

Module

Module type

Parameter

Class

Class type

## Parameters

## Signature

`type 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

`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)

`type 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.

`type edge = E.t`

### Size functions

`val is_empty : t -> bool`

`val nb_vertex : t -> int`

`val nb_edges : t -> int`

Degree of a vertex

### Membership functions

`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`

.

`find_all_edges g v1 v2`

returns all the edges from `v1`

to `v2`

.

### Successors and predecessors

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

Labeled edges going from/to a vertex

### Graph iterators

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

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

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

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

`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`

Remove all vertices and edges from the given graph.

`copy g`

returns a copy of `g`

. Vertices and edges (and eventually marks, see module `Mark`

) are duplicated.

`add_vertex g v`

adds the vertex `v`

to the graph `g`

. Do nothing if `v`

is already in `g`

.

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

`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`

.

`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`

.

`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`

.

`include Graph.Oper.S with type g = t`

`type g = t`

`add_transitive_closure ?reflexive g`

replaces `g`

by its transitive closure. Meaningless for persistent implementations (then acts as `transitive_closure`

).

`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`

).

`replace_by_transitive_reduction ?reflexive g`

replaces `g`

by its transitive reduction. Meaningless for persistent implementations (then acts as `transitive_reduction`

).

`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`

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

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

`module Topological : sig ... end`

`module Dot : sig ... end`

`val transitive_closure : ?reflexive:bool -> t -> unit`

`val to_json : t OpamJson.encoder`

`val of_json : t OpamJson.decoder`

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.

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`

is a function that should return `true` for packages that require fetching sources (packages that do not require it are typically up-to-date pins or "in-place" builds).