Re: [Caml-list] Compute the equivalence classes

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

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

... 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

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