sig
  exception Unreachable
  module type G =
    sig
      type t
      module V : Sig.COMPARABLE
      val pred : Dominator.G.t -> V.t -> V.t list
      val succ : Dominator.G.t -> V.t -> V.t list
      val fold_vertex : (V.t -> '-> 'a) -> Dominator.G.t -> '-> 'a
      val iter_vertex : (V.t -> unit) -> Dominator.G.t -> unit
      val iter_succ : (V.t -> unit) -> Dominator.G.t -> V.t -> unit
      val nb_vertex : Dominator.G.t -> int
    end
  module type S =
    sig
      type t
      type vertex
      module S :
        sig
          type elt = vertex
          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 find : elt -> t -> elt
          val of_list : elt list -> t
        end
      type idom = Dominator.S.vertex -> Dominator.S.vertex
      type idoms = Dominator.S.vertex -> Dominator.S.vertex -> bool
      type dom_tree = Dominator.S.vertex -> Dominator.S.vertex list
      type dominators = Dominator.S.vertex -> Dominator.S.vertex list
      type dom = Dominator.S.vertex -> Dominator.S.vertex -> bool
      type sdom = Dominator.S.vertex -> Dominator.S.vertex -> bool
      type dom_frontier = Dominator.S.vertex -> Dominator.S.vertex list
      val compute_idom :
        Dominator.S.t ->
        Dominator.S.vertex -> Dominator.S.vertex -> Dominator.S.vertex
      val dominators_to_dom :
        ('-> Dominator.S.S.t) -> Dominator.S.vertex -> '-> bool
      val dominators_to_sdom :
        (Dominator.S.vertex -> Dominator.S.S.t) ->
        Dominator.S.vertex -> Dominator.S.vertex -> bool
      val dom_to_sdom :
        (Dominator.S.vertex -> Dominator.S.vertex -> bool) ->
        Dominator.S.vertex -> Dominator.S.vertex -> bool
      val dominators_to_sdominators :
        (Dominator.S.vertex -> Dominator.S.S.t) ->
        Dominator.S.vertex -> Dominator.S.S.t
      val dominators_to_idoms :
        (Dominator.S.vertex -> Dominator.S.S.t) ->
        Dominator.S.vertex -> Dominator.S.vertex -> bool
      val dominators_to_dom_tree :
        Dominator.S.t ->
        ?pred:(Dominator.S.t -> Dominator.S.vertex -> Dominator.S.vertex list) ->
        (Dominator.S.vertex -> Dominator.S.S.t) ->
        Dominator.S.vertex -> Dominator.S.S.t
      val idom_to_dom_tree :
        Dominator.S.t ->
        (Dominator.S.vertex -> Dominator.S.vertex) ->
        Dominator.S.vertex -> Dominator.S.vertex list
      val idom_to_idoms :
        Dominator.S.idom -> Dominator.S.vertex -> Dominator.S.vertex -> bool
      val compute_dom_frontier :
        Dominator.S.t ->
        Dominator.S.dom_tree ->
        Dominator.S.idom -> Dominator.S.vertex -> Dominator.S.vertex list
      val idom_to_dominators : ('-> 'a) -> '-> 'a list
      val idom_to_dom :
        (Dominator.S.vertex -> Dominator.S.vertex) ->
        Dominator.S.vertex -> Dominator.S.vertex -> bool
    end
  module Make :
    functor (G : G->
      sig
        type t = G.t
        type vertex = G.V.t
        module S :
          sig
            type elt = vertex
            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 find : elt -> t -> elt
            val of_list : elt list -> t
          end
        type idom = vertex -> vertex
        type idoms = vertex -> vertex -> bool
        type dom_tree = vertex -> vertex list
        type dominators = vertex -> vertex list
        type dom = vertex -> vertex -> bool
        type sdom = vertex -> vertex -> bool
        type dom_frontier = vertex -> vertex list
        val compute_idom : t -> vertex -> vertex -> vertex
        val dominators_to_dom : ('-> S.t) -> vertex -> '-> bool
        val dominators_to_sdom : (vertex -> S.t) -> vertex -> vertex -> bool
        val dom_to_sdom :
          (vertex -> vertex -> bool) -> vertex -> vertex -> bool
        val dominators_to_sdominators : (vertex -> S.t) -> vertex -> S.t
        val dominators_to_idoms : (vertex -> S.t) -> vertex -> vertex -> bool
        val dominators_to_dom_tree :
          t ->
          ?pred:(t -> vertex -> vertex list) ->
          (vertex -> S.t) -> vertex -> S.t
        val idom_to_dom_tree :
          t -> (vertex -> vertex) -> vertex -> vertex list
        val idom_to_idoms : idom -> vertex -> vertex -> bool
        val compute_dom_frontier :
          t -> dom_tree -> idom -> vertex -> vertex list
        val idom_to_dominators : ('-> 'a) -> '-> 'a list
        val idom_to_dom : (vertex -> vertex) -> vertex -> vertex -> bool
      end
  module type I =
    sig
      type t
      module V : Sig.COMPARABLE
      val pred : t -> V.t -> V.t list
      val succ : t -> V.t -> V.t list
      val fold_vertex : (V.t -> '-> 'a) -> t -> '-> 'a
      val iter_vertex : (V.t -> unit) -> t -> unit
      val iter_succ : (V.t -> unit) -> t -> V.t -> unit
      val nb_vertex : t -> int
      val create : ?size:int -> unit -> t
      val add_edge : t -> V.t -> V.t -> unit
    end
  module Make_graph :
    functor (G : I->
      sig
        type t = G.t
        type vertex = G.V.t
        module S :
          sig
            type elt = vertex
            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 find : elt -> t -> elt
            val of_list : elt list -> t
          end
        type idom = vertex -> vertex
        type idoms = vertex -> vertex -> bool
        type dom_tree = vertex -> vertex list
        type dominators = vertex -> vertex list
        type dom = vertex -> vertex -> bool
        type sdom = vertex -> vertex -> bool
        type dom_frontier = vertex -> vertex list
        val compute_idom : t -> vertex -> vertex -> vertex
        val dominators_to_dom : ('-> S.t) -> vertex -> '-> bool
        val dominators_to_sdom : (vertex -> S.t) -> vertex -> vertex -> bool
        val dom_to_sdom :
          (vertex -> vertex -> bool) -> vertex -> vertex -> bool
        val dominators_to_sdominators : (vertex -> S.t) -> vertex -> S.t
        val dominators_to_idoms : (vertex -> S.t) -> vertex -> vertex -> bool
        val dominators_to_dom_tree :
          t ->
          ?pred:(t -> vertex -> vertex list) ->
          (vertex -> S.t) -> vertex -> S.t
        val idom_to_dom_tree :
          t -> (vertex -> vertex) -> vertex -> vertex list
        val idom_to_idoms : idom -> vertex -> vertex -> bool
        val compute_dom_frontier :
          t -> dom_tree -> idom -> vertex -> vertex list
        val idom_to_dominators : ('-> 'a) -> '-> 'a list
        val idom_to_dom : (vertex -> vertex) -> vertex -> vertex -> bool
        type dom_graph = unit -> t
        type dom_functions = {
          idom : idom;
          idoms : idoms;
          dom_tree : dom_tree;
          dominators : dominators;
          dom : dom;
          sdom : sdom;
          dom_frontier : dom_frontier;
          dom_graph : Dominator.Make_graph.dom_graph;
        }
        val compute_dom_graph : Dominator.G.t -> dom_tree -> Dominator.G.t
        val compute_all :
          Dominator.G.t -> vertex -> Dominator.Make_graph.dom_functions
      end
end