/usr/lib/ocaml/ocamlgraph/components.mli is in libocamlgraph-ocaml-dev 1.8.6-1+b2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 49 50 51 52 53 54 55 56 57 | (**************************************************************************)
(* *)
(* Ocamlgraph: a generic graph library for OCaml *)
(* Copyright (C) 2004-2010 *)
(* 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.1, with the special exception on linking *)
(* described in file LICENSE. *)
(* *)
(* 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. *)
(* *)
(**************************************************************************)
(** Strongly connected components. *)
(** Minimal graph signature required by {!Make}.
Sub-signature of {!Sig.G}. *)
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
(** Functor providing functions to compute strongly connected components of a
graph. *)
module Make (G: G) : sig
val scc : G.t -> int * (G.V.t -> int)
(** [scc g] computes the strongly connected components of [g].
The result is a pair [(n,f)] where [n] is the number of
components. Components are numbered from [0] to [n-1], and
[f] is a function mapping each vertex to its component
number. In particular, [f u = f v] if and only if [u] and
[v] are in the same component. Another property of the
numbering is that components are numbered in a topological
order: if there is an arc from [u] to [v], then [f u >= f u]
Not tail-recursive.
Complexity: O(V+E)
The function returned has complexity O(1) *)
val scc_array : G.t -> G.V.t list array
(** [scc_array g] computes the strongly connected components of [g].
Components are stored in the resulting array, indexed with a
numbering with the same properties as for [scc] above. *)
val scc_list : G.t -> G.V.t list list
(** [scc_list g] computes the strongly connected components of [g].
The result is a partition of the set of the vertices of [g].
The [n]-th components is [(scc_array g).(n-1)]. *)
end
|