Finding all the paths between two vertices with weight limit in a directed graph

Question

I'm trying to find all the paths between two vertices that have weight less than N in a directed weighted graph that may have loops but not self-loops. So far, I could do it only by using AllDirectedPaths and then filter out the paths that have weight bigger than N:

SimpleDirectedWeightedGraph<String, DefaultWeightedEdge> g = new SimpleDirectedWeightedGraph<>(DefaultWeightedEdge.class);
AllDirectedPaths<String, DefaultWeightedEdge> allPaths = new AllDirectedPaths<>(g);
int maxWeight = 30;
List<GraphPath<String, DefaultWeightedEdge>> pathsLimitedByWeight = allPaths.getAllPaths(startVertex, endVertex, false, maxWeight / minGraphLatency)
    .filter(graphPath -> graphPath.getWeight() < maxWeight)
    .collect(Collectors.toList());

This approach is obviously suboptimal because for larger graphs it is slow. To limit the output and make it faster, I supply maxPathLength to the AllDirectedPaths#getAllPaths, which I set to the max weight a path can have divided by a minimal weight an edge in the graph has since in my case edge weight is an integer and is always greater than 1.

I considered using KShortestSimplePaths with a custom PathValidator, but it supports only simple paths, i.e, doesn't allow loops.

What other option, if any, do I have within jgrapht that can be used to solve finding all paths without having to traverse the graph myself.

Answer 1

There is no algorithm that allows you to efficiently query all non-simple paths between a pair of vertices. There can be exponentially many paths. Imagine a graph with the following edges: (s,u),(u,v),(v,u),(u,t), where all edges have length 1. Now find all non-simple paths from s to t, with a weight limit of N. You would get the following paths:

• s,u,t
• s,u,v,u,t
• s,u,v,u,v,u,t
• s,u,v,u,v,u,v,u,t
• ....

You could continue cycling [u,v,u] until you finally hit the weight limit. If this is really what you want, I would recommend implementing a simple labeling algorithm. A label encodes a partial path. A label keeps a reference to its preceding label, a reference to the node the label is associated with, as well as a cost equal to the total cost of the partial path represented by the label. Start the algorithm by creating a label for the source node s with cost 0 and add it to a queue of open labels. During every iteration of the algorithm, poll a label from the open queue until the queue is exhausted. For a polled label L associated with node i and having cost c, expand the label: for each neighbor j of node i, create a new label L' that points back to label L and set its cost equal to c plus edge weight d_ij. If the cost of the new label L' exceeds the available budget, discard the label. Else, if j is the target node, we found a new path, so store the label such that we can recover the path later. Else, add L' to the queue of open labels. A simple implementation of this algorithm can be found below.

Notes:

1. The above labeling algorithm will only work when either the graph is relatively small, N is low, or the edge weights are high, since the number of possible paths from s to t can grow very fast.
2. The performance of the above algorithm can be slightly improved by including a admissible heuristic to compute the least amount of budget required to complete a path from a given node to the terminal. This would allow you to prune some labels.
3. All edge weights are required to be larger than 0.

import org.jgrapht.*;
import org.jgrapht.graph.*;

import java.util.*;

public class NonSimplePaths<V,E> {

    public List<GraphPath<V, E>> computeNoneSimplePaths(Graph<V,E> graph, V source, V target, double budget){
        GraphTests.requireDirected(graph); //Require input graph to be directed
        if(source.equals(target))
            return Collections.emptyList();

        Label start = new Label(null, source, 0);
        Queue<Label> openQueue = new LinkedList<>(); //List of open labels
        List<Label> targetLabels = new LinkedList<>(); //Labels associated with target node
        openQueue.add(start);

        while(!openQueue.isEmpty()){
            Label openLabel = openQueue.poll();
            for(E e : graph.outgoingEdgesOf(openLabel.node)){
                double weight = graph.getEdgeWeight(e);
                V neighbor = Graphs.getOppositeVertex(graph, e, openLabel.node);

                //Check whether extension is possible
                if(openLabel.cost + weight <= budget){
                    Label label = new Label(openLabel, neighbor, openLabel.cost + weight); //Create new label
                    if(neighbor.equals(target)) //Found a new path from source to target
                        targetLabels.add(label);
                    else //Must continue extending the path until a complete path is found
                        openQueue.add(label);
                }
            }
        }

        //Every label in the targetLabels list corresponds to a unique path. Recreate paths by backtracking labels
        List<GraphPath<V,E>> paths = new ArrayList<>(targetLabels.size());
        for(Label label : targetLabels){ //Iterate over every path
            List<V> path = new LinkedList<>();
            double pathWeight = label.cost;
            do{
                path.add(label.node);
                label=label.pred;
            }while(label != null);
            Collections.reverse(path); //By backtracking the labels, we recoved the path in reverse order
            paths.add(new GraphWalk<>(graph, path, pathWeight));
        }

       return paths;
   }

    private final class Label{
        private final Label pred;
        private final V node;
        private final double cost;

        private Label(Label pred, V node, double cost) {
            this.pred = pred;
            this.node = node;
            this.cost = cost;
        }
    }

    public static void main(String[] args){
        Graph<String,DefaultWeightedEdge> graph = new SimpleDirectedWeightedGraph<>(DefaultWeightedEdge.class);
        Graphs.addAllVertices(graph, Arrays.asList("s","u","v","t"));
        graph.addEdge("s","u");
        graph.addEdge("u","t");
        graph.addEdge("u","v");
        graph.addEdge("v","u");
        graph.edgeSet().forEach(e -> graph.setEdgeWeight(e,1.0)); //Set weight of all edges to 1

        NonSimplePaths<String,DefaultWeightedEdge> nonSimplePaths = new NonSimplePaths<>();
        List<GraphPath<String,DefaultWeightedEdge>> paths = nonSimplePaths.computeNoneSimplePaths(graph, "s", "t", 10);
        for(GraphPath<String,DefaultWeightedEdge> path : paths)
            System.out.println(path+" cost: "+path.getWeight());
    }
}

Output of the above sample code:

[s, u, t] cost: 2.0
[s, u, v, u, t] cost: 4.0
[s, u, v, u, v, u, t] cost: 6.0
[s, u, v, u, v, u, v, u, t] cost: 8.0
[s, u, v, u, v, u, v, u, v, u, t] cost: 10.0

Improving the performance of the above implementation, e.g. by adding an admissible heuristic, I leave as an exercise to the OP.