传递减少算法:伪代码？

Question

我一直在寻找一种算法来对图表进行传递减少,但没有成功.在我的算法圣经中没有任何内容(Cormen等人的算法导论),虽然我已经看到了大量的传递闭包伪代码,但我还是无法追踪任何减少的东西.我最接近的是Volker Turau的"Algorithmische Graphentheorie"中有一个(ISBN:978-3-486-59057-9),但不幸的是我无法访问这本书!维基百科是无益的,谷歌还没有发现任何东西.:^(

有谁知道用于执行传递减少的算法？

Answer 1

见Harry Hsu."用于寻找有向图的最小等价图的算法.",ACM期刊,22(1):11-16,1975年1月.下面的简单立方算法(使用N×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;

Answer 2

我使用的传递约简算法的基本要点是

foreach x in graph.vertices
   foreach y in graph.vertices
      foreach z in graph.vertices
         delete edge xz if edges xy and yz exist

我在同一个脚本中使用的传递闭包算法非常相似,但最后一行是

         add edge xz if edges xy and yz OR edge xz exist

Answer 3

基于 Alan Donovan 提供的参考资料，其中指出您应该使用路径矩阵（如果存在从节点 i 到节点 j 的路径，则该矩阵的值为 1），而不是邻接矩阵（仅当存在边时该矩阵的值为 1）从节点 i 到节点 j)。

下面是一些示例 python 代码，以显示解决方案之间的差异

def prima(m, title=None):
    """ Prints a matrix to the terminal """
    if title:
        print title
    for row in m:
        print ', '.join([str(x) for x in row])
    print ''

def path(m):
    """ Returns a path matrix """
    p = [list(row) for row in m]
    n = len(p)
    for i in xrange(0, n):
        for j in xrange(0, n):
            if i == j:
                continue
            if p[j][i]:
                for k in xrange(0, n):
                    if p[j][k] == 0:
                        p[j][k] = p[i][k]
    return p

def hsu(m):
    """ Transforms a given directed acyclic graph into its minimal equivalent """
    n = len(m)
    for j in xrange(n):
        for i in xrange(n):
            if m[i][j]:
                for k in xrange(n):
                    if m[j][k]:
                        m[i][k] = 0

m = [   [0, 1, 1, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 1, 1],
        [0, 0, 0, 0, 1],
        [0, 1, 0, 0, 0]]

prima(m, 'Original matrix')
hsu(m)
prima(m, 'After Hsu')

p = path(m)
prima(p, 'Path matrix')
hsu(p)
prima(p, 'After Hsu')

输出：

Adjacency matrix
0, 1, 1, 0, 0
0, 0, 0, 0, 0
0, 0, 0, 1, 1
0, 0, 0, 0, 1
0, 1, 0, 0, 0

After Hsu
0, 1, 1, 0, 0
0, 0, 0, 0, 0
0, 0, 0, 1, 0
0, 0, 0, 0, 1
0, 1, 0, 0, 0

Path matrix
0, 1, 1, 1, 1
0, 0, 0, 0, 0
0, 1, 0, 1, 1
0, 1, 0, 0, 1
0, 1, 0, 0, 0

After Hsu
0, 0, 1, 0, 0
0, 0, 0, 0, 0
0, 0, 0, 1, 0
0, 0, 0, 0, 1
0, 1, 0, 0, 0

Answer 4

维基百科关于传递归约的文章指出了 GraphViz（开源）中的实现。不完全是伪代码，但也许可以从某个地方开始？

LEDA 包括传递归约算法。我已经没有LEDA书的副本了，这个功能可能是在书出版后添加的。但如果它在那里，那么就会有对算法的很好的描述。

谷歌指出了有人建议将其包含在 Boost 中的算法。我没有尝试阅读它，所以也许不正确？

另外，这可能值得一看。