Jgrapht库中有向无环图的最长路径

Question

我想找到定向(acyclic(图的最长路径。假设我知道启动节点 - 下沉。路径应从这一点开始。我以为我可以将边缘的权重设置为-1。有许多方法可以找到所有最短路径，但是您必须通过终点。是否有可能获得最短路径(无论端节点如何(？

DirectedAcyclicGraph graph = new DirectedAcyclicGraph<Integer, DefaultEdge>(DefaultEdge.class);
graph.addVertex(1);
graph.addVertex(2);
graph.addVertex(3);
graph.addVertex(4);
graph.addVertex(5);
graph.addVertex(6);
graph.addVertex(7);
graph.addVertex(8);
try {
    graph.addDagEdge(1, 2);
    graph.addDagEdge(2, 3);
    graph.addDagEdge(3, 4);
    graph.addDagEdge(5, 6);
graph.addDagEdge(2, 7);
graph.addDagEdge(7, 8);
} catch(Exception e) {
}
//????????????????

假设我想找到节点NR 1(接收器(的最长路径。因此，这个算法shoud给我1-2-3-4-5-6。

Answer 1

我正在寻找一个类似问题的答案，以从git存储库中计算詹金斯中的平行构建组。为了解决它，我应用了此处和此处描述的算法。下面的代码是用Groovy编写的，因此您必须转换为Java。结果是到其各自的最大深度的顶点地图。由此，您可以获得最大的价值。相反，如果您想知道图表中特定顶点的最大深度，则可以首先将图表修剪成由所需的源顶点扎根的子图，然后在子绘图上运行下面的方法。

>

def calcDepths(g) {    
    Map<String, Integer> vertexToDepthMap = new HashMap<>()
    Iterator<String> iterator = new TopologicalOrderIterator<String, DefaultEdge>(g)
    iterator.each { v ->
        Set<String> predecessors = Graphs.predecessorListOf(g, v).toSet()
        Integer maxPredecessorDepth = -1
        predecessors.each { predecessor ->
            maxPredecessorDepth = Math.max(maxPredecessorDepth, vertexToDepthMap.get(predecessor))
        }
        vertexToDepthMap.put(v, maxPredecessorDepth + 1)
    }
    return vertexToDepthMap
}

Answer 2

您可以使用alldirectedpaths算法来解析所有路径，按照路径长度以相反顺序对结果进行排序，然后获得第一个：

    AllDirectedPaths<String, DefaultEdge> paths = new AllDirectedPaths<String, DefaultEdge>(graph);
    GraphPath<String, DefaultEdge> longestPath = paths.getAllPaths(source, target, true, null)
        .stream()
        .sorted((GraphPath<String, DefaultEdge> path1, GraphPath<String, DefaultEdge> path2)-> new Integer(path2.getLength()).compareTo(path1.getLength()))
        .findFirst().get();
    System.out.println(longestPath.getLength() +  " " + longestPath);