package / ocaml-base-compiler.4.10.0 / utils / strongly_connected_components.mli
1 (**************************************************************************)
2 (* *)
3 (* OCaml *)
4 (* *)
5 (* Pierre Chambart, OCamlPro *)
6 (* Mark Shinwell and Leo White, Jane Street Europe *)
7 (* *)
8 (* Copyright 2013--2016 OCamlPro SAS *)
9 (* Copyright 2014--2016 Jane Street Group LLC *)
10 (* *)
11 (* All rights reserved. This file is distributed under the terms of *)
12 (* the GNU Lesser General Public License version 2.1, with the *)
13 (* special exception on linking described in the file LICENSE. *)
14 (* *)
15 (**************************************************************************)
16
17 (** Kosaraju's algorithm for strongly connected components.
18
19 {b Warning:} this module is unstable and part of
20 {{!Compiler_libs}compiler-libs}.
21
22 *)
23
24 module type S = sig
25 module Id : Identifiable.S
26
27 type directed_graph = Id.Set.t Id.Map.t
28 (** If (a -> set) belongs to the map, it means that there are edges
29 from [a] to every element of [set]. It is assumed that no edge
30 points to a vertex not represented in the map. *)
31
32 type component =
33 | Has_loop of Id.t list
34 | No_loop of Id.t
35
36 val connected_components_sorted_from_roots_to_leaf
37 : directed_graph
38 -> component array
39
40 val component_graph : directed_graph -> (component * int list) array
41 end
42
43 module Make (Id : Identifiable.S) : S with module Id := Id
44