Re: [Caml-list] Compute the equivalence classes

[Toby Kelsey <toby.kelsey@gmail.com>]

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