sig
  module Set :
    sig
      type elt = Cudf.package
      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) -> t -> '-> '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 map : (elt -> elt) -> t -> t
      val choose_one : t -> elt
      val of_list : elt list -> t
      val to_string : t -> string
      val to_json : t -> OpamJson.t
      val find : (elt -> bool) -> t -> elt
    end
  module Map :
    sig
      type key = Cudf.package
      type +'a t
      val empty : 'a t
      val is_empty : 'a t -> bool
      val mem : key -> 'a t -> bool
      val add : key -> '-> 'a t -> 'a t
      val singleton : key -> '-> 'a t
      val remove : key -> 'a t -> 'a t
      val merge :
        (key -> 'a option -> 'b option -> 'c option) -> 'a t -> 'b t -> 'c t
      val compare : ('-> '-> int) -> 'a t -> 'a t -> int
      val equal : ('-> '-> bool) -> 'a t -> 'a t -> bool
      val iter : (key -> '-> unit) -> 'a t -> unit
      val fold : (key -> '-> '-> 'b) -> 'a t -> '-> 'b
      val for_all : (key -> '-> bool) -> 'a t -> bool
      val exists : (key -> '-> bool) -> 'a t -> bool
      val filter : (key -> '-> bool) -> 'a t -> 'a t
      val partition : (key -> '-> bool) -> 'a t -> 'a t * 'a t
      val cardinal : 'a t -> int
      val bindings : 'a t -> (key * 'a) list
      val min_binding : 'a t -> key * 'a
      val max_binding : 'a t -> key * 'a
      val choose : 'a t -> key * 'a
      val split : key -> 'a t -> 'a t * 'a option * 'a t
      val find : key -> 'a t -> 'a
      val map : ('-> 'b) -> 'a t -> 'b t
      val mapi : (key -> '-> 'b) -> 'a t -> 'b t
      val to_string : ('-> string) -> 'a t -> string
      val to_json : ('-> OpamJson.t) -> 'a t -> OpamJson.t
      val values : 'a t -> 'a list
      val keys : 'a t -> key list
      val union : ('-> '-> 'a) -> 'a t -> 'a t -> 'a t
      val of_list : (key * 'a) list -> 'a t
    end
  module Graph :
    sig
      type t
      val of_universe : Cudf.universe -> OpamCudf.Graph.t
      val transitive_closure : OpamCudf.Graph.t -> OpamCudf.Graph.t
      val close_and_linearize :
        OpamCudf.Graph.t -> OpamCudf.Set.t -> Cudf.package list
    end
  module Diff :
    sig
      type package = {
        installed : OpamCudf.Set.t;
        removed : OpamCudf.Set.t;
        reinstalled : OpamCudf.Set.t;
      }
      type universe = (Cudf_types.pkgname, OpamCudf.Diff.package) Hashtbl.t
      val diff : Cudf.universe -> Cudf.universe -> OpamCudf.Diff.universe
    end
  module ActionGraph :
    sig
      type package = Cudf.package
      type t
      module V :
        sig
          type t = package OpamTypes.action
          val compare : t -> t -> int
          val hash : t -> int
          val equal : t -> t -> bool
          type label
          val create : label -> t
          val label : t -> label
        end
      type vertex = V.t
      module E :
        sig
          type t
          val compare : t -> t -> int
          type vertex = vertex
          val src : t -> vertex
          val dst : t -> vertex
          type label
          val create : vertex -> label -> vertex -> t
          val label : t -> label
        end
      type edge = E.t
      val is_directed : bool
      val is_empty : t -> bool
      val nb_vertex : t -> int
      val nb_edges : t -> int
      val out_degree : t -> vertex -> int
      val in_degree : t -> vertex -> int
      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
      val find_all_edges : t -> vertex -> vertex -> edge list
      val succ : t -> vertex -> vertex list
      val pred : t -> vertex -> vertex list
      val succ_e : t -> vertex -> edge list
      val pred_e : t -> vertex -> edge list
      val iter_vertex : (vertex -> unit) -> t -> unit
      val fold_vertex : (vertex -> '-> 'a) -> t -> '-> 'a
      val iter_edges : (vertex -> vertex -> unit) -> t -> unit
      val fold_edges : (vertex -> vertex -> '-> 'a) -> t -> '-> 'a
      val iter_edges_e : (edge -> unit) -> t -> unit
      val fold_edges_e : (edge -> '-> 'a) -> t -> '-> 'a
      val map_vertex : (vertex -> vertex) -> t -> t
      val iter_succ : (vertex -> unit) -> t -> vertex -> unit
      val iter_pred : (vertex -> unit) -> t -> vertex -> unit
      val fold_succ : (vertex -> '-> 'a) -> t -> vertex -> '-> 'a
      val fold_pred : (vertex -> '-> 'a) -> t -> vertex -> '-> 'a
      val iter_succ_e : (edge -> unit) -> t -> vertex -> unit
      val fold_succ_e : (edge -> '-> 'a) -> t -> vertex -> '-> 'a
      val iter_pred_e : (edge -> unit) -> t -> vertex -> unit
      val fold_pred_e : (edge -> '-> 'a) -> t -> vertex -> '-> 'a
      val create : ?size:int -> unit -> t
      val clear : t -> unit
      val copy : t -> t
      val add_vertex : t -> vertex -> unit
      val remove_vertex : t -> vertex -> unit
      val add_edge : t -> vertex -> vertex -> unit
      val add_edge_e : t -> edge -> unit
      val remove_edge : t -> vertex -> vertex -> unit
      val remove_edge_e : t -> edge -> unit
      type g = t
      val transitive_closure : ?reflexive:bool -> g -> g
      val add_transitive_closure : ?reflexive:bool -> g -> g
      val mirror : g -> g
      val complement : g -> g
      val intersect : g -> g -> g
      val union : g -> g -> g
      module Parallel :
        sig
          module G :
            sig
              type t = t
              module V :
                sig
                  type t = V.t
                  val compare : t -> t -> int
                  val hash : t -> int
                  val equal : t -> t -> bool
                  type label
                  val create : label -> t
                  val label : t -> label
                end
              type vertex = V.t
              module E :
                sig
                  type t
                  val compare : t -> t -> int
                  type vertex = vertex
                  val src : t -> vertex
                  val dst : t -> vertex
                  type label
                  val create : vertex -> label -> vertex -> t
                  val label : t -> label
                end
              type edge = E.t
              val is_directed : bool
              val is_empty : t -> bool
              val nb_vertex : t -> int
              val nb_edges : t -> int
              val out_degree : t -> vertex -> int
              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
              val find_all_edges : t -> vertex -> vertex -> edge list
              val succ : t -> vertex -> vertex list
              val pred : t -> vertex -> vertex list
              val succ_e : t -> vertex -> edge list
              val pred_e : t -> vertex -> edge list
              val fold_vertex : (vertex -> '-> 'a) -> t -> '-> 'a
              val iter_edges : (vertex -> vertex -> unit) -> t -> unit
              val fold_edges :
                (vertex -> vertex -> '-> 'a) -> t -> '-> 'a
              val iter_edges_e : (edge -> unit) -> t -> unit
              val fold_edges_e : (edge -> '-> 'a) -> t -> '-> 'a
              val map_vertex : (vertex -> vertex) -> t -> t
              val iter_pred : (vertex -> unit) -> t -> vertex -> unit
              val fold_succ : (vertex -> '-> 'a) -> t -> vertex -> '-> 'a
              val fold_pred : (vertex -> '-> 'a) -> t -> vertex -> '-> 'a
              val iter_succ_e : (edge -> unit) -> t -> vertex -> unit
              val fold_succ_e : (edge -> '-> 'a) -> t -> vertex -> '-> 'a
              val iter_pred_e : (edge -> unit) -> t -> vertex -> unit
              val fold_pred_e : (edge -> '-> 'a) -> t -> vertex -> '-> 'a
              val create : ?size:int -> unit -> t
              val clear : t -> unit
              val copy : t -> t
              val add_vertex : t -> vertex -> unit
              val remove_vertex : t -> vertex -> unit
              val add_edge : t -> vertex -> vertex -> unit
              val add_edge_e : t -> edge -> unit
              val remove_edge : t -> vertex -> vertex -> unit
              val remove_edge_e : t -> edge -> unit
              val iter_vertex : (V.t -> unit) -> t -> unit
              val iter_succ : (V.t -> unit) -> t -> V.t -> unit
              val in_degree : t -> V.t -> int
              val has_cycle : t -> bool
              val scc_list : t -> V.t list list
              val string_of_vertex : V.t -> string
            end
          val iter :
            int ->
            G.t ->
            pre:(G.V.t -> unit) ->
            child:(G.V.t -> unit) -> post:(G.V.t -> unit) -> unit
          val iter_l :
            int ->
            G.vertex list ->
            pre:(G.V.t -> unit) ->
            child:(G.V.t -> unit) -> post:(G.V.t -> unit) -> unit
          val map_reduce :
            int ->
            G.t ->
            map:(G.V.t -> 'a) -> merge:('-> '-> 'a) -> init:'-> 'a
          val map_reduce_l :
            int ->
            G.vertex list ->
            map:(G.V.t -> 'a) -> merge:('-> '-> 'a) -> init:'-> 'a
          val create : G.V.t list -> G.t
          exception Errors of (G.V.t * OpamParallel.error) list * G.V.t list
          exception Cyclic of G.V.t list list
        end
      module Topological :
        sig
          val iter : (package OpamTypes.action -> unit) -> t -> unit
          val fold : (package OpamTypes.action -> '-> 'a) -> t -> '-> 'a
        end
      type solution = {
        to_remove : package list;
        to_process : t;
        root_causes : (package * package OpamTypes.cause) list;
      }
      val dump_solution : solution -> unit
    end
  val dependencies : Cudf.universe -> Cudf.package list -> Cudf.package list
  val reverse_dependencies :
    Cudf.universe -> Cudf.package list -> Cudf.package list
  val get_final_universe :
    Cudf.universe ->
    Cudf_types.vpkg OpamTypes.request ->
    (Cudf.universe, Algo.Diagnostic.reason list) OpamTypes.result
  val actions_of_diff :
    OpamCudf.Diff.universe -> Cudf.package OpamTypes.action list
  val solution_of_actions :
    simple_universe:Cudf.universe ->
    complete_universe:Cudf.universe ->
    Cudf.package OpamTypes.action list -> OpamCudf.ActionGraph.solution
  val resolve :
    Cudf.universe ->
    Cudf_types.vpkg OpamTypes.request ->
    (Cudf.package OpamTypes.action list, Algo.Diagnostic.reason list)
    OpamTypes.result
  val remove :
    Cudf.universe -> Cudf_types.pkgname -> Cudf_types.constr -> Cudf.universe
  val uninstall_all : Cudf.universe -> Cudf.universe
  val install : Cudf.universe -> Cudf.package -> Cudf.universe
  val remove_all_uninstalled_versions_but :
    Cudf.universe -> string -> Cudf_types.constr -> Cudf.universe
  val s_reinstall : string
  val s_installed_root : string
  val string_of_vpkgs : Cudf_types.vpkg list -> string
  val string_of_reason :
    (Cudf.package -> OpamTypes.package) ->
    OpamTypes.universe -> Algo.Diagnostic.reason -> string option
  val string_of_reasons :
    (Cudf.package -> OpamTypes.package) ->
    OpamTypes.universe -> Algo.Diagnostic.reason list -> string
  val string_of_atom : Cudf_types.vpkg -> string
  val string_of_request : Cudf_types.vpkg OpamTypes.request -> string
  val string_of_universe : Cudf.universe -> string
  val string_of_packages : Cudf.package list -> string
  val external_solver_available : unit -> bool
end