[Caml-list] Compute the equivalence classes

[Caml-list] Compute the equivalence classes

[Ly Kim Quyen]

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

Dear group,

I have an question about data structure and types. I have a function calculates
transitive closure of relation represented as an adjacency matrix

let trans_closure (m: 'a array array) : 'a array array =
  let last_cols = length m - 1 in
    for k = 0 to last_cols do
      for i = 0 to last_cols do
for j = 0 to last_cols do
  m.(i).(j) <- m.(i).(j) || (m.(i).(k) && m.(k).(j))
done;
      done;
  done;
  m
;;

(* transpose matrix A is the matrix A' formed by turning rows into
   columns and vice versa: (A')i,j = Aj,i.*)
let transpose (m: 'a array array) : 'a array array =
  let tc = trans_closure m in
  let last_cols = length m - 1 in
  for i = 0 to last_cols do
    for j = 0 to last_cols do
      tc.(j).(i) <- tc.(i).(j)
    done;
  done;
  tc
;;

I would like to compute equivalence classes, it is disjoint between matrix
transitive closure  and matrix transpose. I would like it returns for me a
new list with the type: list of list [[]]

I have a function convert 'a array array to 'a list list

let to_list (m : 'a array array) : 'a list list =
  List.map to_list (to_list m)

let eq_class (m: 'a array array) : 'a list list =
  let lst = length m - 1 in
      for i = 0 to lst do
for j = 0 to lst do
  let a = tc.(i).(j) && trans.(i).(j) in
            if a
            then
           ???

I'm stuck here, I don't know how I can add the result "a" into the new list
of list. I think I should create a new list with type 'a list list, but I
don't know where I should write it?

Thank you for helping me understand and give me some advises.

Best regards,
Gwen

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

Re: [Caml-list] Compute the equivalence classes

[Kakadu]

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

maybe

let eq_class tc trans : 'a list list =
  let ans = (* create result matrix here *) in
  let lst = length m - 1 in
      for i = 0 to lst do
for j = 0 to lst do
  let a = tc.(i).(j) && trans.(i).(j) in
            if a
            then ans.(i).(j) <- ...
            else ....
        done
       done;
     to_list ans
;;

If I have understanded correctly.....


---------------
Kakadu


On Mon, Oct 31, 2011 at 7:36 PM, Ly Kim Quyen <lykimq@gmail.com> wrote:

> Dear group,
>
> I have an question about data structure and types. I have a function calculates
> transitive closure of relation represented as an adjacency matrix
>
> let trans_closure (m: 'a array array) : 'a array array =
>   let last_cols = length m - 1 in
>     for k = 0 to last_cols do
>       for i = 0 to last_cols do
> for j = 0 to last_cols do
>   m.(i).(j) <- m.(i).(j) || (m.(i).(k) && m.(k).(j))
> done;
>       done;
>   done;
>   m
> ;;
>
> (* transpose matrix A is the matrix A' formed by turning rows into
>    columns and vice versa: (A')i,j = Aj,i.*)
> let transpose (m: 'a array array) : 'a array array =
>   let tc = trans_closure m in
>   let last_cols = length m - 1 in
>   for i = 0 to last_cols do
>     for j = 0 to last_cols do
>       tc.(j).(i) <- tc.(i).(j)
>     done;
>   done;
>   tc
> ;;
>
> I would like to compute equivalence classes, it is disjoint between matrix
> transitive closure  and matrix transpose. I would like it returns for me a
> new list with the type: list of list [[]]
>
> I have a function convert 'a array array to 'a list list
>
> let to_list (m : 'a array array) : 'a list list =
>   List.map to_list (to_list m)
>
> let eq_class (m: 'a array array) : 'a list list =
>   let lst = length m - 1 in
>       for i = 0 to lst do
> for j = 0 to lst do
>   let a = tc.(i).(j) && trans.(i).(j) in
>             if a
>             then
>            ???
>
> I'm stuck here, I don't know how I can add the result "a" into the new
> list of list. I think I should create a new list with type 'a list list,
> but I don't know where I should write it?
>
> Thank you for helping me understand and give me some advises.
>
> Best regards,
> Gwen
>

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

Re: [Caml-list] Compute the equivalence classes

[Toby Kelsey]

On 31/10/11 15:36, Ly Kim Quyen wrote:
> Dear group,
> 
> I have an question about data structure and types. I have a function calculates
> transitive closure of relation represented as an adjacency matrix
> 
> let trans_closure (m: 'a array array) : 'a array array =
>   let last_cols = length m - 1 in
>     for k = 0 to last_cols do
>       for i = 0 to last_cols do
> for j = 0 to last_cols do
>   m.(i).(j) <- m.(i).(j) || (m.(i).(k) && m.(k).(j))
> done;
>       done;
>   done;
>   m
> ;;

I may have misunderstood how you are using this, but I'm not sure this finds the transitive closure since you iterate over k just once in one direction. You might need to repeat this until no more relations are found.
Since you're using logical operators on elements, your 'a type must be boolean (unless you override the operators).

> (* transpose matrix A is the matrix A' formed by turning rows into
>    columns and vice versa: (A')i,j = Aj,i.*)
> let transpose (m: 'a array array) : 'a array array =
>   let tc = trans_closure m in
>   let last_cols = length m - 1 in
>   for i = 0 to last_cols do
>     for j = 0 to last_cols do
>       tc.(j).(i) <- tc.(i).(j)
>     done;
>   done;
>   tc
> ;;

This visits each position twice and is not symmetric, so for example
(a b)
(c d)
becomes
(a b)
(b d)

To transpose you want to visit each non-diagonal entry once and swap, I.E. (untested):
  for i = 0 to last_cols-1 do
    for j = i+1 to last_cols do
      let tmp = tc.(i).(j) in
      begin
        tc.(i).(j) <- tc.(j).(i);
        tc.(j).(i) <- tmp
      end
    done;
  done;

> I would like to compute equivalence classes, it is disjoint between matrix
> transitive closure  and matrix transpose. I would like it returns for me a
> new list with the type: list of list [[]]
> 
> I have a function convert 'a array array to 'a list list
> 
> let to_list (m : 'a array array) : 'a list list =
>   List.map to_list (to_list m)
> 
> let eq_class (m: 'a array array) : 'a list list =
>   let lst = length m - 1 in
>       for i = 0 to lst do
> for j = 0 to lst do
>   let a = tc.(i).(j) && trans.(i).(j) in
>             if a
>             then
>            ???
> 
> I'm stuck here, I don't know how I can add the result "a" into the new list
> of list. I think I should create a new list with type 'a list list, but I
> don't know where I should write it?

How do you want to represent your equivalence class?  You could have a list of (i,j) pairs for each class, or perhaps a more complex data structure. Once you choose the data structure that will help determine what you need to do.
In any case looping once over the matrix probably can't compute it. You will have to follow the equivalence relations to find all equivalent entries, so you might need a recursive 'flood-fill' style algorithm to find all the entries.

> Thank you for helping me understand and give me some advises.
> 
> Best regards,
> Gwen

Regards,
Toby

Re: [Caml-list] Compute the equivalence classes

[Diego Olivier Fernandez Pons]

[-- 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 --]

Re: [Caml-list] Compute the equivalence classes

[Diego Olivier Fernandez Pons]

[-- 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 --]

Re: [Caml-list] Compute the equivalence classes

[Ly Kim Quyen]

[-- 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 --]