Re: [Caml-list] Compute the equivalence classes

[Diego Olivier Fernandez Pons <dofp.ocaml@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 951 bytes --]

    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

[-- Attachment #2: Type: text/html, Size: 1380 bytes --]