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 pA38BCh4025112 for ; Thu, 3 Nov 2011 09:11:12 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AqQBAD9Msk7RVaE2kGdsb2JhbABEhHmkDWkIIgEBAQEJCQ0bBCGBcgEBAQMBEgIPBBkBGx0BAwELBgMCCzcCAiEBAREBBQEcBhMih2CXSwqLDUeCYIVMPYhwAgUKiACBFASIBowQijuCfj2DfA X-IronPort-AV: E=Sophos;i="4.69,448,1315173600"; d="scan'208";a="116512473" Received: from mail-fx0-f54.google.com ([209.85.161.54]) by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 03 Nov 2011 09:11:06 +0100 Received: by faar19 with SMTP id r19so2519321faa.27 for ; Thu, 03 Nov 2011 01:11:06 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type; bh=wKujH8jlmkmKeRc8r7BtjZHY+xCtcL5mVV3Y1NykH1s=; b=nnKLNPm73OMqknjSfh1g05Xb09gPzomkGRoxXtT92kJ8tV+bHK72jnKFdRycbuwfHn yHrHyOTp/gfo8jRquBA+pMMZfhVMIGKw/6sOcTj7GrpAA67N8QEXSeNfOHzpbkZ5Lf6Q tvnMiE/T0IGgbdQ/wjEb+o3V/GdDCFbV86SDM= Received: by 10.223.75.15 with SMTP id w15mr14800233faj.9.1320307866171; Thu, 03 Nov 2011 01:11:06 -0700 (PDT) MIME-Version: 1.0 Received: by 10.223.104.143 with HTTP; Thu, 3 Nov 2011 01:10:25 -0700 (PDT) In-Reply-To: References: From: Ly Kim Quyen Date: Thu, 3 Nov 2011 16:10:25 +0800 Message-ID: To: Diego Olivier Fernandez Pons Cc: caml-list@inria.fr Content-Type: multipart/alternative; boundary=0015174c19565b77f704b0d02185 Subject: Re: [Caml-list] Compute the equivalence classes --0015174c19565b77f704b0d02185 Content-Type: text/plain; charset=UTF-8 Hi Diego, Thank you very much. >>You will need to avoid generating multiple times the same component. Here is the code: 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) = true && matrix.(j).(i) = true then* begin marked.(j) <- true; component := j :: !component end done; result := !component :: !result end done; !result ;; Ly On 2 November 2011 01:55, Diego Olivier Fernandez Pons wrote: > ... 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 > --0015174c19565b77f704b0d02185 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Hi Diego,=

=
Thank you very much.=C2=A0

>>You will need to avoid generating multiple time= s the same component.

Here is the code:
=
<= div> let output =3D function matrix ->
=C2=A0 let n =3D Array.lengt= h matrix in
=C2=A0 let marked =3D Array.make n false in
=C2=A0 let result =3D ref [] in
=C2=A0 for i =3D 0 to n - 1 do
=C2=A0 =C2=A0 if (not marked.(i)) then
=C2=A0 =C2=A0 =C2=A0 begin
let component =3D ref[i] in
for j =3D i + 1= to n - 1 do
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 if matrix.(i).(j) =3D true &&= matrix.(j).(i) =3D true=C2=A0then
=C2=A0 =C2=A0 begin
=C2= =A0marked.(j) <- true;
=C2=A0component :=3D j :: !component
= =C2=A0end=
done;=
result :=3D !component :: !result
=C2=A0 =C2=A0 =C2=A0 end
=
=C2=A0 done;
=C2=A0 !result ;;

Ly
On 2 November 2011 01:55, Diego Olivier Fernandez Pons= <dofp.ocaml@g= mail.com> wrote:
... sorry, sent too early
=

> You can compute the strongly connected compon= ents directly on the transitive closure. Notice you don't need to trans= pose it explicitely

// Strong connected components matrix form
let sccmatrix =3D= function matrix ->
=C2=A0 let n =3D Array.l= ength matrix in
=C2=A0 let result =3D Array.make_matrix n n= 0 in
=C2=A0 for i =3D 0 to n - 1 do
=C2=A0 =C2=A0 =C2=A0 for j =3D 0 to n - 1 do
=C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 result.(i).(j) <- min matrix.(i).(j) matrix.= (j).(i)
=C2=A0 =C2=A0 =C2=A0 done;
=C2=A0 done;=C2=A0
=C2=A0 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 o= utput =3D function matrix ->
=C2=A0 =C2=A0 l= et n =3D Array.length matrix in
=C2=A0 =C2=A0 let marked =3D Array.make n false in
=C2= =A0 =C2=A0 let result =3D ref [] in
=C2=A0 =C2= =A0 for i =3D 0 to n - 1 do
=C2=A0 =C2=A0 =C2=A0 =C2=A0 if = (not marked.(i)) then
=C2=A0 =C2=A0 =C2=A0 =C2=A0 begin
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 let component =3D ref [i] in
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 for j =3D i + 1 to n - 1 do<= /div>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 if matrix= .(i).(j) =3D 1 then
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 begin
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0 =C2=A0 =C2=A0marked.(j) <- true;
=C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0component := =3D j :: !component
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 end
= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 done;
=C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 result :=3D !component :: !result
=C2=A0= =C2=A0 =C2=A0 =C2=A0 =C2=A0end
=C2=A0 =C2=A0 =C2=A0done; =C2=A0 = =C2=A0=C2=A0
=C2=A0 =C2=A0 =C2=A0!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 scc= matrix and output

=C2=A0 = =C2=A0 =C2=A0 =C2=A0 Diego Olivier

--0015174c19565b77f704b0d02185--