传递归约算法：伪代码？

Question

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

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

Answer 1

见哈里·许。 “一种查找有向图的最小等价图的算法。”，Journal of the 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;

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 书 的副本，并且此功能可能是书出版后添加的。但如果它在那里，那么就会有对算法的很好的描述。

Google 指出有人建议将其纳入 Boost 的一种算法 。我没有尝试阅读它，所以也许不正确？

另外，这个可能值得一看。

Answer 5

伪Python中的深度优先算法：

for vertex0 in vertices:
    done = set()
    for child in vertex0.children:
        df(edges, vertex0, child, done)

df = function(edges, vertex0, child0, done)
    if child0 in done:
        return
    for child in child0.children:
        edge.discard((vertex0, child))
        df(edges, vertex0, child, done)
    done.add(child0)

该算法不是最优的，但处理了先前解决方案的多边跨度问题。结果与 graphviz 生成的 tred 非常相似。

Answer 6

“girlwithglasses”的算法忘记了冗余边可以跨越三个边的链。要更正，请计算 Q = R x R+，其中 R+ 是传递闭包，然后删除 R 中出现在 Q 中的所有边。另请参阅维基百科文章。

Answer 7

移植到 java / jgrapht，本页上的 python 示例来自@Michael Clerx：

import java.util.ArrayList;
import java.util.List;
import java.util.Set;

import org.jgrapht.DirectedGraph;

public class TransitiveReduction<V, E> {

    final private List<V> vertices;
    final private int [][] pathMatrix;
    
    private final DirectedGraph<V, E> graph;
    
    public TransitiveReduction(DirectedGraph<V, E> graph) {
        super();
        this.graph = graph;
        this.vertices = new ArrayList<V>(graph.vertexSet());
        int n = vertices.size();
        int[][] original = new int[n][n];

        // initialize matrix with zeros
        // --> 0 is the default value for int arrays
        
        // initialize matrix with edges
        Set<E> edges = graph.edgeSet();
        for (E edge : edges) {
            V v1 = graph.getEdgeSource(edge);
            V v2 = graph.getEdgeTarget(edge);

            int v_1 = vertices.indexOf(v1);
            int v_2 = vertices.indexOf(v2);

            original[v_1][v_2] = 1;
        }
        
        this.pathMatrix = original;
        transformToPathMatrix(this.pathMatrix);
    }
    
    // (package visible for unit testing)
    static void transformToPathMatrix(int[][] matrix) {
        // compute path matrix 
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) { 
                if (i == j) {
                    continue;
                }
                if (matrix[j][i] > 0 ){
                    for (int k = 0; k < matrix.length; k++) {
                        if (matrix[j][k] == 0) {
                            matrix[j][k] = matrix[i][k];
                        }
                    }
                }
            }
        }
    }

    // (package visible for unit testing)
    static void transitiveReduction(int[][] pathMatrix) {
        // transitively reduce
        for (int j = 0; j < pathMatrix.length; j++) { 
            for (int i = 0; i < pathMatrix.length; i++) {
                if (pathMatrix[i][j] > 0){
                    for (int k = 0; k < pathMatrix.length; k++) {
                        if (pathMatrix[j][k] > 0) {
                            pathMatrix[i][k] = 0;
                        }
                    }
                }
            }
        }
    }

    public void reduce() {
        
        int n = pathMatrix.length;
        int[][] transitivelyReducedMatrix = new int[n][n];
        System.arraycopy(pathMatrix, 0, transitivelyReducedMatrix, 0, pathMatrix.length);
        transitiveReduction(transitivelyReducedMatrix);
        
        for (int i = 0; i <n; i++) {
            for (int j = 0; j < n; j++) { 
                if (transitivelyReducedMatrix[i][j] == 0) {
                    // System.out.println("removing "+vertices.get(i)+" -> "+vertices.get(j));
                    graph.removeEdge(graph.getEdge(vertices.get(i), vertices.get(j)));
                }
            }
        }
    }
}

单元测试：

import java.util.Arrays;

import org.junit.Assert;
import org.junit.Test;

public class TransitiveReductionTest {

