sig
  module type G =
    sig
      type t
      module Vertex :
        sig
          type t
          val print : Format.formatter -> t -> unit
          val compare : Search.G.t -> Search.G.t -> int
        end
      module Edge :
        sig
          type t
          val print : Format.formatter -> t -> unit
          val src : Search.G.t -> Search.G.Vertex.t
          val tgt : Search.G.t -> Search.G.Vertex.t
        end
      val mem_vertex : Search.G.t -> Search.G.Vertex.t -> bool
      val iter_succ :
        (Search.G.Edge.t -> unit) -> Search.G.t -> Search.G.Vertex.t -> unit
      val fold_succ :
        (Search.G.Edge.t -> '-> 'a) ->
        Search.G.t -> Search.G.Vertex.t -> '-> 'a
      val iter_pred :
        (Search.G.Edge.t -> unit) -> Search.G.t -> Search.G.Vertex.t -> unit
      val fold_pred :
        (Search.G.Edge.t -> '-> 'a) ->
        Search.G.t -> Search.G.Vertex.t -> '-> 'a
    end
  module Make :
    functor (G : G->
      sig
        module Path :
          sig
            type t = G.Edge.t list
            val print : Format.formatter -> t -> unit
          end
        type traversal =
            Forward_path of Search.Make.Path.t
          | Backward_path of Search.Make.Path.t
          | Forward_reach of Search.G.Vertex.t list
          | Backward_reach of Search.G.Vertex.t list
        val fwd_dfs :
          Search.G.t ->
          Search.G.Vertex.t list ->
          Search.G.Vertex.t list -> Search.Make.traversal
        val fwd_bfs :
          Search.G.t ->
          Search.G.Vertex.t list ->
          Search.G.Vertex.t list -> Search.Make.traversal
        val bwd_dfs :
          Search.G.t ->
          Search.G.Vertex.t list ->
          Search.G.Vertex.t list -> Search.Make.traversal
        val bwd_bfs :
          Search.G.t ->
          Search.G.Vertex.t list ->
          Search.G.Vertex.t list -> Search.Make.traversal
      end
end