比較兩個等價類

Question

我有這個簡單的圖形：

傳遞閉包矩陣的

name -> string 
^ 
| 
v 
label 

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

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

輸出爲：

假假假
真真真
真真真正

功能比較等價類：

let cmp_classes m i j = 
    match m.(i).(j), m.(j).(i) with 
     (* same class: there is a path between i and j, and between j and i *) 
    | true, true -> 0 
     (* there is a path between i and j *) 
    | true, false -> -1 
     (* there is a path between j and i *) 
    | false, true -> 1 
     (* i and j are not compareable *) 
    | false, false -> raise Not_found 

let sort_eq_classes m = List.sort (cmp_classes m);; 

個

函數計算的等價類：

let eq_class m i = 
    let column = m.(i) 
    and set = ref [] in 
    Array.iteri begin fun j _ -> 
    if j = i || column.(j) && m.(j).(i) then 
     set := j :: !set 
    end column; 
    !set;; 

let eq_classes m = 
    let classes = ref [] in 
    Array.iteri begin fun e _ -> 
    if not (List.exists (List.mem e) !classes) then 
     classes := eq_class m e :: !classes 
    end m; 
    !classes;; 

(* compute transitive closure of given matrix *) 
let tc_xsds = transClosure matrix 
(* finding equivalence classes in transitive closure matrix *) 
let eq_xsds = eq_classes tc_xsds 
(* sorting all equivalence classes with transitive closure matrix *) 
let sort_eq_xsds = sort_eq_classes tc_xsds (List.flatten eq_xsds) 

它給我的命令：label, name, string，意味着正確的順序。

的問題是，當我與另一圖形測試，例如：

name -> string 
^ 
| 
v 
label -> int 

或

name -> int 
^ \ 
| \ 
v  v 
label string 

或

name -> string 
| 
v 
label -> int 

輸出是提高Not_found

你能幫我解釋爲什麼它不能給出正確的順序嗎？謝謝。

Answer 1

正如我在previous thread中所說的那樣，它不能給你正確的訂單，因爲在某些情況下有很多正確的訂單。

在所有三個反例中，您會如何看待string和int？一個接一個還是隨機訂單？由於它們之間沒有邊界，所以它們不具有可比性，並且您的代碼會引發Not_found異常。

解決此問題的一種方法是捕獲Not_found異常，並說沒有唯一的順序。或者更溫和的方法是返回0而不是引發異常，這意味着您不關心無比的類之間的順序。

正如@ygrek在評論中所說，使用內置的異常是一個壞主意。您應該定義專用於您的目的的自定義異常。