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 pA1HKInD030560
	for <caml-list@sympa-roc.inria.fr>; Tue, 1 Nov 2011 18:20:18 +0100
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AlABAOoosE5KfVI0kGdsb2JhbABCnmaDAgGGMoEiCCIBAQEBCQkNBxQEIYFyAQEBBBICExkBGx0BAwwGBQQBBjsiAREBBQEcBjWHaJgzCotUgmCFCD2IcAIFCoh9BIJYkTeNMz2DcA
X-IronPort-AV: E=Sophos;i="4.69,439,1315173600"; 
   d="scan'208";a="115988463"
Received: from mail-ww0-f52.google.com ([74.125.82.52])
  by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 01 Nov 2011 18:20:12 +0100
Received: by wwn31 with SMTP id 31so3412251wwn.9
        for <caml-list@inria.fr>; Tue, 01 Nov 2011 10:20:12 -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=pbdw05b/WAYnDoiE6aonhJuf+C4e0kIedYR0GY5SR7I=;
        b=EZBSpRQvcpCGzxwJ7rDEOHsDAWSEfSFiX82hOzkP0b4wvdzq/TLX9d1eb9QfsLSktg
         pb3Bj5By1jkHhjuM+3EiKJ+3sUTf46FIxFgHo4RxzxQNXcSCAIVvYLzFonwWoUMIecjO
         bS2ujGoyIU+qmaHsw8I2HRS10WFc99f8rq9UA=
MIME-Version: 1.0
Received: by 10.216.208.169 with SMTP id q41mr4711567weo.64.1320168012141;
 Tue, 01 Nov 2011 10:20:12 -0700 (PDT)
Received: by 10.216.17.137 with HTTP; Tue, 1 Nov 2011 10:20:11 -0700 (PDT)
In-Reply-To: <CAHrFk+vEoS+1PoKm=PR4EBko0Ot8osuNVpk9EO4JLL-fu7mm6w@mail.gmail.com>
References: <CAHrFk+vEoS+1PoKm=PR4EBko0Ot8osuNVpk9EO4JLL-fu7mm6w@mail.gmail.com>
Date: Tue, 1 Nov 2011 18:20:11 +0100
Message-ID: <CAHqiZ-+T=7nep4TmUuzzYu0qMpO908TmegwaNCg7f--+4PVeGw@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=0016e6dee8dc68567504b0af91e8
Subject: Re: [Caml-list] Compute the equivalence classes


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

    Ly,

The algorithm for the transitive closure is fine. It's a typical
Floyd-Warshall algorithm

// Make a random graph
let makegraph = fun n -> Array.init n (fun _ -> Array.init n (fun _ ->
Random.int(2)))

// Compute transitive closure (in place)
let transitiveClosure = fun matrix ->
    let n = Array.length matrix in
        for k = 0 to n - 1 do
            for i = 0 to n - 1 do
                for j = 0 to n - 1 do
                    matrix.(i).(j) <- max matrix.(i).(j) (min
matrix.(i).(k) matrix.(k).(j))
                done;
            done;
        done

I guess that by "equivalence class" you mean strongly connected components.
There are linear algorithm (Tarjan, Gabow) that are variants of DFS (depht
first search) with bookkeeping
http://en.wikipedia.org/wiki/Strongly_connected_component

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

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

=A0 =A0 Ly,<div><br></div><div>The algorithm for the transitive closure is =
fine. It&#39;s a typical Floyd-Warshall algorithm</div><div><br></div><div>=
// Make a random graph</div><div><div>let makegraph =3D fun n -&gt;=A0Array=
.init n (fun _ -&gt; Array.init n (fun _ -&gt; Random.int(2)))</div>
</div><div><br></div><div>// Compute transitive closure (in place)</div><di=
v>let transitiveClosure =3D fun matrix -&gt;</div><div>=A0 =A0 let n =3D Ar=
ray.length matrix in</div><div>=A0 =A0 =A0 =A0 for k =3D 0 to n - 1 do</div=
><div>=A0 =A0 =A0 =A0 =A0 =A0 for i =3D 0 to n - 1 do</div>
<div>=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 for j =3D 0 to n - 1 do</div><div>=A0 =
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 matrix.(i).(j) &lt;- max matrix.(i).(j)=
 (min matrix.(i).(k) matrix.(k).(j))</div><div>=A0 =A0 =A0 =A0 =A0 =A0 =A0 =
=A0 done;</div><div>=A0 =A0 =A0 =A0 =A0 =A0 done;=A0</div><div>=A0 =A0 =A0 =
=A0 done=A0</div>
<div><br>I guess that by &quot;equivalence class&quot; you mean strongly co=
nnected components.</div><div>There are linear algorithm (Tarjan, Gabow) th=
at are variants of DFS (depht first search) with bookkeeping=A0<a href=3D"h=
ttp://en.wikipedia.org/wiki/Strongly_connected_component">http://en.wikiped=
ia.org/wiki/Strongly_connected_component</a></div>
<div><br></div><div>You can compute the strongly connected components direc=
tly on the transitive closure. Notice you don&#39;t need to transpose it ex=
plicitely</div><div><br></div><div>=A0</div><div><br><br><div class=3D"gmai=
l_quote">
<br></div></div>

--0016e6dee8dc68567504b0af91e8--