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

Question

我想在有向（无环）图中找到最长的路径。假设我知道起始节点-汇。路径应该从这一点开始。我在想我可以将边的权重设置为-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（汇）找到最长路径。所以这个算法给了我1-2-3-4-5-6。

Answer 1

您可以使用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);

Answer 2

我正在寻找一个类似问题的答案，以从Git存储库的DAG计算Jenkins中的并行构建分组。为了解决这个问题，我应用了这里和这里描述的算法。下面的代码是用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
}