    @Test
    public void test() {

        int[][] matrix = new int[][] {
            {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}
        };
        
        int[][] expected_path_matrix = new int[][] {
            {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}
        };
        
        int[][] expected_transitively_reduced_matrix = new int[][] {
            {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}
        };
        
        System.out.println(Arrays.deepToString(matrix) + " original matrix");

        int n = matrix.length;

        // calc path matrix
        int[][] path_matrix = new int[n][n];
        {
            System.arraycopy(matrix, 0, path_matrix, 0, matrix.length);
            
            TransitiveReduction.transformToPathMatrix(path_matrix);
            System.out.println(Arrays.deepToString(path_matrix) + " path matrix");
            Assert.assertArrayEquals(expected_path_matrix, path_matrix);
        }

        // calc transitive reduction
        {
            int[][] transitively_reduced_matrix = new int[n][n];
            System.arraycopy(path_matrix, 0, transitively_reduced_matrix, 0, matrix.length);
            
            TransitiveReduction.transitiveReduction(transitively_reduced_matrix);
            System.out.println(Arrays.deepToString(transitively_reduced_matrix) + " transitive reduction");
            Assert.assertArrayEquals(expected_transitively_reduced_matrix, transitively_reduced_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]] original 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]] path matrix
[[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]] transitive reduction

Answer 8

这是一个借鉴了 NetworkX 图书馆。其中使用的两个函数是拓扑排序（用于检测循环）和 DFS（用于查找从凝视顶点可到达的所有顶点）。所有这些都可以在没有任何依赖的情况下实现，我在我的 GitHub 上有一个完整的实现。但是，它位于私人存储库中，因此，我将模块的完整内容复制粘贴到此处。

from __future__ import annotations
from collections import defaultdict, deque
from typing import TypeVar, NamedTuple

T = TypeVar('T')


class Edge(NamedTuple):
    src: T
    dest: T


class Graph:
    def __init__(self, vertices: set[T] = None, edges: set[Edge] = None):
        self.vertices = vertices or set()
        self.edges = edges or set()
        self.adj = defaultdict(set)
        self.indegrees = defaultdict(int)
        for u, v in self.edges:
            self.vertices.add(u)
            self.vertices.add(v)
            self.adj[u].add(v)
            self.indegrees[v] += 1
        self.indegrees.update({v: 0 for v in (self.vertices - self.indegrees.keys())})

    def add_edge(self, edge: Edge) -> None:
        u, v, = edge
        self.vertices.add(u)
        self.vertices.add(v)
        self.edges.add(edge)
        self.adj[u].add(v)
        self.indegrees[v] += 1

    # Kahn's Algorithm
    def topological_sort(self) -> list[T]:
        indegrees = self.indegrees.copy()
        q = deque(node for node, degree in indegrees.items() if degree == 0)
        result = []
        while q:
            u = q.popleft()
            result.append(u)
            if u not in self.adj:
                continue
            for v in self.adj[u]:
                indegrees[v] -= 1
                if indegrees[v] == 0:
                    q.append(v)

        if len(result) != len(self.vertices):
            raise ValueError('Graph has a cycle')
        return result

    def dfs(self, start: T) -> list[Edge]:
        stack = [(None, start)]
        result = []
        visited = set()
        while stack:
            u, v = stack.pop()
            if u is not None:
                result.append(Edge(u, v))
            if v in visited or v not in self.adj:
                continue
            visited.add(v)
            for k in self.adj[v]:
                if k not in visited:
                    stack.append((v, k))
        return result

    # Input: DAG G=(V,E)
    #
    # E2 = E
    # for edge (u,v) in E2 do
    #     if there is a path from u to v in G=(V,E2) that does not use edge (u,v) then
    #         E2 = E2 - {(u,v)}   // remove edge (u,v) from E2
    #     end if
    # end for
    #
    # Output: G2=(V,E2) is the transitive reduction of G
    def transitive_reduction(self) -> Graph:
        # Throws exception if graph has a cycle.
        _ = self.topological_sort()

        tr = Graph(self.vertices)
        # descendants[v] is the list of all vertices reachable from v.
        descendants = {}
        indegrees = self.indegrees.copy()
        for u in self.vertices:
            if u not in self.adj:
                continue
            u_neighbors = self.adj[u].copy()
            for v in self.adj[u]:
                if v in u_neighbors:
                    if v not in descendants:
                        descendants[v] = {y for x, y in self.dfs(v)}
                    u_neighbors -= descendants[v]
                indegrees[v] -= 1
                if indegrees[v] == 0:
                    del indegrees[v]
            for v in u_neighbors:
                tr.add_edge(Edge(u, v))
        return tr

有关提高算法效率的详细讨论，请参阅 这个。