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

For further reference see Wikipedia page

• 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

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