Re: [Caml-list] Compute the equivalence classes

[Ly Kim Quyen <lykimq@gmail.com>]

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

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 <dofp.ocaml@gmail.com
> 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
>

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