Module org.jgrapht.core

Package org.jgrapht.alg.shortestpath

Class SuurballeKDisjointShortestPaths<V,E>

java.lang.Object

org.jgrapht.alg.shortestpath.BaseKDisjointShortestPathsAlgorithm<V,E>

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 BaseKDisjointShortestPathsAlgorithm<V,E>

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.

Field Summary

Fields

Modifier and Type	Field	Description
private ShortestPathAlgorithm.SingleSourcePaths<V,E>	singleSourcePaths

Fields inherited from class org.jgrapht.alg.shortestpath.BaseKDisjointShortestPathsAlgorithm

originalGraph, pathList, workingGraph

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method	Description
protected GraphPath<V,E>	calculateShortestPath(V startVertex, V endVertex)	Calculates the shortest paths for the current iteration.
protected void	transformGraph(List<E> previousPath)	Prepares the working graph for next iteration.

Methods inherited from class org.jgrapht.alg.shortestpath.BaseKDisjointShortestPathsAlgorithm

getPaths

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

singleSourcePaths

private ShortestPathAlgorithm.SingleSourcePaths<V,E> singleSourcePaths

Constructor Details

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 Details

transformGraph

protected void transformGraph(List<E> previousPath)

Description copied from class: BaseKDisjointShortestPathsAlgorithm

Prepares the working graph for next iteration. To be called from the second iteration and on so implementation may assume a preceding BaseKDisjointShortestPathsAlgorithm.calculateShortestPath(V, V) call.

Specified by:

transformGraph in class BaseKDisjointShortestPathsAlgorithm<V,E>

Parameters:

previousPath - the path found at the previous iteration.

calculateShortestPath

protected GraphPath<V,E> calculateShortestPath(V startVertex,
 V endVertex)

Description copied from class: BaseKDisjointShortestPathsAlgorithm

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

Specified by:

calculateShortestPath in class BaseKDisjointShortestPathsAlgorithm<V,E>

Parameters:

startVertex - the start vertex

endVertex - the end vertex

Returns:

the shortest path between start and end vertices.