Классы транзитивного замыкания и эквивалентности

Question

Я хочу спросить о транзитивном замыкании и сортировке в классах эквивалентности.

У меня есть логическая матрица, результат, который я хочу получить, состоит в том, что из логической матрицы я вычисляю транзитивное замыкание, нахожу класс (ы) эквивалентности и упорядочиваю все эти классы (ы) эквивалентности.

Например: у меня есть график

0 <-> 1
      |
      v
      2

У меня есть 2 класса эквивалентности {{0;1};{2}}, и результат сортировки этого класса: {2} после класса {0;1}

1) Я хочу понять, почему по транзитивному замыканию я могу найти классы эквивалентности?Не могли бы вы дать мне пример?Я легко понимаю на примере.

2) Вот пример.Я тестирую с помощью алгоритма, который я описал выше

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

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

(* compute transitive closure of boolean matrix *)
let tc_ma = transClosure matrix;;
(* compute equivalence classes on transitive closure*)
let eq = equivalence_classes tc_ma;;
(* sorting all equivalence classes *)
let sort = sort_equivalence_classes tc_ma eq;;

с этими функциями equivalence_classes и sort_equivalence_classes из: Запрос о типе возврата, списке и структуре данных в OCaml

Я не понимаю, почему выходные данные функций eq и sort одинаковы, а вот выходные данные обеих функций: [[3; 1; 0]; [1]];Я не понимаю, почему он дал мне этот результат, и где 2?Как получить ожидаемый результат?

Большое спасибо

Answer 1

В вашем примере функция transClosure не меняет матрицу. Это верно для вашего примера, но вы должны проверить эту функцию с большим количеством входных данных, чтобы понять, работает ли она.

Одна ошибка - это функция equalence_class, предполагающая, что все отношения симметричны, и проверяет только одно направление. Если он видит i -> j , он также принимает j -> i . Это не относится к вашим данным, поэтому вы получите неверные результаты. Ваш пример матрицы имеет отношения 0-> 1, 2-> 0, 2-> 1 и 2-> 3. Здесь нет циклов, поэтому классы эквивалентности не должны генерироваться. Если у вас есть циклы, транзитивное замыкание должно преобразовать их в рефлексивные симметричные подмножества.

Другая проблема заключается в том, что ваши отношения не рефлексивны, но вам нужна рефлексивность, чтобы получить одноэлементные множества эквивалентности.

Таким образом, чтобы это работало, вам нужно: 1) сделать отношения рефлексивными, и 2) исправить функцию эквивалентности для проверки обоих направлений.