Longest path in directed acyclic graph in jgrapht library

Question

I want to find the longest path in directed (acyclic) graph. Let's say that I know starting node - sink. The path should begin from this point. I was thinking that I can set weights of edges to -1. There is many methods of finding all shortest path but you have to pass ending point. Is it possible to get the shortest path (no matter the end node)?

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) {

}
//????????????????

Let's say that I'd like to find longest path for node nr 1 (sink). So this algoritm shoud give me 1-2-3-4-5-6.

Answer 1

You can use AllDirectedPaths algorithm to resolve all paths, sort the results by path length in reverse order and get the first:

    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

I was looking for an answer to a similar question to calculate parallel build groupings in Jenkins from a DAG of Git repos. To solve it, I applied the algorithm described here and here. The code below is written in Groovy, so you'll have to convert to Java. The result is a Map of vertices to their respective max depths. From that you can get the single largest value. If instead you want to know the max depth from a specific vertex in the graph, you can first prune the graph into a subgraph rooted by your desired source vertex and then run the method below on the subgraph.

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
}