From mboxrd@z Thu Jan  1 00:00:00 1970
Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105])
	by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id pA1HtRkA031670
	for <caml-list@sympa-roc.inria.fr>; Tue, 1 Nov 2011 18:55:27 +0100
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AjYBADAysE5KfVK2kGdsb2JhbABDqEl0CCIBAQEBCQkNBxQEIYFyAQEBAwESAhMZARsdAQMBCwYFBAc7IgERAQUBHAY1h2CYOgqLVIJghQo9iHACBQqIfQSUD40zPYNw
X-IronPort-AV: E=Sophos;i="4.69,439,1315173600"; 
   d="scan'208";a="115990928"
Received: from mail-wy0-f182.google.com ([74.125.82.182])
  by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 01 Nov 2011 18:55:25 +0100
Received: by wyg36 with SMTP id 36so1127959wyg.27
        for <caml-list@inria.fr>; Tue, 01 Nov 2011 10:55:25 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=gamma;
        h=mime-version:in-reply-to:references:date:message-id:subject:from:to
         :cc:content-type;
        bh=x+7COqiiVpVLujGXgWADy3k5s5jFG4TQrmjrTR2quVU=;
        b=L3PG6zWmf2sV6GB42TYEdAm3ViO6qJ4msJSAlnIdDwKU2qxWV9S22mR/lm3vKtGUSj
         GKjdx4AKskiPAW0kA0PR8SjhpiM5mktBXlUWIXHTh6ldZbp7Utvb/O4qkL3Y0i2LCYZI
         YEjW+XJwOK/9y9xnYfl/jw+1A+pLGbvZ1d1j8=
MIME-Version: 1.0
Received: by 10.216.208.169 with SMTP id q41mr4752451weo.64.1320170124834;
 Tue, 01 Nov 2011 10:55:24 -0700 (PDT)
Received: by 10.216.17.137 with HTTP; Tue, 1 Nov 2011 10:55:24 -0700 (PDT)
In-Reply-To: <CAHqiZ-+T=7nep4TmUuzzYu0qMpO908TmegwaNCg7f--+4PVeGw@mail.gmail.com>
References: <CAHrFk+vEoS+1PoKm=PR4EBko0Ot8osuNVpk9EO4JLL-fu7mm6w@mail.gmail.com>
	<CAHqiZ-+T=7nep4TmUuzzYu0qMpO908TmegwaNCg7f--+4PVeGw@mail.gmail.com>
Date: Tue, 1 Nov 2011 18:55:24 +0100
Message-ID: <CAHqiZ-Jg36Tu-4zgXe9M1dUMqQQ-NJwjKt2LO0Oo-N_EFc4-+w@mail.gmail.com>
From: Diego Olivier Fernandez Pons <dofp.ocaml@gmail.com>
To: Ly Kim Quyen <lykimq@gmail.com>
Cc: caml-list@inria.fr
Content-Type: multipart/alternative; boundary=0016e6dee8dc5576a704b0b00f71
Subject: Re: [Caml-list] Compute the equivalence classes


--0016e6dee8dc5576a704b0b00f71
Content-Type: text/plain; charset=ISO-8859-1

... sorry, sent too early

> You can compute the strongly connected components directly on the
transitive closure. Notice you don't need to transpose it explicitely

// Strong connected components matrix form
let sccmatrix = function matrix ->
  let n = Array.length matrix in
  let result = Array.make_matrix n n 0 in
  for i = 0 to n - 1 do
      for j = 0 to n - 1 do
          result.(i).(j) <- min matrix.(i).(j) matrix.(j).(i)
      done;
  done;
  result

Now you just have to collect the results in a list of lists.
You will need to avoid generating multiple times the same component.

// Output list of lists from matrix
let output = function matrix ->
    let n = Array.length matrix in
    let marked = Array.make n false in
    let result = ref [] in
    for i = 0 to n - 1 do
        if (not marked.(i)) then
        begin
            let component = ref [i] in
            for j = i + 1 to n - 1 do
                if matrix.(i).(j) = 1 then
                begin
                     marked.(j) <- true;
                     component := j :: !component
                end
            done;
            result := !component :: !result
         end
     done;
     !result

Since the code uses for loops, it needs references to store the results.

One can do a nicer code and merge the two functions sccmatrix and output

        Diego Olivier

--0016e6dee8dc5576a704b0b00f71
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

... sorry, sent too early<div><br></div><div><div>&gt; You can compute the =
strongly connected components directly on the transitive closure. Notice yo=
u don&#39;t need to transpose it explicitely</div></div><div><br></div><div>
// Strong connected components matrix form</div><div><div>let sccmatrix =3D=
 function matrix -&gt;</div><div>=A0 let n =3D Array.length matrix in</div>=
<div>=A0 let result =3D Array.make_matrix n n 0 in</div><div>=A0 for i =3D =
0 to n - 1 do</div>
<div>=A0 =A0 =A0 for j =3D 0 to n - 1 do</div><div>=A0 =A0 =A0 =A0 =A0 resu=
lt.(i).(j) &lt;- min matrix.(i).(j) matrix.(j).(i)</div><div>=A0 =A0 =A0 do=
ne;</div><div>=A0 done;=A0</div><div>=A0 result</div><br></div><div>Now you=
 just have to collect the results in a list of lists.</div>
<div>You will need to avoid generating multiple times the same component.</=
div><div><br></div><div>// Output list of lists from matrix</div><div>let o=
utput =3D function matrix -&gt;</div><div>=A0 =A0 let n =3D Array.length ma=
trix in</div>
<div>=A0 =A0 let marked =3D Array.make n false in</div><div>=A0 =A0 let res=
ult =3D ref [] in</div><div>=A0 =A0 for i =3D 0 to n - 1 do</div><div>=A0 =
=A0 =A0 =A0 if (not marked.(i)) then</div><div>=A0 =A0 =A0 =A0 begin</div><=
div>=A0 =A0 =A0 =A0 =A0 =A0 let component =3D ref [i] in</div>
<div>=A0 =A0 =A0 =A0 =A0 =A0 for j =3D i + 1 to n - 1 do</div><div>=A0 =A0 =
=A0 =A0 =A0 =A0 =A0 =A0 if matrix.(i).(j) =3D 1 then</div><div>=A0 =A0 =A0 =
=A0 =A0 =A0 =A0 =A0 begin</div><div>=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0=
 =A0marked.(j) &lt;- true;</div><div>=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =
=A0 =A0component :=3D j :: !component</div>
<div>=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 end</div><div>=A0 =A0 =A0 =A0 =A0 =A0 =
done;</div><div>=A0 =A0 =A0 =A0 =A0 =A0 result :=3D !component :: !result</=
div><div>=A0 =A0 =A0 =A0 =A0end</div><div>=A0 =A0 =A0done; =A0 =A0=A0</div>=
<div>=A0 =A0 =A0!result</div><div><br></div><div>Since the code uses for lo=
ops, it needs references to store the results.</div>
<div><br></div><div>One can do a nicer code and merge the two functions scc=
matrix and output</div><div><br></div><div>=A0 =A0 =A0 =A0 Diego Olivier</d=
iv>

--0016e6dee8dc5576a704b0b00f71--