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
|
(*
* Graph: generic graph library
* Copyright (C) 2004
* Sylvain Conchon, Jean-Christophe Filliatre and Julien Signoles
*
* This software is free software; you can redistribute it and/or
* modify it under the terms of the GNU Library General Public
* License version 2, as published by the Free Software Foundation.
*
* This software is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
*
* See the GNU Library General Public License version 2 for more details
* (enclosed in the file LGPL).
*)
(* $Id: components.mli,v 1.12 2004/10/22 14:42:06 signoles Exp $ *)
(** Strongly connected components *)
open Util
(** Minimal graph signature for [scc] *)
module type G = sig
type t
module V : Sig.COMPARABLE
val iter_vertex : (V.t -> unit) -> t -> unit
val iter_succ : (V.t -> unit) -> t -> V.t -> unit
end
module Make (G: G) : sig
val scc : G.t -> (G.V.t -> int)
(** [scc g] computes the strongly connected components of [g].
The result is a function [f] such that [f u = f v] if and only if
[u] and [v] are in the same component.
Beware: to be used efficiently, [scc] must be applied to a single
argument (the graph). *)
val scc_list : G.t -> G.V.t list list
(** [scc_list] computes the strongly connected components of [g].
The result is a partition of the set of the vertices of [g]. *)
end
|