java - 在 jgrapht 中修剪有向无环图的更有效方法？

Question

我正在寻找一种更有效的方法来修剪在 jgrapht 中构建的有向无环图 (DAG) .

DAG 表示一组网络对话之间的时间关系。对话的 parent 是在子对话开始之前完成的任何对话。构造DAG比较简单，但是有很多不必要的关系。为了提高效率，我想修剪 DAG，以便每个 child 都与最少数量的 parent 有直接关系(或者相反，所以每个 parent 都有最少数量的直接 child )。

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

我相信我的问题类似于 What algorithm can I apply to this DAG? 中描述的问题和 Algorithm for Finding Redundant Edges in a Graph or Tree .也就是说，我需要找到 transitive reduction 或我的 DAG 的最小表示。 jgrapht 似乎不包含 DAG 的传递归约的直接实现，仅包含传递闭包。

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

注意:或者，如果有不同的 Java 图形库包含传递归约的 native 实现，我可以切换到该库。我对 jgrapht 的使用仅限于一个 200 行的类，因此只要界面相似，将其换出应该不难。为了维护类接口(interface)(保存到数据库)，我需要一个 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

我担心您的算法无法正确处理图形，例如边 (A,B)、(B,C)、(C,D) 和 (A,D)，最后一条边 (A,D) 不是删除。我在类似问题的答案中找到了python中正确的算法transitive reduction algorithm: pseudocode?迈克尔·克莱克斯。我在这里使用 jgrapht 将他的 python 代码移植到 java https://github.com/aequologica/dagr/blob/develop/dagr-web/src/main/java/net/aequologica/neo/dagr/jgrapht/TransitiveReduction.java .

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