sig
  module type ANY_TYPE = sig type t end
  module type ORDERED_TYPE =
    sig
      type t
      val compare : Sig.ORDERED_TYPE.t -> Sig.ORDERED_TYPE.t -> int
    end
  module type ORDERED_TYPE_DFT =
    sig type t val compare : t -> t -> int val default : t end
  module type HASHABLE =
    sig
      type t
      val hash : Sig.HASHABLE.t -> int
      val equal : Sig.HASHABLE.t -> Sig.HASHABLE.t -> bool
    end
  module type COMPARABLE =
    sig
      type t
      val compare : Sig.COMPARABLE.t -> Sig.COMPARABLE.t -> int
      val hash : Sig.COMPARABLE.t -> int
      val equal : Sig.COMPARABLE.t -> Sig.COMPARABLE.t -> bool
    end
  module type VERTEX =
    sig
      type t
      val compare : t -> t -> int
      val hash : t -> int
      val equal : t -> t -> bool
      type label
      val create : Sig.VERTEX.label -> Sig.VERTEX.t
      val label : Sig.VERTEX.t -> Sig.VERTEX.label
    end
  module type EDGE =
    sig
      type t
      val compare : Sig.EDGE.t -> Sig.EDGE.t -> int
      type vertex
      val src : Sig.EDGE.t -> Sig.EDGE.vertex
      val dst : Sig.EDGE.t -> Sig.EDGE.vertex
      type label
      val create :
        Sig.EDGE.vertex -> Sig.EDGE.label -> Sig.EDGE.vertex -> Sig.EDGE.t
      val label : Sig.EDGE.t -> Sig.EDGE.label
    end
  module type G =
    sig
      type t
      module V : VERTEX
      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 = Sig.G.E.t
      val is_directed : bool
      val is_empty : Sig.G.t -> bool
      val nb_vertex : Sig.G.t -> int
      val nb_edges : Sig.G.t -> int
      val out_degree : Sig.G.t -> Sig.G.vertex -> int
      val in_degree : Sig.G.t -> Sig.G.vertex -> int
      val mem_vertex : Sig.G.t -> Sig.G.vertex -> bool
      val mem_edge : Sig.G.t -> Sig.G.vertex -> Sig.G.vertex -> bool
      val mem_edge_e : Sig.G.t -> Sig.G.edge -> bool
      val find_edge : Sig.G.t -> Sig.G.vertex -> Sig.G.vertex -> Sig.G.edge
      val find_all_edges :
        Sig.G.t -> Sig.G.vertex -> Sig.G.vertex -> Sig.G.edge list
      val succ : Sig.G.t -> Sig.G.vertex -> Sig.G.vertex list
      val pred : Sig.G.t -> Sig.G.vertex -> Sig.G.vertex list
      val succ_e : Sig.G.t -> Sig.G.vertex -> Sig.G.edge list
      val pred_e : Sig.G.t -> Sig.G.vertex -> Sig.G.edge list
      val iter_vertex : (Sig.G.vertex -> unit) -> Sig.G.t -> unit
      val fold_vertex : (Sig.G.vertex -> 'a -> 'a) -> Sig.G.t -> 'a -> 'a
      val iter_edges :
        (Sig.G.vertex -> Sig.G.vertex -> unit) -> Sig.G.t -> unit
      val fold_edges :
        (Sig.G.vertex -> Sig.G.vertex -> 'a -> 'a) -> Sig.G.t -> 'a -> 'a
      val iter_edges_e : (Sig.G.edge -> unit) -> Sig.G.t -> unit
      val fold_edges_e : (Sig.G.edge -> 'a -> 'a) -> Sig.G.t -> 'a -> 'a
      val map_vertex : (Sig.G.vertex -> Sig.G.vertex) -> Sig.G.t -> Sig.G.t
      val iter_succ :
        (Sig.G.vertex -> unit) -> Sig.G.t -> Sig.G.vertex -> unit
      val iter_pred :
        (Sig.G.vertex -> unit) -> Sig.G.t -> Sig.G.vertex -> unit
      val fold_succ :
        (Sig.G.vertex -> 'a -> 'a) -> Sig.G.t -> Sig.G.vertex -> 'a -> 'a
      val fold_pred :
        (Sig.G.vertex -> 'a -> 'a) -> Sig.G.t -> Sig.G.vertex -> 'a -> 'a
      val iter_succ_e :
        (Sig.G.edge -> unit) -> Sig.G.t -> Sig.G.vertex -> unit
      val fold_succ_e :
        (Sig.G.edge -> 'a -> 'a) -> Sig.G.t -> Sig.G.vertex -> 'a -> 'a
      val iter_pred_e :
        (Sig.G.edge -> unit) -> Sig.G.t -> Sig.G.vertex -> unit
      val fold_pred_e :
        (Sig.G.edge -> 'a -> 'a) -> Sig.G.t -> Sig.G.vertex -> 'a -> 'a
    end
  module type P =
    sig
      type t
      module V : VERTEX
      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 -> 'a) -> t -> 'a -> 'a
      val iter_edges : (vertex -> vertex -> unit) -> t -> unit
      val fold_edges : (vertex -> vertex -> 'a -> 'a) -> t -> 'a -> 'a
      val iter_edges_e : (edge -> unit) -> t -> unit
      val fold_edges_e : (edge -> 'a -> 'a) -> t -> 'a -> '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 -> '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 empty : t
      val add_vertex : t -> vertex -> t
      val remove_vertex : t -> vertex -> t
      val add_edge : t -> vertex -> vertex -> t
      val add_edge_e : t -> edge -> t
      val remove_edge : t -> vertex -> vertex -> t
      val remove_edge_e : t -> edge -> t
    end
  module type I =
    sig
      type t
      module V : VERTEX
      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 -> 'a) -> t -> 'a -> 'a
      val iter_edges : (vertex -> vertex -> unit) -> t -> unit
      val fold_edges : (vertex -> vertex -> 'a -> 'a) -> t -> 'a -> 'a
      val iter_edges_e : (edge -> unit) -> t -> unit
      val fold_edges_e : (edge -> 'a -> 'a) -> t -> 'a -> '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 -> '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
      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
    end
  module type WEIGHT =
    sig
      type edge
      type t
      val weight : Sig.WEIGHT.edge -> Sig.WEIGHT.t
      val compare : Sig.WEIGHT.t -> Sig.WEIGHT.t -> int
      val add : Sig.WEIGHT.t -> Sig.WEIGHT.t -> Sig.WEIGHT.t
      val zero : Sig.WEIGHT.t
    end
  module type MARK =
    sig
      type graph
      type vertex
      val clear : Sig.MARK.graph -> unit
      val get : Sig.MARK.vertex -> int
      val set : Sig.MARK.vertex -> int -> unit
    end
  module type IM =
    sig
      type t
      module V : VERTEX
      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 -> 'a) -> t -> 'a -> 'a
      val iter_edges : (vertex -> vertex -> unit) -> t -> unit
      val fold_edges : (vertex -> vertex -> 'a -> 'a) -> t -> 'a -> 'a
      val iter_edges_e : (edge -> unit) -> t -> unit
      val fold_edges_e : (edge -> 'a -> 'a) -> t -> 'a -> '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 -> '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
      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
      module Mark :
        sig
          type graph = t
          type vertex = vertex
          val clear : graph -> unit
          val get : vertex -> int
          val set : vertex -> int -> unit
        end
    end
end