1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
(**************************************************************************)
(* *)
(* OCaml *)
(* *)
(* Pierre Chambart, OCamlPro *)
(* Mark Shinwell and Leo White, Jane Street Europe *)
(* *)
(* 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
|
