fr.inria.opengve.bridge.algorithms.common.shortestPath
Class KShortestPaths<V,E extends Link<V>,G extends Graph<V,E>>

java.lang.Object
  java.util.Observable
      fr.inria.opengve.bridge.algorithms.StepAlgo<V,E>
          fr.inria.opengve.bridge.algorithms.common.shortestPath.KShortestPaths<V,E,G>

All Implemented Interfaces:

java.lang.Runnable

public abstract class KShortestPaths<V,E extends Link<V>,G extends Graph<V,E>>
extends StepAlgo<V,E>

This class solve the problem of k-shortest path (not disjoint). It uses the algorithm found in the book "Routing, Flow and Capacity Design in Communication and Computer Networks" by michal Pioro and Deepankar.

The algorithm is based on the paper: C. J. McCallum, An Algorithm for finding the k shortest paths in a network. Bell laboratories, Technical Memorandum, 1973; M. M. B. Pascoal, V. Captivo, and J. C. N. Climaco, An algorithm for ranking quickest simple paths, Computers & Operations Research, 2003. The original idea is from: J. Y. Yen, Finding the k shortest loopless paths in a network, Management Science, 17:712-716, 1971.

This algorithm uses DijkstraAdvanced to compute the shortest paths. It reads the lenght (or weight) of arcs getting a value stored in a AbstractScalar. The value used to compute path weight is load from the map passed as constructor argument. You can set the name (setDistanceContext(Object)) and the context (setDistanceContext(Object)) used to load this value.

When the computation is done, you can ask the number of found paths (which is inferior or equal to requested number of paths) with the method numberOfComputedPaths(). Then, you can get the paths with getShortestPath(int). If the requested k-th path does not exist, it will return a null pointer.

Author:

fabrice.peix@sophia.inria.fr

Nested Class Summary

Nested classes/interfaces inherited from class fr.inria.opengve.bridge.algorithms.StepAlgo

StepAlgo.StepAlgoMessage, StepAlgo.StepAlgoMessageType

Field Summary

int	numberOfComputedPaths The current number of computed paths.

Constructor Summary

KShortestPaths(G g, Map distance)
Constructor of KShortestPaths.

KShortestPaths(G g, Map distance, boolean stepMode)
This constructor permit to specify the stepMode of the algorithm.

Method Summary

void	computeShortestPath(V s, V t, int k) Compute k shortest path between s and t.
protected abstract CopyGraph<V,E,G>	createCopyGraph() Create a new copy tool.
protected abstract DijkstraAdvanced<V,E,G>	createDijkstraAdvanced(G g, V destination) Create an algorithms that compute shortest path between source and destination.
protected abstract Path<V,E>	createPath() Create a new path.
double	getDistance(int k) Returns the weight of the k-th path.
Path<V,E>	getShortestPath(int k) Return the k-th path computed.
int	numberOfComputedPaths() Return the number of computed paths.
void	run() Runs the computation of k shortests paths between s and t.
void	setDistanceContext(java.lang.Object context) Set the context used to load distance of edges in the map.
void	setDistanceName(java.lang.String name) Set the name used to load distance of edges in the map.
void	setEndsOfPath(V s, V t) Set the ends of computed paths.
void	setInfiniteDistance(AbstractScalar infinite) Set the distance used as infinite.
void	setNumberOfComputedPath(int k) Set the number of paths that must be computed.

Methods inherited from class fr.inria.opengve.bridge.algorithms.StepAlgo

ends, getDemoMode, getStepMode, isEnded, nextStep, notifyGraphDisplayRequest, notifyGraphDisplayRequest, notifyLabelEdgesRequest, notifyLabelVerticesRequest, pause, setPauseMode, setTime, start

Methods inherited from class java.util.Observable

addObserver, clearChanged, countObservers, deleteObserver, deleteObservers, hasChanged, notifyObservers, notifyObservers, setChanged

Methods inherited from class java.lang.Object

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

Field Detail

numberOfComputedPaths

public int numberOfComputedPaths

The current number of computed paths.

Constructor Detail

KShortestPaths

public KShortestPaths(G g,
                      Map distance)

Constructor of KShortestPaths.

Parameters:

g - the graph on which we search paths.

distance - the map storing weight of each edges.

KShortestPaths

public KShortestPaths(G g,
                      Map distance,
                      boolean stepMode)

This constructor permit to specify the stepMode of the algorithm.

Parameters:

g - the graph to use to find paths.

distance - the map storing weight of each edges.

stepMode - The stepMode of the algorithms.

Method Detail

createDijkstraAdvanced

protected abstract DijkstraAdvanced<V,E,G> createDijkstraAdvanced(G g,
                                                                  V destination)

Create an algorithms that compute shortest path between source and destination.

Parameters:

g - The graph.

destination - The destination of the path.

Returns:

An implementation of DijkstraAdvanced.

createCopyGraph

protected abstract CopyGraph<V,E,G> createCopyGraph()

Create a new copy tool.

Returns:

The newly created copyGraph.

createPath

protected abstract Path<V,E> createPath()

Create a new path.

Returns:

A path.

setDistanceName

public void setDistanceName(java.lang.String name)

Set the name used to load distance of edges in the map. By default this name is "distance".

Parameters:

name - The new name used to load distance of edges in the map.

setDistanceContext

public void setDistanceContext(java.lang.Object context)

Set the context used to load distance of edges in the map. By default the graph is used.

Parameters:

context - The new context.

setInfiniteDistance

public void setInfiniteDistance(AbstractScalar infinite)

Set the distance used as infinite.

Parameters:

infinite - The new infinite distance.

setNumberOfComputedPath

public void setNumberOfComputedPath(int k)

Set the number of paths that must be computed.

Parameters:

k - The number of path that must be computed.

setEndsOfPath

public void setEndsOfPath(V s,
                          V t)

Set the ends of computed paths.

Parameters:

s - The first vertex of computed path in directed graph and one of two ends in undirected one.

t - The last vertex of computed path in directed graph and one of two ends in undirected one.

computeShortestPath

public void computeShortestPath(V s,
                                V t,
                                int k)

Compute k shortest path between s and t.

Parameters:

s - The begining of paths. Only sense with directed graph.

t - The end of paths. Only sense with directed graph.

k - The number of paths that msut be computed.

run

public void run()

Runs the computation of k shortests paths between s and t.

Specified by:

run in interface java.lang.Runnable

Specified by:

run in class StepAlgo<V,E extends Link<V>>

getShortestPath

public Path<V,E> getShortestPath(int k)

Return the k-th path computed. Start at k=0 (the first path). If there is no k-th path, it returns null.

Parameters:

k - the number of the path (start at 0).

Returns:

the k-th path.

numberOfComputedPaths

public int numberOfComputedPaths()

Return the number of computed paths.

Returns:

the number of computed paths.

getDistance

public double getDistance(int k)

Returns the weight of the k-th path. Starts at k=0.

Returns:

Returns the weight of k-th path.