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