сравнить два класса эквивалентности

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 в комментарии, использование встроенного исключения - плохая идея. Вы должны определить настраиваемое исключение, предназначенное для вашей цели.