functor
  (G : Sig.IM) (W : sig
                      type edge = G.E.t
                      type t
                      val weight : edge -> t
                      val compare : t -> t -> int
                      val add : t -> t -> t
                      val zero : t
                    end->
  sig
    type t
    module V :
      sig
        type t = G.V.t
        val compare : t -> t -> int
        val hash : t -> int
        val equal : t -> t -> bool
        type label = G.V.label
        val create : label -> t
        val label : t -> label
      end
    type vertex = V.t
    module E :
      sig
        type t = G.E.t
        val compare : t -> t -> int
        type vertex = G.vertex
        val src : t -> vertex
        val dst : t -> vertex
        type label = G.E.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
    module Mark :
      sig
        type graph = t
        type vertex = vertex
        val clear : graph -> unit
        val get : vertex -> int
        val set : vertex -> int -> unit
      end
    exception Negative_cycle of G.E.t list
  end