在JGrapht中修剪有向无环图的更有效的方法？

Question

我正在寻找一种更有效的方法来修剪用JGrapht构造的有向无环图（a DAG）。

DAG表示一组网络会话之间的时间关系。会话的父会话是在子会话开始之前完成的任何会话。构建DAG相对简单，但存在大量不必要的关系。为了提高效率，我希望对DAG进行修剪，以便每个子级与最小的父级数量有直接关系（或者相反，以便每个父级具有最小的直接子级数量）。

我现在使用的剪枝实现（如下所示）是基于在Streme中找到的代码。它适用于我手工构建的所有单元测试场景。然而，在真实的数据集中，它通常是相当慢的。今天我碰到一个场景，有215个顶点，但超过22,000条边。在服务器级硬件上修剪DAG大约需要8分钟的时钟时间--对于我的直接用例来说是可以忍受的，但是对于更大的场景来说太慢了。

我相信我的问题类似于我可以对这个DAG应用什么算法中描述的问题？以及在图或树中寻找冗余边的算法。也就是说，我需要为我的DAG找到传递约简或最小表示。jgrapht似乎不包含DAG的可传递约简的直接实现，只包含可传递闭包。

我正在寻找关于如何提高下面实现效率的建议，或者可能是一个指向jgrapht的可传递约简的现有实现的指针，我可以改用它。

注意：或者，如果有一个不同的用于Java的图形库，它包含一个传递约简的本机实现，我可以切换到那个库。我对jgrapht的使用仅限于一个200行的类，因此只要接口相似，将其交换出去应该不难。要维护类接口（持久化到数据库），我需要一个DAG实现，它提供一种获取给定节点的父节点和子节点的方法--类似于JGrapht的graphs.preducessorlistof()和graphs.successorlistof()。

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import org.jgrapht.DirectedGraph;
import org.jgrapht.Graphs;
import org.jgrapht.alg.DijkstraShortestPath;

public static <V, E> void prune(DirectedGraph<V, E> dag) {
   Deque<V> todo = new ArrayDeque<V>(dag.vertexSet());
   Set<V> seen = new HashSet<V>();
   while (!todo.isEmpty()) {
       V v = todo.pop();
       if (seen.contains(v)) {
           continue;
       }
       seen.add(v);
       List<V> targets = Graphs.successorListOf(dag, v);
       for (int i = 0; i < targets.size(); i++) {
           for (int j = i; j < targets.size(); j++) {
               V vi = targets.get(i);
               V vj = targets.get(j);
               List<E> path = DijkstraShortestPath.findPathBetween(dag, vi, vj);
               if (path != null && !path.isEmpty()) {
                   E edge = dag.getEdge(v, vj);
                   dag.removeEdge(edge);
               }
           }
       }
   }
}

Answer 1

我担心你的算法不能正确处理图，例如有边（A,B）,（B,C）,（C,D）和（A,D）的图，最后一条边（A,D）没有被删除。我在类似问题传递性约简算法的答案中，在python中找到了一个正确的算法：伪代码？作者：Michael Clerx。我在这里使用jgrapht将他的python代码移植到了Java https://html" target="_blank">github.com/aequologica/dagr/blob/develop/dagr-web/src/main/Java/net/aequologica/neo/dagr/jgrapht/transitivereduction.java。

我只使用很小的图，也许这个解决方案不适用于很大的图。