(**************************************************************************)
(*                                                                        *)
(*                                 OCaml                                  *)
(*                                                                        *)
                          , OCamlPro                        
              and   ,                 
(*                                                                        *)
(*   Copyright 2013--2016 OCamlPro SAS                                    *)
    Copyright 2014 - -2016 Jane Street Group LLC                           
(*                                                                        *)
(*   All rights reserved.  This file is distributed under the terms of    *)
    the GNU Lesser General Public License version 2.1 , with the          
(*   special exception on linking described in the file LICENSE.          *)
(*                                                                        *)
(**************************************************************************)

* Kosaraju 's algorithm for strongly connected components .

module type S = sig
  module Id : sig
    type t

    module Map : Map.S with type key = t

    module Set : Set.S with type elt = t
  end

  type directed_graph = Id.Set.t Id.Map.t
  (** If (a -> set) belongs to the map, it means that there are edges
      from [a] to every element of [set].  It is assumed that no edge
      points to a vertex not represented in the map. *)

  type component =
    | Has_loop of Id.t list
    | No_loop of Id.t

  val connected_components_sorted_from_roots_to_leaf : directed_graph -> component array

  val component_graph : directed_graph -> (component * int list) array
end

module Make (Id : sig
  type t

  module Map : Map.S with type key = t

  module Set : Set.S with type elt = t
end) : S with module Id = Id

************************************************************************
                                                                        
                                 OCaml                                  
                                                                        
                                                                        
   Copyright 2013--2016 OCamlPro SAS                                    
                                                                        
   All rights reserved.  This file is distributed under the terms of    
   special exception on linking described in the file LICENSE.          
                                                                        
************************************************************************
* If (a -> set) belongs to the map, it means that there are edges
      from [a] to every element of [set].  It is assumed that no edge
      points to a vertex not represented in the map. 
                          , OCamlPro                        
              and   ,                 
    Copyright 2014 - -2016 Jane Street Group LLC                           
    the GNU Lesser General Public License version 2.1 , with the          

* Kosaraju 's algorithm for strongly connected components .

module type S = sig
  module Id : sig
    type t

    module Map : Map.S with type key = t

    module Set : Set.S with type elt = t
  end

  type directed_graph = Id.Set.t Id.Map.t

  type component =
    | Has_loop of Id.t list
    | No_loop of Id.t

  val connected_components_sorted_from_roots_to_leaf : directed_graph -> component array

  val component_graph : directed_graph -> (component * int list) array
end

module Make (Id : sig
  type t

  module Map : Map.S with type key = t

  module Set : Set.S with type elt = t
end) : S with module Id = Id
