Re: [Caml-list] Compute the equivalence classes

[Kakadu <kakadu.hafanana@gmail.com>]

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