• en

Module Algo

module Defaultgraphs : sig
val it : Common.Util.Info.t
val info : ('a, unit, string, unit) Pervasives.format4 -> 'a
val nt : Common.Util.Notice.t
val notice : ('a, unit, string, unit) Pervasives.format4 -> 'a
val wt : Common.Util.Warning.t
val warning : ('a, unit, string, unit) Pervasives.format4 -> 'a
val dt : Common.Util.Debug.t
val debug : ('a, unit, string, unit) Pervasives.format4 -> 'a
val fatal : ('a, unit, string, 'b) Pervasives.format4 -> 'a
val tr_timer : Common.Util.Timer.t
val trbar : Common.Util.Progress.t
TODO: functor:dose.3.2.2+opam/dose3/Algo.Defaultgraphs.GraphOper
module SyntacticDependencyGraph : sig
syntactic dependency graph. Vertex are Cudf packages and are indexed considering only the pair name,version . Edges are labelled with
  • OrDepends : disjuctive dependency
  • DirDepends : direct dependecy
  • Conflict : conflict
module PkgV : sig
type t =
| Pkg of Cudf.package
| Or of (Cudf.package * int)
val compare : t -> t -> int
val hash : t -> int
val equal : t -> t -> bool
end
module PkgE : sig
type t =
| OrDepends
| DirDepends
| Conflict
val compare : 'a -> 'a -> int
val hash : 'a -> int
val equal : 'a -> 'a -> bool
val default : t
end
module G : sig
type t = Graph.Imperative.Digraph.ConcreteBidirectionalLabeled(PkgV)(PkgE).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 = PkgV.t
val compare : t -> t -> int
val hash : t -> int
val equal : t -> t -> bool
type label = PkgV.t
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 = (PkgV.t * PkgE.t * PkgV.t)
val compare : t -> t -> int
type vertex = vertex
val src : t -> vertex
Edge origin.
val dst : t -> vertex
Edge destination.
type label = PkgE.t
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
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
val string_of_vertex : G.V.t -> string
val string_of_edge : G.E.t -> string
module DotPrinter : sig
module Display : sig
type t = Graph.Imperative.Digraph.ConcreteBidirectionalLabeled(PkgV)(PkgE).t
Abstract type of graphs
module V = G.V
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 = G.E
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
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
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 vertex_name : G.V.t -> string
val graph_attributes : 'a -> TODO: b list
val get_subgraph : 'a -> 'b option
val default_edge_attributes : 'a -> 'b list
val default_vertex_attributes : 'a -> TODO: b list
val vertex_attributes : G.V.t -> TODO: a list
val edge_attributes : G.E.t -> TODO: a list
end
val fprint_graph : Format.formatter -> Display.t -> unit
fprint_graph ppf graph pretty prints the graph graph in the CGL language on the formatter ppf.
val output_graph : Pervasives.out_channel -> Display.t -> unit
output_graph oc graph pretty prints the graph graph in the dot language on the channel oc.
val print : Format.formatter -> Display.t -> unit
end
module S : sig
type elt = PkgV.t
type t = Set.Make(PkgV).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 GmlPrinter : sig
val print : Format.formatter -> G.t -> unit
end
module GraphmlPrinter : sig
val print : Format.formatter -> G.t -> unit
print fmt graph print the GraphMl representation of the given graph on the given formatter
end
val depgraphbar : Common.Util.Progress.t
val dependency_graph : Cudf.universe -> G.t
end
TODO: functor:dose.3.2.2+opam/dose3/Algo.Defaultgraphs.MakePackageGraph
module PkgV : sig
type t = Cudf.package
val compare : Cudf.package -> Cudf.package -> int
val hash : Cudf.package -> int
val equal : Cudf.package -> Cudf.package -> bool
end
module PkgE : sig
type t = float
val compare : 'a -> 'a -> int
val hash : 'a -> int
val equal : 'a -> 'a -> bool
val default : float
end
module PackageGraph : sig
module G : sig
type t = Graph.Imperative.Digraph.ConcreteBidirectional(PkgV).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 = PkgV.t
val compare : t -> t -> int
val hash : t -> int
val equal : t -> t -> bool
type label = PkgV.t
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 = (PkgV.t * PkgV.t)
val compare : t -> t -> int
type vertex = vertex
val src : t -> vertex
Edge origin.
val dst : t -> vertex
Edge destination.
type label = unit
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
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 UG : sig
type t = Graph.Imperative.Graph.Concrete(PkgV).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 = PkgV.t
val compare : t -> t -> int
val hash : t -> int
val equal : t -> t -> bool
type label = PkgV.t
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 = (PkgV.t * PkgV.t)
val compare : t -> t -> int
type vertex = vertex
val src : t -> vertex
Edge origin.
val dst : t -> vertex
Edge destination.
type label = unit
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
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 O : sig
val transitive_reduction : G.t -> unit
module O : sig
type g = 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.
end
module S : sig
type elt = G.V.t
type t = Set.Make(G.V).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 subgraph : G.t -> S.elt list -> G.t
end
module S : sig
type elt = PkgV.t
type t = Set.Make(PkgV).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 DotPrinter : sig
module Display : sig
type t = Graph.Imperative.Digraph.ConcreteBidirectional(PkgV).t
Abstract type of graphs
module V = G.V
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 = G.E
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
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
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 vertex_name : Cudf.package -> string
val graph_attributes : 'a -> 'b list
val get_subgraph : 'a -> 'b option
val default_edge_attributes : 'a -> 'b list
val default_vertex_attributes : 'a -> 'b list
val vertex_attributes : Cudf.package -> TODO: a list
val edge_attributes : 'a -> 'b list
end
val fprint_graph : Format.formatter -> Display.t -> unit
fprint_graph ppf graph pretty prints the graph graph in the CGL language on the formatter ppf.
val output_graph : Pervasives.out_channel -> Display.t -> unit
output_graph oc graph pretty prints the graph graph in the dot language on the channel oc.
val print : Format.formatter -> Display.t -> unit
end
module GmlPrinter : sig
val print : Format.formatter -> G.t -> unit
end
module GraphmlPrinter : sig
val print : Format.formatter -> G.t -> unit
print fmt graph print the GraphMl representation of the given graph on the given formatter
end
val add_edge : ?transitive:bool -> G.t -> G.vertex -> G.vertex -> unit
val conjdepgraph_int : ?transitive:bool -> G.t -> Cudf.universe -> G.vertex -> unit
val conjdepgraph : Cudf.universe -> G.vertex list -> G.t
val conjdeps : G.t -> G.V.t -> G.V.t list
val dependency_graph : ?conjunctive:bool -> Cudf.universe -> G.t
val dependency_graph_list : ?conjunctive:bool -> Cudf.universe -> G.vertex list -> G.t
val conflict_graph : Cudf.universe -> UG.t
val undirect : G.t -> UG.t
val connected_components : UG.t -> UG.V.t list list
val pred_list : G.t -> G.vertex -> G.vertex list
val succ_list : G.t -> G.vertex -> G.vertex list
val pred_set : G.t -> G.vertex -> S.t
val succ_set : G.t -> G.vertex -> S.t
val cycle_reduction : G.t -> unit
val out : ?dump:string option -> ?dot:string option -> ?detrans:bool -> G.t -> unit
val load : 'a -> string -> G.t
end
module IntPkgGraph : sig
Integer Imperative Bidirectional Graph
module PkgV : sig
type t = int
val compare : 'a -> 'a -> int
val hash : 'a -> 'a
val equal : 'a -> 'a -> bool
end
module G : sig
type t = Graph.Imperative.Digraph.ConcreteBidirectional(PkgV).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 = PkgV.t
val compare : t -> t -> int
val hash : t -> int
val equal : t -> t -> bool
type label = PkgV.t
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 = (PkgV.t * PkgV.t)
val compare : t -> t -> int
type vertex = vertex
val src : t -> vertex
Edge origin.
val dst : t -> vertex
Edge destination.
type label = unit
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
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 S : sig
type elt = PkgV.t
type t = Set.Make(PkgV).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 O : sig
val transitive_reduction : G.t -> unit
module O : sig
type g = 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.
end
module S : sig
type elt = G.V.t
type t = Set.Make(G.V).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 subgraph : G.t -> S.elt list -> G.t
end
module DotPrinter : sig
module Display : sig
type t = Graph.Imperative.Digraph.ConcreteBidirectional(PkgV).t
Abstract type of graphs
module V = G.V
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 = G.E
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
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
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 vertex_name : int -> string
val graph_attributes : 'a -> 'b list
val get_subgraph : 'a -> 'b option
val default_edge_attributes : 'a -> 'b list
val default_vertex_attributes : 'a -> 'b list
val vertex_attributes : 'a -> 'b list
val edge_attributes : 'a -> 'b list
end
val fprint_graph : Format.formatter -> Display.t -> unit
fprint_graph ppf graph pretty prints the graph graph in the CGL language on the formatter ppf.
val output_graph : Pervasives.out_channel -> Display.t -> unit
output_graph oc graph pretty prints the graph graph in the dot language on the channel oc.
val print : Format.formatter -> Display.t -> unit
end
module DIn : sig
val parse : string -> Graph.Builder.I(G).G.t
Parses a dot file
val parse_bounding_box_and_clusters : string -> (Graph.Builder.I(G).G.t * string * Graph.Dot.clusters_hash)
Parses a dot file and returns the graph, its bounding box and a hash table from clusters to dot attributes
end
module GmlPrinter : sig
val print : Format.formatter -> G.t -> unit
end
val add_edge : bool -> G.t -> G.vertex -> G.vertex -> unit
val conjdepgraph_int : ?transitive:bool -> G.t -> Cudf.universe -> G.vertex -> unit
val conjdepgraph : Cudf.universe -> G.vertex list -> G.t
val conjdeps : G.t -> G.V.t -> G.V.t list
val dependency_graph : ?conjunctive:bool -> Cudf.universe -> G.t
val dependency_graph_list : ?conjunctive:bool -> Cudf.universe -> G.vertex list -> G.t
val load : 'a -> string -> G.t
end
end
module Statistics : sig
val it : Common.Util.Info.t
val info : ('a, unit, string, unit) Pervasives.format4 -> 'a
val nt : Common.Util.Notice.t
val notice : ('a, unit, string, unit) Pervasives.format4 -> 'a
val wt : Common.Util.Warning.t
val warning : ('a, unit, string, unit) Pervasives.format4 -> 'a
val dt : Common.Util.Debug.t
val debug : ('a, unit, string, unit) Pervasives.format4 -> 'a
val fatal : ('a, unit, string, 'b) Pervasives.format4 -> 'a
TODO: functor:dose.3.2.2+opam/dose3/Algo.Statistics.Make
end
module Dominators : sig
val dombar : Common.Util.Progress.t
val domtimer : Common.Util.Timer.t
val tjntimer : Common.Util.Timer.t
val crtimer : Common.Util.Timer.t
val sdtrtimer : Common.Util.Timer.t
val domtrtimer : Common.Util.Timer.t
val it : Common.Util.Info.t
val info : ('a, unit, string, unit) Pervasives.format4 -> 'a
val nt : Common.Util.Notice.t
val notice : ('a, unit, string, unit) Pervasives.format4 -> 'a
val wt : Common.Util.Warning.t
val warning : ('a, unit, string, unit) Pervasives.format4 -> 'a
val dt : Common.Util.Debug.t
val debug : ('a, unit, string, unit) Pervasives.format4 -> 'a
val fatal : ('a, unit, string, 'b) Pervasives.format4 -> 'a
module G = Defaultgraphs.PackageGraph.G
module O : sig
val transitive_reduction : G.t -> unit
module O : sig
type g = 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.
end
module S : sig
type elt = G.V.t
type t = Set.Make(G.V).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 subgraph : G.t -> S.elt list -> G.t
end
module S = Defaultgraphs.PackageGraph.S
val impactset : (G.t * G.vertex) -> S.t
val scons : (G.t * G.vertex) -> S.t
val dominators_direct : ?relative:float option -> G.t -> G.t
val dominators_tarjan : G.t -> G.t
end
module Diagnostic_int : sig
type reason =
| Dependency of (int * Cudf_types.vpkg list * int list)
| Missing of (int * Cudf_types.vpkg list)
| Conflict of (int * int * Cudf_types.vpkg)
type result =
| Success of ?all:bool -> unit -> int list
| Failure of unit -> reason list
type request =
| Sng of (int option * int)
| Lst of (int option * int list)
end
module Depsolver_int : sig
val progressbar_init : Common.Util.Progress.t
val progressbar_univcheck : Common.Util.Progress.t
val it : Common.Util.Info.t
val info : ('a, unit, string, unit) Pervasives.format4 -> 'a
val nt : Common.Util.Notice.t
val notice : ('a, unit, string, unit) Pervasives.format4 -> 'a
val wt : Common.Util.Warning.t
val warning : ('a, unit, string, unit) Pervasives.format4 -> 'a
val dt : Common.Util.Debug.t
val debug : ('a, unit, string, unit) Pervasives.format4 -> 'a
val fatal : ('a, unit, string, 'b) Pervasives.format4 -> 'a
module R : sig
type reason = Diagnostic_int.reason
end
module S : sig
module X : sig
type reason = R.reason
end
type state = Common.EdosSolver.M(R).state
state of the solver
type var = int
variables are integers numbered from 0 to (size - 1)
type value = Common.EdosSolver.M(R).value =
| True
| False
| Unknown
The value of a literal
type lit = Common.EdosSolver.M(R).lit
A literal. Literals can be positive or negative
val lit_of_var : var -> bool -> lit
lit_of_var given a variable create a positive or a negative literal. By default the assigment of all variables (that is its value) is Unknown.
val initialize_problem : ?pbo:int array -> ?print_var:Format.formatter -> int -> unit -> ?buffer:bool -> int -> state
initialize the solver initialize_problem n
print_var a function to print a variable
buffer decide weather or not to store a human readable representaion of the sat problem.
n the size of the sat problem. that is the max number of variables to consider
val copy : state -> state
provide a deep copy of the current state of the solver
val propagate : state -> unit
val protect : state -> unit
val reset : state -> unit
reset reset the state of the solver to a state that would be obtained by re initializing the solver with an identical constraints set
val assignment : state -> value array
assignment st return the array of values associated to every variable.
val assignment_true : state -> var list
assignment_true st return the list of variables that are true
val add_rule : state -> lit array -> X.reason list -> unit
add_rule st l add a disjuction to the solver of type TARGET NONE: \Bigvee l
val associate_vars : state -> lit -> var list -> unit
associate_vars st lit vl associate a variable to a list of variables. The solver will use this information to guide the search heuristic
val solve_all : state -> unit -> state -> var -> bool
val solve_pbo : (int array * state) -> unit -> state -> var -> bool
solve st v finds a variable assignment that makes v True
val solve : state -> var -> bool
val solve_lst : state -> var list -> bool
solve st l finds a variable assignment that makes True all variables in l
val collect_reasons : state -> var -> X.reason list
in case of failure return the list of associated reasons
val collect_reasons_lst : state -> var list -> X.reason list
in case of failure return the list of associated reasons
val dump : state -> (int * bool) list list
if the solver was initialized with buffer = true, dump the state of the solver. Return an empty list otherwise
val debug : bool -> unit
enable debug messages
val stats : state -> unit
val pboidx : state -> int -> int -> int
end
TODO: dose.3.2.2+opam/dose3/Algo.Depsolver_intTODO: dose.3.2.2+opam/dose3/Algo.Depsolver_int
type intprojection = TODO: a
type #intprojection = TODO: a
TODO: dose.3.2.2+opam/dose3/Algo.Depsolver_intTODO: dose.3.2.2+opam/dose3/Algo.Depsolver_int
type identity = TODO: a
type #identity = TODO: a
val init_map : Common.Util.IntHashtbl.key list -> 'a -> intprojection
type solver = {
constraints : S.state; (* the sat problem *)
map : intprojection; (* a map from cudf package ids to solver ids *)
}
low level solver data type
type dep_t = ((Cudf_types.vpkg list * S.var list) list * (Cudf_types.vpkg * S.var list) list)
type pool_t = dep_t array
type pool =
| SolverPool of pool_t
| CudfPool of pool_t
type result =
| Success of unit -> int list
| Failure of unit -> Diagnostic_int.reason list
val strip_solver_pool : pool -> pool_t
val strip_cudf_pool : pool -> pool_t
val init_pool_univ : global_constraints:bool -> Cudf.universe -> pool
val init_solver_pool : TODO: a -> pool -> 'b list -> pool
val newpred : S.state -> S.var -> S.var list -> unit
val rempred : S.state -> S.var -> S.var list -> unit
val changepred : S.state -> S.var -> S.var list -> S.var list -> unit
type domain =
| New
| Removed
| Solution
| Changed
type criteria =
| Count of domain
| NotUpToDate of domain
| UnsatRecommends of domain
val init_criteria : ?closure:int list -> criteria array -> Cudf.universe -> (criteria * (int list * int list) list * int * int) list
val init_solver_criteria : TODO: a -> S.state -> (criteria * ('b list * 'b list) list * 'c * int) list -> unit
val init_solver_cache : ?buffer:bool -> ?pbopool:('a * 'b * int * int) list -> pool -> S.state
val solve : ?tested:bool array -> solver -> Diagnostic_int.request -> Diagnostic_int.result
val solve_pbo : ?callback:(int array * Diagnostic_int.result) -> unit -> solver -> Diagnostic_int.request -> Diagnostic_int.result
val pkgcheck : bool -> (Diagnostic_int.result * Diagnostic_int.request) -> 'a option -> solver -> bool array -> int -> bool
val init_solver_univ : ?global_constraints:bool -> ?buffer:bool -> Cudf.universe -> solver
val init_solver_closure : ?buffer:bool -> ?pbopool:(criteria * (Common.Util.IntHashtbl.key list * Common.Util.IntHashtbl.key list) list * int * int) list -> pool -> Common.Util.IntHashtbl.key list -> solver
val copy_solver : solver -> solver
val reverse_dependencies : Cudf.universe -> int list array
val dependency_closure_cache : ?maxdepth:int -> ?conjunctive:bool -> pool -> int list -> S.var list
val dependency_closure : ?maxdepth:int -> ?conjunctive:bool -> Cudf.universe -> Cudf.package list -> Cudf.package list
val reverse_dependency_closure : ?maxdepth:int -> int list array -> int list -> int list
end
module Strongdeps_int : sig
val mainbar : Common.Util.Progress.t
val conjbar : Common.Util.Progress.t
val strongtimer : Common.Util.Timer.t
val conjtimer : Common.Util.Timer.t
val it : Common.Util.Info.t
val info : ('a, unit, string, unit) Pervasives.format4 -> 'a
val nt : Common.Util.Notice.t
val notice : ('a, unit, string, unit) Pervasives.format4 -> 'a
val wt : Common.Util.Warning.t
val warning : ('a, unit, string, unit) Pervasives.format4 -> 'a
val dt : Common.Util.Debug.t
val debug : ('a, unit, string, unit) Pervasives.format4 -> 'a
val fatal : ('a, unit, string, 'b) Pervasives.format4 -> 'a
module G = Defaultgraphs.PackageGraph.G
module O = Defaultgraphs.PackageGraph.O
val strong_depends : Depsolver_int.solver -> int -> Common.Util.IntHashtbl.key -> bool
val check_strong : Cudf.universe -> bool -> G.t -> Depsolver_int.solver -> Common.Util.IntHashtbl.key -> Common.Util.IntHashtbl.key list -> unit
val somedisj : Depsolver_int.pool -> int -> bool
val strongdeps_int : ?transitive:bool -> G.t -> Cudf.universe -> G.vertex list -> G.t
val strongdeps : ?transitive:bool -> Cudf.universe -> G.vertex list -> G.t
val strongdeps_univ : ?transitive:bool -> Cudf.universe -> G.t
val impactlist : Defaultgraphs.PackageGraph.G.t -> Defaultgraphs.PackageGraph.G.vertex -> Defaultgraphs.PackageGraph.G.vertex list
val stronglist : Defaultgraphs.PackageGraph.G.t -> Defaultgraphs.PackageGraph.G.vertex -> Defaultgraphs.PackageGraph.G.vertex list
val impactset : Defaultgraphs.PackageGraph.G.t -> Defaultgraphs.PackageGraph.G.vertex -> Defaultgraphs.PackageGraph.S.t
val strongset : Defaultgraphs.PackageGraph.G.t -> Defaultgraphs.PackageGraph.G.vertex -> Defaultgraphs.PackageGraph.S.t
end
module Strongdeps : sig
val strongdeps : ?transitive:bool -> Cudf.universe -> Cudf.package list -> Defaultgraphs.PackageGraph.G.t
strongdeps u l build the strong dependency graph of all packages in l wrt the universe u
val strongdeps_univ : ?transitive:bool -> Cudf.universe -> Defaultgraphs.PackageGraph.G.t
strongdeps_univ u build the strong dependency graph of all packages in the universe u
val impactset : Defaultgraphs.PackageGraph.G.t -> Cudf.package -> Cudf.package list
compute the impact set of the node q, that is the list of all packages p that strong depends on q
val conjdeps_univ : Cudf.universe -> Defaultgraphs.PackageGraph.G.t
compute the conjunctive dependency graph
val conjdeps : Cudf.universe -> Cudf.package list -> Defaultgraphs.PackageGraph.G.t
compute the conjunctive dependency graph considering only packages in pkglist
end
module Diagnostic : sig
type reason =
| Dependency of (Cudf.package * Cudf_types.vpkg list * Cudf.package list) (* Not strictly a un-installability, Dependency (a,vpkglist,pkglist) is used to recontruct the the dependency path from the root package to the offending un-installable package *)
| Missing of (Cudf.package * Cudf_types.vpkg list) (* Missing (a,vpkglist) means that the dependency vpkglist of package a cannot be satisfied *)
| Conflict of (Cudf.package * Cudf.package * Cudf_types.vpkg) (* Conflict (a,b,vpkg) means that the package a is in conflict with package b because of vpkg *)
type request =
| Package of Cudf.package (* Check the installability of one package *)
| PackageList of Cudf.package list (* Check the installability of a list of packages *)
The request provided to the solver
type result =
| Success of ?all:bool -> unit -> Cudf.package list (* If successfull returns a function that will return the installation set for the given query. Since not all packages are tested for installability directly, the installation set might be empty. In this case, the solver can be called again to provide the real installation set using the parameter ~all:true *)
| Failure of unit -> reason list (* If unsuccessful returns a function containing the list of reason *)
The result of an installability query
type diagnosis = {
result : result;
request : request;
}
module ResultHash : sig
type key = reason
type 'a t
val create : int -> 'a t
val clear : 'a t -> unit
val reset : 'a t -> unit
val copy : 'a t -> 'a t
val add : 'a t -> key -> 'a -> unit
val remove : 'a t -> key -> unit
val find : 'a t -> key -> 'a
val find_all : 'a t -> key -> 'a list
val replace : 'a t -> key -> 'a -> unit
val mem : 'a t -> key -> bool
val iter : key -> 'a -> unit -> 'a t -> unit
val fold : key -> 'a -> 'b -> 'b -> 'a t -> 'b -> 'b
val length : 'a t -> int
val stats : 'a t -> Hashtbl.statistics
end
type summary = {
missing : int;
conflict : int;
unique_missing : int;
unique_conflict : int;
summary : Cudf.package list Pervasives.ref ResultHash.t;
}
val default_result : int -> summary
val collect : summary -> diagnosis -> unit
type pp = Cudf.package -> (string * string * (string * string) list)
val pp_summary : ?pp:Cudf.package -> (Cudf_types.pkgname * string * (string * string) list) -> ?explain:bool -> unit -> Format.formatter -> summary -> unit
val pp_package : ?source:bool -> pp -> Format.formatter -> Cudf.package -> unit
val pp_vpkglist : pp -> Format.formatter -> Cudf_types.vpkglist -> unit
val pp_dependency : pp -> ?label:string -> Format.formatter -> (Cudf.package * Cudf_types.vpkglist) -> unit
val pp_dependencies : pp -> Format.formatter -> (Cudf.package * Cudf_types.vpkglist) list list -> unit
val pp_list : Format.formatter -> 'a -> unit -> Format.formatter -> 'a list -> unit
val print_error : pp -> Cudf.package -> Format.formatter -> reason list -> unit
val get_installationset : ?minimal:bool -> diagnosis -> Cudf.package list
val is_solution : diagnosis -> bool
val default_pp : Cudf.package -> (Cudf_types.pkgname * string * 'a list)
val print_error_human : ?prefix:string -> pp -> Cudf.package -> Format.formatter -> reason list -> unit
val fprintf_human : ?pp:pp -> ?prefix:string -> Format.formatter -> diagnosis -> unit
val fprintf : ?pp:pp -> ?failure:bool -> ?success:bool -> ?explain:bool -> ?minimal:bool -> Format.formatter -> diagnosis -> unit
val printf : ?pp:pp -> ?failure:bool -> ?success:bool -> ?explain:bool -> diagnosis -> unit
end
module Depsolver : sig
type solver
the solver is an abstract data type associated to a universe
val load : ?check:bool -> Cudf.universe -> solver
initialize the solver. If check is true (default), then check for universe consistency (cf. Cudf_checker.is_consistent)
val result : Depsolver_int.identity -> Cudf.universe -> Diagnostic_int.result -> Diagnostic.result
Turn a result from Diagnostic_int into one of Diagnostic
val request : Cudf.universe -> Diagnostic_int.request -> Diagnostic.request
Turn a request from Diagnostic_int into one of Diagnostic
val edos_install : ?global_constraints:bool -> Cudf.universe -> Cudf.package -> Diagnostic.diagnosis
check if the given package can be installed in the universe
global_constraints : enforce global constraints on the given universe. In particular packages marked as `Keep_package must be always installed. Default false.
val edos_coinstall : ?global_constraints:bool -> Cudf.universe -> Cudf.package list -> Diagnostic.diagnosis
check if the give package list can be installed in the universe
global_constraints : enforce global constraints on the given universe. In particular packages marked as `Keep_package must be always installed. Default false.
val edos_coinstall_prod : ?global_constraints:bool -> Cudf.universe -> Cudf.package list list -> Diagnostic.diagnosis list
accept a list of list of packages and return the coinstallability test of the cartesian product.
val trim : ?global_constraints:bool -> Cudf.universe -> Cudf.universe
remove uninstallable packages from the universe . global_constraints is true by default
val find_broken : ?global_constraints:bool -> Cudf.universe -> Cudf.package list
return the list of broken packages
val find_installable : ?global_constraints:bool -> Cudf.universe -> Cudf.package list
return the list of installable packages
val find_listbroken : ?global_constraints:bool -> Cudf.universe -> Cudf.package list -> Cudf.package list
return the list of broken packages
val find_listinstallable : ?global_constraints:bool -> Cudf.universe -> Cudf.package list -> Cudf.package list
return the list of installable packages
val univcheck : ?global_constraints:bool -> ?callback:Diagnostic.diagnosis -> unit -> Cudf.universe -> int
univcheck check if all packages in the universe can be installed. Since not all packages are directly tested for installation, if a packages is installable, the installation might be empty. To obtain an installation set for each installable packages, the correct procedure is to iter on the list of packages.
callback : execute a function for each package. This function can have side effects and can be used to collect the installation set or the failure reason.
global_constraints : enforce global constraints on the given universe. In particular packages marked as `Keep_package must be always installed. Default true.
Returns the number of broken packages
val listcheck : ?global_constraints:bool -> ?callback:Diagnostic.diagnosis -> unit -> Cudf.universe -> Cudf.package list -> int
val dependency_closure : ?maxdepth:int -> ?conjunctive:bool -> Cudf.universe -> Cudf.package list -> Cudf.package list
dependency_closure universe l compute the dependencies closure of the give package list. Invariant : l must be a subset of universe
val reverse_dependencies : Cudf.universe -> Cudf.package list Common.CudfAdd.Cudf_hashtbl.t
reverse_dependencies univ compute the reverse dependency list of all packages in the universe univ
val reverse_dependency_closure : ?maxdepth:int -> Cudf.universe -> Cudf.package list -> Cudf.package list
reverse_dependencies_closure univ compute the reverse dependency list of all packages in l in the universe univ
type enc =
| Cnf
| Dimacs
val output_clauses : ?global_constraints:bool -> ?enc:enc -> Cudf.universe -> string
output_clauses enc univ return a string encoded accordingly to enc (default cnf).
global_constraints : enforce global constraints on the given universe.
type solver_result =
| Sat of (Cudf.preamble option * Cudf.universe)
| Unsat of Diagnostic.diagnosis option
| Error of string
val check_request : ?cmd:string -> ?callback:(int array * Diagnostic.diagnosis) -> unit -> ?criteria:string -> ?explain:bool -> Cudf.cudf -> solver_result
check_request check if there exists a solution for the give cudf document if ?cmd is specified, it will be used to call an external cudf solver to satisfy the request. if ?criteria is specified it will be used as optimization criteria. if ?explain is specified and there is no solution for the give request, the result will contain the failure reason.
val check_request_using : ?call_solver:Cudf.cudf -> (Cudf.preamble option * Cudf.universe) -> ?callback:(int array * Diagnostic.diagnosis) -> unit -> ?criteria:string -> ?explain:bool -> Cudf.cudf -> solver_result
Same as check_request, but allows to specify any function to call the external solver. It should raise Depsolver.Unsat on failure
end
module Strongconflicts_int : sig
val it : Common.Util.Info.t
val info : ('a, unit, string, unit) Pervasives.format4 -> 'a
val nt : Common.Util.Notice.t
val notice : ('a, unit, string, unit) Pervasives.format4 -> 'a
val wt : Common.Util.Warning.t
val warning : ('a, unit, string, unit) Pervasives.format4 -> 'a
val dt : Common.Util.Debug.t
val debug : ('a, unit, string, unit) Pervasives.format4 -> 'a
val fatal : ('a, unit, string, 'b) Pervasives.format4 -> 'a
module SG = Defaultgraphs.IntPkgGraph.G
module PkgV = Defaultgraphs.IntPkgGraph.PkgV
type cfl_type =
| Explicit
| Conjunctive
| Other of Diagnostic_int.reason list
module CflE : sig
type t = (int * int * cfl_type)
val compare : 'a -> 'a -> int
val default : (int * int * cfl_type)
end
module IG = Graph.Imperative.Matrix.Graph
module CG : sig
type t = Graph.Imperative.Graph.ConcreteLabeled(PkgV)(CflE).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 = PkgV.t
val compare : t -> t -> int
val hash : t -> int
val equal : t -> t -> bool
type label = PkgV.t
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 = (PkgV.t * CflE.t * PkgV.t)
val compare : t -> t -> int
type vertex = vertex
val src : t -> vertex
Edge origin.
val dst : t -> vertex
Edge destination.
type label = CflE.t
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
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
val seedingbar : Common.Util.Progress.t
val localbar : Common.Util.Progress.t
val sctimer : Common.Util.Timer.t
module S : sig
type elt = int
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 swap : ('a * 'a) -> ('a * 'a)
val to_set : S.elt list -> S.t
val explicit : Cudf.universe -> ((int * int), unit) ExtLib.Hashtbl.t
val triangle : S.elt list array -> S.t -> S.t -> S.t -> bool
val strongconflicts : Cudf.universe -> CG.t
end
module Strongconflicts : sig
val it : Common.Util.Info.t
val info : ('a, unit, string, unit) Pervasives.format4 -> 'a
val nt : Common.Util.Notice.t
val notice : ('a, unit, string, unit) Pervasives.format4 -> 'a
val wt : Common.Util.Warning.t
val warning : ('a, unit, string, unit) Pervasives.format4 -> 'a
val dt : Common.Util.Debug.t
val debug : ('a, unit, string, unit) Pervasives.format4 -> 'a
val fatal : ('a, unit, string, 'b) Pervasives.format4 -> 'a
module ICG = Strongconflicts_int.CG
type cfl_type =
| Explicit
| Conjunctive
| Other of Diagnostic.reason list
module CflE : sig
type t = (Cudf.package * Cudf.package * cfl_type)
val compare : 'a -> 'a -> int
val default : (Cudf.package * Cudf.package * cfl_type)
end
module CG : sig
type t = Graph.Imperative.Graph.ConcreteLabeled(Defaultgraphs.PkgV)(CflE).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 = Defaultgraphs.PkgV.t
val compare : t -> t -> int
val hash : t -> int
val equal : t -> t -> bool
type label = Defaultgraphs.PkgV.t
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 = (Defaultgraphs.PkgV.t * CflE.t * Defaultgraphs.PkgV.t)
val compare : t -> t -> int
type vertex = vertex
val src : t -> vertex
Edge origin.
val dst : t -> vertex
Edge destination.
type label = CflE.t
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
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
val reason : Cudf.universe -> Diagnostic_int.reason list -> Diagnostic.reason list
val cvt : Cudf.universe -> Strongconflicts_int.cfl_type -> cfl_type
val strongconflicts : Cudf.universe -> CG.t
end
module Flatten : sig
val it : Common.Util.Info.t
val info : ('a, unit, string, unit) Pervasives.format4 -> 'a
val nt : Common.Util.Notice.t
val notice : ('a, unit, string, unit) Pervasives.format4 -> 'a
val wt : Common.Util.Warning.t
val warning : ('a, unit, string, unit) Pervasives.format4 -> 'a
val dt : Common.Util.Debug.t
val debug : ('a, unit, string, unit) Pervasives.format4 -> 'a
val fatal : ('a, unit, string, 'b) Pervasives.format4 -> 'a
val print_list : Format.formatter -> Format.formatter -> 'a -> unit -> string -> 'a list -> unit
module Package : sig
type t = int
val print : Cudf.universe -> Format.formatter -> int -> unit
val compare : int -> int -> int
end
module PSet : sig
type elt = Package.t
type t = Set.Make(Package).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 print_set : Format.formatter -> Format.formatter -> PSet.elt -> unit -> string -> PSet.t -> unit
val pset_of_lst : PSet.elt list -> PSet.t
val pset_map : PSet.elt -> PSet.elt -> PSet.t -> PSet.t
module PTbl : sig
type 'a t = 'a array
val create : int -> 'a -> 'a array
val init : int -> int -> 'a -> 'a array
val get : 'a array -> int -> 'a
val set : 'a array -> int -> 'a -> unit
val iteri : int -> 'a -> unit -> 'a array -> unit
val map : 'a -> 'b -> 'a array -> 'b array
val mapi : int -> 'a -> 'b -> 'a array -> 'b array
val foldi : int -> 'a -> 'b -> 'b -> 'a array -> 'b -> 'b
val fold : 'a -> 'b -> 'b -> 'a array -> 'b -> 'b
end
module Disj : sig
type t = PSet.t
val print : Cudf.universe -> Format.formatter -> PSet.t -> unit
val implies : PSet.t -> PSet.t -> bool
val equiv : PSet.t -> PSet.t -> bool
val lit : PSet.elt -> PSet.t
val lit_disj : PSet.elt list -> PSet.t
val _false : PSet.t
val disj : PSet.t -> PSet.t -> PSet.t
val disjl : PSet.t list -> PSet.t
val iter : PSet.t -> PSet.elt -> unit -> unit
val cut : PSet.t -> PSet.elt -> PSet.t -> PSet.t
val fold : PSet.elt -> 'a -> 'a -> PSet.t -> 'a -> 'a
val for_all : PSet.elt -> bool -> PSet.t -> bool
val exists : PSet.elt -> bool -> PSet.t -> bool
val implies1 : PSet.elt -> PSet.t -> bool
val to_lit : PSet.t -> PSet.elt option
val to_lits : 'a -> 'a
val filter : PSet.elt -> bool -> PSet.t -> PSet.t
val normalize : PSet.t -> PSet.t
val compare : PSet.t -> PSet.t -> int
end
module CSet : sig
type elt = Disj.t
type t = Set.Make(Disj).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 Formula : sig
type t = Disj.t list
val print : Cudf.universe -> Format.formatter -> PSet.t list -> unit
val of_disj : 'a -> 'a list
val lit : PSet.elt -> PSet.t list
val lit_disj : PSet.elt list -> PSet.t list
val implies1 : PSet.t list -> PSet.t -> bool
val implies : PSet.t list -> PSet.t list -> bool
val equiv : PSet.t list -> PSet.t list -> bool
val _true : 'a list
val conj1 : PSet.t list -> PSet.t -> PSet.t list
val conj : PSet.t list -> PSet.t list -> PSet.t list
val conjl : PSet.t list list -> PSet.t list
val _false : PSet.t list
val disj : PSet.t list -> PSet.t list -> PSet.t list
val disjl : PSet.t list list -> PSet.t list
val iter : 'a list -> 'a -> unit -> unit
val fold : 'a -> 'b -> 'b -> 'a list -> 'b -> 'b
val filter : 'a -> bool -> 'a list -> 'a list
val exists : 'a -> bool -> 'a list -> bool
val map : 'a -> 'b -> 'a list -> 'b list
val normalize : PSet.t list -> PSet.t list
end
module Conflict : sig
type t = PSet.t PTbl.t
val create : int -> PSet.t array
val has : PSet.t array -> int -> bool
val check : PSet.t array -> PSet.elt -> int -> bool
val add : PSet.t array -> PSet.elt -> PSet.elt -> unit
val remove : PSet.t array -> PSet.elt -> PSet.elt -> unit
val iter : PSet.t array -> PSet.elt -> PSet.elt -> unit -> unit
val iter_on_packages : 'a array -> int -> 'a -> unit -> unit
val of_package : 'a array -> int -> 'a
val exists : PSet.t array -> PSet.elt -> bool -> int -> bool
val for_all : PSet.t array -> PSet.elt -> bool -> int -> bool
end
val simplify_formula : PSet.t array -> PSet.t list -> PSet.t list
val filter_conflicts : PSet.t array -> 'a -> PSet.t list -> PSet.t list
val flatten_deps : (PSet.elt, PSet.t list) ExtLib.Hashtbl.t -> PSet.t list array -> PSet.t array -> PSet.elt list -> PSet.t list -> (PSet.t list * PSet.t)
val flatten_dep : (PSet.elt, PSet.t list) ExtLib.Hashtbl.t -> PSet.t list array -> PSet.t array -> PSet.elt list -> PSet.elt -> (PSet.t list * PSet.t)
val flatten_dependencies : int -> PSet.t list array -> PSet.t array -> PSet.t list array
val remove_self_conflicts : PSet.t list array -> PSet.t array -> PSet.t list array
val remove_redundant_conflicts : PSet.t list array -> PSet.t array -> PSet.t list array
val maybe_remove : PSet.t list array -> PSet.t array -> 'a -> 'b -> PSet.t -> bool
val is_composition : PSet.t list array -> PSet.elt -> PSet.t list -> PSet.t -> bool
val remove_deps : PSet.t list array -> PSet.t array -> PSet.t list array
val repository : Cudf.universe -> (PSet.t list array * PSet.t array)
val flatten_repository : int -> (PSet.t list array * PSet.t array) -> (PSet.t list array * PSet.t array)
end