傳遞閉包和等價類

Question

我想問關於等價類中的傳遞閉包和排序問題。

我有一個布爾矩陣，我想要的結果是，從布爾矩陣，我計算傳遞閉包，找到等價類（es），並命令所有這些等價類（es）。

例如：我有一個曲線圖

0 <-> 1 
     | 
     v 
     2 

我有2個等價類{{0; 1}; {2}}，並且對該類進行排序的結果是：{2}在類{0; 1}

1）我想更多地瞭解爲什麼從傳遞閉包我可以找到等價類？你能舉個例子嗎？我很容易理解的例子。

2）下面是一個例子。我與我的算法描述上述

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;; 

具有這些功能equivalence_classes和sort_equivalence_classes從測試：Asking about return type, list and set data structure in OCaml

我不明白，爲什麼功能eq輸出和sort是相同的， 和這裏兩種功能的輸出：[[3; 1; 0]; [1]];我不明白爲什麼它給了我這個結果，以及2在哪裏？我怎麼能得到我預期的結果？

非常感謝您

Answer 1

在您的示例transClo​​sure功能不改變矩陣。這對你的例子來說是正確的，但你應該用更多的輸入來測試這個函數，以瞭解它是否有效。

一個錯誤是equivalence_class函數假定所有關係都是對稱的，只檢查一個方向。如果它看到i - > j它也假設爲j - > i。 這不適用於您的數據，因此您會得到不正確的結果。您的矩陣示例具有0-> 1，2-> 0，2-> 1和2-> 3的關係。沒有周期，所以不應該生成等價類。一旦你有循環，傳遞閉包應該將它們轉換爲自反對稱子集。

另一個問題是你的關係不是自反的，但你需要反身性來獲得單身等價集合。

所以爲了得到這個工作，你需要1）使關係自反，2）修正equivalence_class函數來檢查兩個方向。