Search code examples
javagraphjgrapht

JGraphT: All paths of a given length that terminate in a specified vertex

I am using JGraphT and am looking for a way to compute all incoming paths to a vertex of a specific length. For example, given a directed graph:

A -> B

B -> C

D -> E

E -> C

F -> C

I am looking for some function function(node, k) that gives me all paths that are k edges long that terminate in node (e.g., for the above graph, function(C, 2) should give (A, B, C), (D, E, C)). Does such functionality exist out-of-the-box in the library, or do I need to write an algorithm myself?

Thanks in advance!

I've tried going through the API documentation, and found functions that allow me to compute paths between two nodes, not all paths incoming to one node.

EDIT: Clarified question per Joris' feedback.

Solution

  • The easiest approach is to simply use a shortest path algorithm.

    Graph<Integer,DefaultEdge> graph = ...; //whatever graph you like
//Create a new shortest path algorithm with limited radius
DijkstraShortestPath dsp = new DijkstraShortestPath<>(graph, 2.0);
SingleSourcePaths<Integer,DefaultEdge> paths = dsp.getPaths(targetVertex);

    Note that the above code finds all paths starting from targetVertex. In your example, you seem to have a directed graph with arcs pointing towards vertex C. You would either have to specify the graph as undirected, or revert the arc directions to make this work out-of-the-box.

    Various other solutions exist as well, but I wouldn't use them unless you have a good reason to do so:

    • compute an all pairs shortest path using the Floyd-Warshall algorithm. Iterate over all vertices in your graph, query the distance to your target vertex, and if it's meets your distance k, then you can query the corresponding path.

    • Similar to the first shortest path approach, if you change the directions of the arcs, you can also run a breadth-first-search (BFS) from the targetVertex. Iterate over all vertices, query their depth in the BFS tree (see getDepth(.) method. If a vertex is at the desired depth k, you can backtrack the tree to the root node.

    • The shortest path approaches or the BFS approach only give you a single path per vertex. There might exist multiple paths. E.g. if your graph had the following paths: (A,B,C) and (A,D,C), then only one would be returned. If you are interested in all paths into targetVertex of a specific length, you would have to implement a simple dynamic program that generates all paths of length k to the targetVertex by traversing arcs backwards.