Отладка всех кодовых вычислений и сортировка классов эквивалентности

Question

У меня есть эта функция для вычисления класса эквивалентности

let eq_class m i =
  let column = m.(i)
  and set = ref [] in
  Array.iteri begin fun j l ->
    if j = i || column.(j) && m.(j).(i) then
      set := j :: !set else ignore l
  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;;

У меня есть эта функция для сравнения двух классов эквивалентности:

let cmp_classes m c c' = if c = c' then 0 else
  match c, c' with
    | i :: _, j :: _ -> if m.(i).(j) then 1 else -1
    | _ -> assert false

После того, как я использовал эту функцию, чтобы отсортировать ее с помощью List.sort

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

Моя матрица является булевой матрицей, и я рассчитал ее с помощью транзитивного замыкания.

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 tc = transClosure matrix
let eq = eq_classes tc
let sort_eq = sort_eq_classes tc eq

Я протестировал множество примеров счетчиков, чтобы протестировать все эти функции, например, с графиком (матрицей)

EDIT

матрица:

 a <-> b  c <-> d
 |          
 v          
 e

matrix_2:

a <-> b -> e -> f
|          |
v          v
h <------- g 
|          |
v          v  
u          k    

Я ввожу логическую матрицу:

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

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

вывод матрицы 1: классы эквивалентности: e d c b a

классы эквивалентности сортировки: e d c b a

вывод матрицы 2: классы эквивалентности: u h g e b a k f

Классы эквивалентности сортировки: u h k g f e b a

И результат в правильном порядке, как я ожидал. Но когда я проверяю это с моими данными, которые являются данными xsds, возникают более сложные зависимые отношения. Это выводит для меня неправильный порядок. У меня был тест с функцией преобразования в булеву матрицу из xsds, и я тестировал транзитивное замыкание, это правильно. Так что я думаю, что их ошибки в моих функциях (eq_class) или (cmp_classes).

Не могли бы вы помочь мне увидеть, что не так в этом коде?

Answer 1

Проблема в функции cmp_classes.

Из вашего исходного кода :

(* We check that if two elements are in the same equivalence class they are
   equal (0); if they have a path from i to j then i < j (-1)
   otherwise i > j (1). We assumes that: each equivalence class only
   appears once and each equivalence class contains at least one
   element. *)

let cmp_classes m c c' = if c = c' then 0 else
  match c, c' with
    | i :: _, j :: _ -> if m.(i).(j) then 1 else -1
    | _ -> assert false

Очевидно, ваш код не соответствует вашим требованиям.Можно упомянуть несколько ошибок:

1. Если m.(i).(j) = true, вы вообще не сравниваете i и j.
2. Если m.(i).(j) = false, вы полагаете, чтосравнивайте другие комбинации, кроме i и j, но здесь вы ошибочно возвращаете -1.
3. Вы сравниваете только с использованием головок c и c' и игнорируете другие элементы, пока предполагаете использоватьлюбая пара элементов в двух списках, прежде чем прийти к выводу.

В ваших небольших примерах вы получили правильные результаты, потому что классы эквивалентности часто имеют один элемент.Так как они собраны в том порядке, в котором нет пути от прежних к последующим, ваше возвращение -1, к счастью, верно.Это больше не относится к произвольному вводу из деревьев xsd.

Исправить функцию несложно, если вы можете четко определить ее.Теперь я до сих пор не знаю порядка двух классов эквивалентности без какого-либо пути, соединяющего их вместе ({a,b} и {c, d} классы в matrix).

Чтобы вам было проще протестировать исправление, приведем небольшой пример, который приведет к неправильному порядку:

 a <-> b  c <-> d
 ^     ^  ^     ^
 |     |  |     |
 e     e  e     e