比较两个等价类

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在评论中所说，使用内置的异常是一个坏主意。您应该定义专用于您的目的的自定义异常。