org.jgrapht.alg.shortestpath

Class SuurballeKDisjointShortestPaths<V,E>

• java.lang.Object
• org.jgrapht.alg.shortestpath.SuurballeKDisjointShortestPaths<V,E>
• Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
KShortestPathAlgorithm<V,E>

public class SuurballeKDisjointShortestPaths<V,E>
extends Object
An implementation of Suurballe algorithm for finding K edge-disjoint shortest paths. The algorithm determines the k disjoint shortest simple paths in increasing order of weight. Only directed simple graphs are allowed.

The algorithm is running k sequential Dijkstra iterations to find the shortest path at each step. Hence, yielding a complexity of k*O(Dijkstra).

• Suurballe, J. W.; Tarjan, R. E. (1984), A quick method for finding shortest pairs of disjoint paths.
Author:
Assaf Mizrachi
• Field Summary

Fields
Modifier and Type Field and Description
protected Graph<V,E> originalGraph
protected Set<E> overlappingEdges
protected List<List<E>> pathList
protected Graph<V,E> workingGraph
Graph on which shortest paths are searched.
• Constructor Summary

Constructors
Constructor and Description
SuurballeKDisjointShortestPaths(Graph<V,E> graph)
Creates a new instance of the algorithm.
• Method Summary

All Methods
Modifier and Type Method and Description
protected GraphPath<V,E> calculateShortestPath(V startVertex, V endVertex)
Calculates the shortest paths for the current iteration.
List<GraphPath<V,E>> getPaths(V startVertex, V endVertex, int k)
Returns the $k$ shortest simple paths in increasing order of weight.
protected void transformGraph(List<E> previousPath)
Prepares the working graph for next iteration.
• Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• Field Detail

• workingGraph

protected Graph<V,E> workingGraph
Graph on which shortest paths are searched.
• pathList

protected List<List<E>> pathList
• overlappingEdges

protected Set<E> overlappingEdges
• originalGraph

protected Graph<V,E> originalGraph
• Constructor Detail

• SuurballeKDisjointShortestPaths

public SuurballeKDisjointShortestPaths(Graph<V,E> graph)
Creates a new instance of the algorithm.
Parameters:
graph - graph on which shortest paths are searched.
Throws:
IllegalArgumentException - if the graph is null.
IllegalArgumentException - if the graph is undirected.
IllegalArgumentException - if the graph is not simple.
• Method Detail

• transformGraph

protected void transformGraph(List<E> previousPath)
Prepares the working graph for next iteration. To be called from the second iteration and on so implementation may assume a preceding calculateShortestPath(V, V) call.
Parameters:
previousPath - the path found at the previous iteration.
• calculateShortestPath

protected GraphPath<V,E> calculateShortestPath(V startVertex,
V endVertex)
Calculates the shortest paths for the current iteration. Path is not final; rather, it is intended to be used in a "post-production" phase (see resolvePaths method).
Parameters:
startVertex - the start vertex
endVertex - the end vertex
Returns:
the shortest path between start and end vertices.
• getPaths

public List<GraphPath<V,E>> getPaths(V startVertex,
V endVertex,
int k)
Returns the $k$ shortest simple paths in increasing order of weight.
Specified by:
getPaths in interface KShortestPathAlgorithm<V,E>
Parameters:
startVertex - source vertex of the calculated paths.
endVertex - target vertex of the calculated paths.
k - the number of shortest paths to return
Returns:
list of disjoint paths between the start vertex and the end vertex
Throws:
IllegalArgumentException - if the graph does not contain the startVertex or the endVertex
IllegalArgumentException - if the startVertex and the endVertex are the same vertices
IllegalArgumentException - if the startVertex or the endVertex is null