jon.recoil.org

Module OpamPackage.GraphSource

Parallel executions.

include Graph.Sig.I with type E.label = OpamParallel.dependency_label with type V.t = OpamPackage.t

An imperative graph is a graph.

include Graph.Sig.G with type E.label = OpamParallel.dependency_label with type V.t = OpamPackage.t

Graph structure

type t

Abstract type of graphs

module V : Graph.Sig.VERTEX with type t = OpamPackage.t

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 = OpamPackage.Graph.V.t

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.

val is_directed : bool

Is this an implementation of directed graphs?

Size functions

val is_empty : OpamPackage.Graph.t -> bool
val nb_vertex : OpamPackage.Graph.t -> int
val nb_edges : OpamPackage.Graph.t -> int

Degree of a vertex

out_degree g v returns the out-degree of v in g.

in_degree g v returns the in-degree of v in g.

Membership functions

val mem_vertex : OpamPackage.Graph.t -> OpamPackage.Graph.vertex -> bool
val mem_edge_e : OpamPackage.Graph.t -> OpamPackage.Graph.edge -> bool

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.

  • since ocamlgraph 1.8

Successors and predecessors

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

succ g v returns the successors of v in g.

pred g v returns the predecessors of v in g.

Labeled edges going from/to a vertex

succ_e g v returns the edges going from v in g.

pred_e g v returns the edges going to v in g.

Graph iterators

val iter_vertex : (OpamPackage.Graph.vertex -> unit) -> OpamPackage.Graph.t -> unit

Iter on all vertices of a graph.

val fold_vertex : (OpamPackage.Graph.vertex -> 'a -> 'a) -> OpamPackage.Graph.t -> 'a -> 'a

Fold on all vertices of a graph.

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

val fold_edges : (OpamPackage.Graph.vertex -> OpamPackage.Graph.vertex -> 'a -> 'a) -> OpamPackage.Graph.t -> 'a -> 'a

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

val iter_edges_e : (OpamPackage.Graph.edge -> unit) -> OpamPackage.Graph.t -> unit

Iter on all edges of a graph.

val fold_edges_e : (OpamPackage.Graph.edge -> 'a -> 'a) -> OpamPackage.Graph.t -> 'a -> 'a

Fold on all edges of a graph.

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.

val fold_succ : (OpamPackage.Graph.vertex -> 'a -> 'a) -> OpamPackage.Graph.t -> OpamPackage.Graph.vertex -> 'a -> 'a
val fold_pred : (OpamPackage.Graph.vertex -> 'a -> 'a) -> OpamPackage.Graph.t -> OpamPackage.Graph.vertex -> 'a -> 'a

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

val iter_succ_e : (OpamPackage.Graph.edge -> unit) -> OpamPackage.Graph.t -> OpamPackage.Graph.vertex -> unit
val fold_succ_e : (OpamPackage.Graph.edge -> 'a -> 'a) -> OpamPackage.Graph.t -> OpamPackage.Graph.vertex -> 'a -> 'a
val iter_pred_e : (OpamPackage.Graph.edge -> unit) -> OpamPackage.Graph.t -> OpamPackage.Graph.vertex -> unit
val fold_pred_e : (OpamPackage.Graph.edge -> 'a -> 'a) -> OpamPackage.Graph.t -> OpamPackage.Graph.vertex -> 'a -> 'a
val create : ?size:int -> unit -> OpamPackage.Graph.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 : OpamPackage.Graph.t -> unit

Remove all vertices and edges from the given graph.

  • since ocamlgraph 1.4

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

val add_vertex : OpamPackage.Graph.t -> OpamPackage.Graph.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 : OpamPackage.Graph.t -> OpamPackage.Graph.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.

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 : OpamPackage.Graph.t -> OpamPackage.Graph.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.

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.

val remove_edge_e : OpamPackage.Graph.t -> OpamPackage.Graph.edge -> unit

remove_edge_e g e removes the edge e from the graph g. Do nothing if e is not in g.

include Graph.Oper.S with type g = OpamPackage.Graph.t
val add_transitive_closure : ?reflexive:bool -> OpamPackage.Graph.g -> OpamPackage.Graph.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 -> OpamPackage.Graph.g -> OpamPackage.Graph.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.

val replace_by_transitive_reduction : ?reflexive:bool -> OpamPackage.Graph.g -> OpamPackage.Graph.g

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.

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 ... end
Sourcemodule Dot : sig ... end
Sourceval transitive_closure : ?reflexive:bool -> OpamPackage.Graph.t -> unit