推移閉包と等価クラス

Question

等価クラスで推移閉包とソートについて質問したいと思います。

私はブール値行列を持っていますので、ブール値行列から、推移閉包を計算し、等価クラスを見つけ、これらの等価クラスをすべて注文してください。例えば

：私は2つの等価クラス{{0を有するグラフ

0 <-> 1 
     | 
     v 
     2 

を有します。 1}; {2}}の後にこのクラスをソートした結果は{2}です。 1}

1）推移的閉包からなぜ等価クラスを見つけることができるのか、もっと理解したいですか？私に例を挙げてください。私は例で分かりやすい。

2）これは例です。ここれる機能eqの出力とsortは、 を同じである理由を私は理解していないAsking about return type, list and set data structure in OCaml

と：私はから

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上述のアルゴリズムでテストしてい両方の機能の出力：[[3; 1; 0]; [1]];なぜ私にこの結果をもたらしたのか分かりません。どこにありますか？2？どのように私は期待した結果を得ることができますか？

はあなたの例ではtransClo​​sure関数が行列を変更しない非常に

Answer 1

、ありがとうございました。これはあなたの例にあてはまりますが、それが機能するかどうかを理解するために、この関数をより多くの入力でテストする必要があります。

1つのエラーは、equivalence_class関数がすべての関係が対称であり、一方向のみをチェックすることです。 i - > jの場合は、j - > iと仮定します。 これはデータには当てはまらないため、誤った結果が得られます。あなたの行列の例は、0 - > 1、2 - > 0,2 - > 1、2 - > 3という関係を持っています。サイクルがないため、等価クラスを生成する必要はありません。サイクルが完了したら、トランジショナルクロージャはそれらを反射的な対称サブセットに変換する必要があります。

あなたのリレーションシップは反射的ではありませんが、シングルトン同値セットを取得するには反射性が必要です。

この作業を行うには、1）関係を反射的にし、2）両方向を確認するためにequivalence_class関数を修正する必要があります。