mascoptLib.algos.digraph
Class KShortestPaths

java.lang.Object
  mascoptLib.algos.digraph.KShortestPaths

public class KShortestPaths

extends Object

Author:

jflaland

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 Double. The name of the value ie "NAME_OF_VALUE". You can modifiy the static String in the class. Juste put values using setDouValue(KShortestPaths.NAME_OF_VALUE, G, 12.0). You must use the context G as the refering graph you will give to KShortestPaths.

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

Here is an example:

DiGraph G = new DiGraph(V, E); Arc eab = new Arc(a,b); eab.setValue(KShortestPath.WEIGHT, "2"); eab.setDouValue("poids", G, 2.0); KShortestPaths k_shortest = new KShortestPaths(G,5); KShortestPaths.NAME_OF_VALUE = "poids"; k_shortest.run(a,c); k_shortest.printComputedPaths();

Field Summary

static String

NAME_OF_VALUE The string used to get double values on arcs.

Constructor Summary

KShortestPaths(DiGraph g, int k)
Constructor of KShortestPaths.

Method Summary

DiPath	getShortestPath(int k) Return the k-th path computed.
double	getWeight(int k) Returns the weight of the k-th path.
int	numberOfComputedPaths() Return the number of computed paths.
void	printComputedPaths() Prints all the computed paths.
void	run(Vertex s, Vertex t) Runs the computation of k shortests paths between s and t.

Methods inherited from class java.lang.Object

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

Field Detail

NAME_OF_VALUE

public static String NAME_OF_VALUE

The string used to get double values on arcs.

Constructor Detail

KShortestPaths

public KShortestPaths(DiGraph g,
                      int k)

Constructor of KShortestPaths.

Parameters:

g - the graph to use to find paths.

k - the number of paths to find.

Method Detail

run

public void run(Vertex s,
                Vertex t)

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

getShortestPath

public DiPath 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.

printComputedPaths

public void printComputedPaths()

Prints all the computed paths.

getWeight

public double getWeight(int k)

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

Returns:

Returns the weight of k-th path.