传递闭包和对等类 [英] Transitive closure and equivalence classes

问题描述

我想问一下等价类中的传递闭包和排序.

I want to ask about transitive closure and sorting in equivalence classes.

我有一个布尔矩阵，我想要的结果是，从布尔矩阵中，我计算传递闭包，找到等价类，并对所有这些等价类进行排序.

I have an boolean matrix, the result I want is that, from the boolean matrix, I compute transitive closure, find equivalence class(es), and order all these equivalence class(es).

例如:我有一张图

0 <-> 1
      |
      v
      2

我有2个等效类{{0; 1}; {2}}，对此类进行排序的结果是:类{0}之后的{2}； 1}

I have 2 equivalence classes {{0; 1}; {2}}, and the result of sorting this class is: {2} after class {0; 1}

1)我想更多地了解为什么从传递闭包中可以找到等价类?你能给我一个例子吗?我很容易以身作则.

1) I want to understand more about why from transitive closure I can find equivalence classes ? Could you please give me an example? I am easily understand by example.

2)这是一个示例.我正在使用上面描述的算法进行测试

2) Here is an example. I am testing with the algorithm I describe above

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，来自:

with these functions equivalence_classes and sort_equivalence_classes from: Asking about return type, list and set data structure in OCaml

我不明白为什么函数eq和sort的输出相同， 这是两个函数的输出:[[3; 1; 0]; [1]];我不明白为什么它会给我这个结果，2在哪里?我如何得到预期的结果?

I don't understand why the output of functions eq and sort are the same, and here is the output of both functions: [[3; 1; 0]; [1]]; I don't understand why it gave me this result, and where is 2? How can I have a result I expected?

非常感谢

推荐答案

在您的示例中， transClo​​sure 函数不会更改矩阵.这对于您的示例是正确的，但是您应该使用更多输入来测试此功能，以了解其是否有效.

In your example the transClosure function does not change the matrix. This is correct for your example but you should test this function with more inputs to understand if it works.

一个错误是equivalence_class函数假定所有关系都是对称的，并且仅检查一个方向.如果看到 i-> j ，则也假定为 j-> i . 您的数据并非如此，因此您将得到不正确的结果.您的矩阵示例的关系为0-> 1、2-> 0、2-> 1和2-> 3.没有循环，因此不应生成任何等效类.循环后，传递闭包应将其转换为自反对称子集.

One error is the equivalence_class function assumes all relations are symmetric and only checks one direction. If it sees i -> j it assumes j -> i as well. This is not true of your data so you get incorrect results. Your matrix example has the relations 0->1, 2->0, 2->1 and 2->3. There are no cycles and so no equivalence classes should be generated. Once you have cycles the transitive closure should convert them to reflexive symmetric subsets.

另一个问题是您的关系不是自反的，但是您需要自反才能获得单身等价集.

Another problem is your relations are not reflexive, but you need reflexivity to get singleton equivalence sets.

因此，要执行此操作，您需要1)使关系自反，2)修复equivalence_class函数以检查两个方向.

So to get this working you need to 1) make the relations reflexive, and 2) fix the equivalence_class function to check both directions.

这篇关于传递闭包和对等类的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！