传递闭包和等价类(Transitive closure and equivalence classe

我想请教一下传递闭包和等价类排序。

我有一个布尔矩阵，结果我想要的是，从布林矩阵，我计算传递闭包，找到等价类（ES），并且为了所有这些等价类（ES）。

例如：我有一个曲线图

1}; 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]] [[3; 1; 0]; [1]] [[3; 1; 0]; [1]] ; 我不明白为什么它给了我这个结果，并在那里为2 ？我怎样才能有一个结果，我期待？

非常感谢你

在您的示例transClosure功能不改变矩阵。这是你们的榜样正确的，但你应该测试这个功能与更多的投入来了解它是否工作。

一个错误是equivalence_class函数假定所有的关系是对称的，只检查一个方向。如果它看到我- >Ĵ它假定的J - >我也是如此。所以你得到不正确的结果，这不是你的数据的真实。您的基质例如有关系0-> 1，2-> 0，2-> 1和2-> 3。有没有周期，所以没有等价类应生成。一旦你有周期的传递闭包应该将其转换为反身对称的子集。

另一个问题是，你的关系不是自反的，但你需要反思得到单同值。

因此，为了得到这个工作，你需要1）使关系自反，和2）固定equivalence_class功能检查两个方向。