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

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

вывод матрицы транзитивного замыкания:

false false false false
true true true
true true true

функция сравнения классов эквивалентности:

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

Как я уже говорил в предыдущей теме , он не может дать вам правильный заказ, потому что в некоторых случаях есть много правильных заказов.

Во всех трех контрпримерах, что вы ожидаете от порядка string и int? Один за другим или просто случайный порядок? Поскольку между ними нет граней, они несопоставимы, и ваш код вызывает исключение Not_found.

Один из способов решения этой проблемы - перехватить исключение Not_found и сказать, что уникального ордера не существует. Или более мягкий способ - просто вернуть 0 вместо возбуждения исключения, что означает, что вам не важен порядок между несравненными классами.

Как сказал @ygrek в комментарии, использование встроенного исключения - плохая идея. Вы должны определить пользовательское исключение, предназначенное для вашей цели.