algorithm - 传递归约算法 : pseudocode?

Question

我一直在寻找一种算法来对图执行传递归约，但没有成功。我的算法圣经(Cormen 等人的算法简介)中没有任何内容，虽然我已经看到了大量的传递闭包伪代码，但我无法找到任何减少的东西。我得到的最接近的是 Volker Turau 的“Algorithmische Graphentheorie”(ISBN:978-3-486-59057-9)中有一本，但不幸的是我无法访问这本书!维基百科没有帮助，谷歌也没有找到任何东西。 :^(

有人知道执行传递归约的算法吗？

Answer 1

参见 Harry Hsu。 “寻找有向图的最小等效图的算法。”，ACM 杂志，22(1):11-16，1975 年 1 月。下面的简单三次算法(使用 N x N 路径矩阵)足以满足 DAG，但 Hsu 将其推广到循环图。

// reflexive reduction
for (int i = 0; i < N; ++i)
  m[i][i] = false;

// transitive reduction
for (int j = 0; j < N; ++j)
  for (int i = 0; i < N; ++i)
    if (m[i][j])
      for (int k = 0; k < N; ++k)
        if (m[j][k])
          m[i][k] = false;