我一直在寻找一种算法来对图执行可传递减少，但没有成功。我的算法圣经《算法导论》（Cormen等人著）中没有相关内容，虽然我看到了很多转换闭包的伪代码，但我没有能够找到任何关于减少的内容。我找到的最接近的是在Volker Turau的《Algorithmische Graphentheorie》（ISBN:978-3-486-59057-9）中有一种算法，但不幸的是我没有这本书的访问权限！维基百科没有提供帮助，谷歌也没有找到任何相关信息 :^( 请问是否有人知道执行可传递减少的算法？
8个回答
21
参见Harry Hsu. "An algorithm for finding a minimal equivalent graph of a digraph.", Journal of the ACM, 22(1):11-16, January 1975。下面的简单立方体算法（使用N x N路径矩阵）可以满足DAGs的要求，但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;
- Alan Donovan
4
（对于DAG）换句话说：查看每条边（i，j），如果有不在传递闭包中的理由，则删除它。未被删除的边必须在传递闭包内。 - galath
7根据您引用的参考资料，您应该从路径矩阵开始，而不是邻接矩阵。 - Michael Clerx
6并不是所有情况都适用。在一个有边(A,B), (B,C), (C,D) and (A,D)的图中，最后一条边(A,D)应该被删除。但事实上没有任何一组由两条边(m[i][j]和m[j][k])组成的路径能够从A到达D。 - Renze de Waal
1@MichaelClerx非常正确，我是指路径矩阵。感谢您指出错误。如果您有一个邻接矩阵，请先应用Warshall算法来使其具有传递闭包性质。 - Alan Donovan
8
我使用的传递减少算法的基本要点是：
我在同一脚本中使用的传递闭包算法非常相似，但最后一行不同：
对于图中的每个顶点x
对于图中的每个顶点y
对于图中的每个顶点z
如果边xy和yz存在，则删除边xz
我在同一脚本中使用的传递闭包算法非常相似，但最后一行不同：
add edge xz if edges xy and yz OR edge xz exist
- i alarmed alien
6
1你需要在
delete edge... 前添加 if (x,z) != (x,y) && (x,z) != (y,z) 来避免在出现循环的情况下进行错误的删除。除此之外，虽然拥有更快的线性时间算法会更好，但我喜欢这个答案：简单而明了。 - Joey Adams1此外，如果图中存在环，该算法不总是会产生最小的传递闭包。例如，在
[0,1,2,3,4,5]上尝试，其中A指向所有A和B的B（即使它们相同）。它应该产生类似于0->1->2->3->4->5->0的东西，但运行此算法（使用我的调整）还会带来5->2和5->4，除了0->...->5->0之外。不使用我的调整运行它将不会产生任何边缘。 - Joey Adams2我应该声明一下，我的代码包括了您提到的相同边缘的检查，并且我仅使用DAGs进行工作，因此循环不是问题。 - i alarmed alien
你确定你的传递闭包算法没问题吗？对于这个任务，我会使用 Floyd-Warshall 算法，其代码为
foreach y in graph.vertices: foreach x in graph.vertices: foreach z in graph.vertices: add edge xz if edges xy and yz exist OR edge xz exist。请注意 x 和 y 的顺序不同。我以为顺序很重要，但实际上不是吗？ - galath8如 cmn 所述，该算法会清除连接通过一条具有两个以上边的路径也相互连接的节点之间的边。例如：A -> B -> C -> D；A -> C；A -> D。算法将清除 A -> C，但不会清除 A -> D。 - Penz
我在这里实现了可传递性缩减算法，包括@JoeyAdams的附加“if”条件，但有时会产生不正确（而不仅仅是次优）的结果。我有一个DAG（没有循环！）被毁坏的案例：V2→V1，V3→V1，V4→V1，V5→V1，V6→V1，V2→V3，V2→V4，V2→V5，V6→V2，V3→V4，V3→V5，V6→V3，V4→V5，V6→V4，V6→V5被缩减为V5→V1，V6→V1，V2→V3，V6→V2，V3→V4，V4→V5，V6→V4，而正确的结果应该是V5→V1，V2→V3，V6→V2，V3→V4，V4→V5。那么这个算法有什么问题，我在哪里可以找到一个正确的算法，既适用于循环的有向图，也适用于无环的有向图？ - kriegaex
6
根据Alan Donovan提供的参考，应该使用路径矩阵（如果从节点i到节点j有路径，则为1）而不是邻接矩阵（仅当从节点i到节点j有边时才为1）。
下面是一些示例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
- Michael Clerx
5
我感到困惑，因为如果按正确的顺序删除边缘，则可以通过将算法应用于路径矩阵来回到原始（冗余）邻接矩阵。所以基本上你什么也没做。看这个例子：http://i.imgur.com/fbt6oK1.png 假设你从只有黑色边开始，当然你想消除虚线黑/绿边。因此，您添加红色边缘以获取路径矩阵。然后您删除红色边缘，因为它们都可以通过算法删除。现在你卡住了。 - Rag
使用 m = [[0, 1, 0, 1], [0, 0, 1, 0], [0, 0, 0, 1], [0, 0, 0, 0]] 作为输入正常工作 :) - Michael Clerx
我认为只要你不倒霉，先删除哪些边都可以正常工作。 - Rag
尝试一下，顺序无关紧要。 - Michael Clerx
好的，抱歉，你是对的，我找不到任何情况下在两个红边之前去除点状黑/绿边的情况。今晚回家后，我会尝试弄清楚为什么会发生这种情况。 - Rag
4
- Eric
2
感谢您（有点晚了！）的回复。最后，我给一本算法书的作者发送了电子邮件，并询问他是否可以验证我编写的某些伪代码是否正确，他很友善地做了。 - i alarmed alien
3
伪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产生的结果非常相似。
- Penz
3
"girlwithglasses"算法忽略了冗余边可以跨越三条边的链。 为了纠正这个问题，计算Q = R x R +，其中R +是传递闭包，然后删除所有在Q中出现的R中的边。 参见维基百科文章。
- cmh
2
1你能为这个提供一些伪代码吗？下面发布的传递约简算法将在传递闭包图上运行，因此对于一条边x-y，它也可以通过x-A-B-y到达，你还会有x-A-y和x-B-y。 - i alarmed alien
1Q代表什么？你要用它做什么？ - Rag
0
这个页面上的Python示例（@Michael Clerx）已经移植到Java / JGraphT中：
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
- cthiebaud
2
1提供信息，一个重新编写版本的拉取请求已经提交、接受并合并到jgrapht中。https://github.com/jgrapht/jgrapht/commit/474db1fdc197ac253f1e543c7b087cffd255118e - cthiebaud
请注意，如果图形包含循环，则JGraphT中的算法将无法正常工作，请参见[问题＃667]（https://github.com/jgrapht/jgrapht/issues/667）。您可以检查一下其中的问题吗？ - kriegaex
0
这里有一个借鉴了NetworkX库的Python实现。其中使用了两个函数，一个是拓扑排序用于检测循环，另一个是深度优先搜索用于找到从起始顶点可达的所有顶点。所有这些功能都可以在没有任何依赖的情况下实现，我在我的GitHub上有一个完整的实现。然而，它是在一个私有仓库中，所以我将完整模块的内容复制粘贴在这里。
有关改进算法效率的详细讨论，请参阅this。
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
有关改进算法效率的详细讨论，请参阅this。
- Abhijit Sarkar
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接