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.
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:
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:
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.