CODEWITHSUNDEEP
ocaml
Quyen
Quyen

Reputation: 1373

Transitive closure and equivalence classes

I want to ask about transitive closure and sorting in equivalence classes.

I have an boolean matrix, the result I want is that, from the boolean matrix, I compute transitive closure, find equivalence class(es), and order all these equivalence class(es).

For example: I have a graph

0 <-> 1
      |
      v
      2

I have 2 equivalence classes {{0; 1}; {2}}, and the result of sorting this class is: {2} after class {0; 1}

1) I want to understand more about why from transitive closure I can find equivalence classes ? Could you please give me an example? I am easily understand by example.

2) Here is an example. I am testing with the algorithm I describe above 

let matrix = 
[|[| false; true; false; false|];
  [| false; false; false; false|];
  [| true; true; false; true|];
  [| false; false; false; false|];
|]

(* compute a transitive closure of a matrix *)
let transClosure matrix =
  let n = Array.length matrix in
  for k = 0 to n - 1 do
    let mk = matrix.(k) in
    for i = 0 to n - 1 do
      let mi = matrix.(i) in
      for j = 0 to n - 1 do
    mi.(j) <- max mi.(j) (min mi.(k) mk.(j))
      done;
    done;
  done;
  matrix;;

(* compute transitive closure of boolean matrix *)
let tc_ma = transClosure matrix;;
(* compute equivalence classes on transitive closure*)
let eq = equivalence_classes tc_ma;;
(* sorting all equivalence classes *)
let sort = sort_equivalence_classes tc_ma eq;;

with these functions equivalence_classes and sort_equivalence_classes from: Asking about return type, list and set data structure in OCaml

I don't understand why the output of functions eq and sort are the same, and here is the output of both functions: [[3; 1; 0]; [1]]; I don't understand why it gave me this result, and where is 2? How can I have a result I expected?

Thank you very much

Upvotes: 1

Views: 1015

Answers (1)

Toby Kelsey
Toby Kelsey

Reputation: 166

In your example the transClosure function does not change the matrix. This is correct for your example but you should test this function with more inputs to understand if it works.

One error is the equivalence_class function assumes all relations are symmetric and only checks one direction. If it sees i -> j it assumes j -> i as well. This is not true of your data so you get incorrect results. Your matrix example has the relations 0->1, 2->0, 2->1 and 2->3. There are no cycles and so no equivalence classes should be generated. Once you have cycles the transitive closure should convert them to reflexive symmetric subsets.

Another problem is your relations are not reflexive, but you need reflexivity to get singleton equivalence sets.

So to get this working you need to 1) make the relations reflexive, and 2) fix the equivalence_class function to check both directions.

Upvotes: 1

Related Questions