更有效的方法来修剪一个有向无圈图在jgrapht？

Question

我正在寻找一种更有效的方法来修剪一个在杰格特中构造的有向无圈图( DAG)。

DAG代表一组及时的网络会话之间的关系。对话的父母是在孩子对话开始之前完成的任何对话。构建DAG相对简单，但是有很多不必要的关系。为了提高效率，我想修剪DAG，这样每个孩子都与最小数量的父母有直接的关系(或者相反，每个父母都有最小的直接子女数量)。

我现在使用的prune实现(如下所示)是基于在条纹中找到的代码。它适用于我手工构建的所有单元测试场景。然而，在一个真实的数据集中，它通常是相当缓慢的。我今天遇到了一个场景，有215个顶点，但有超过22000个边。修剪DAG在服务器级硬件上花费了将近8分钟的时钟时间--这对于我的直接用例来说是可以忍受的，但是对于更大的场景来说，扩展速度太慢了。

我相信我的问题类似于我能用什么算法来处理这个DAG？和图或树中冗余边的查找算法中描述的问题。也就是说，我需要找到http://en.wikipedia.org/wiki/Transitive_reduction或我的DAG的最小表示。jgrapht似乎不包含DAG传递约简的直接实现，只包含传递闭包。

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

注意:另外，如果有不同的Java图形库，其中包括传递还原的本机实现，我可以切换到该库。我对jgrapht的使用仅限于一个200行类，因此只要接口类似，交换它就不会很困难。为了维护类接口(持久化到数据库)，我需要一个DAG实现，它提供了一种获取给定节点的父节点和子节点的方法--类似于jgrapht的Graphs.predecessorListOf()和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

我担心您的算法没有正确处理图的e.g.with边(A，B)，(B，C)，(C，D)和(A，D)，最后的边(A，D)没有被删除。在Michael对类似问题传递约简算法:伪码？的回答中，我在python中找到了一个正确的算法。我在这里使用https://github.com/aequologica/dagr/blob/develop/dagr-web/src/main/java/net/aequologica/neo/dagr/jgrapht/TransitiveReduction.java将他的python代码移植到java。

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