mascoptLib.algos.abstractalgos
Class KShortestPath

java.lang.Object
  |
  +--mascoptLib.algos.abstractalgos.KShortestPath

All Implemented Interfaces:

Runnable

public class KShortestPath

extends Object

implements Runnable

Provides a simple algorithm to find the K shortest distance between all nodes and the paths corresponding to theses nodes. We suppose that the graph contains no negative cycle (with a negative cycle, you can reduce the length of the path with no limits...)

Self-loops are allowed

This algorithm is made of three steps:
1)finding the shortest path between 2 nodes
2)erasing this path
3)finding the new shortest path between theses 2 nodes

There are two different ways of erasing a path (depending of the kind of paths we want to find : disjoint or not)

DISTANCE_MAX is a constant representing the maximum distance beetween two nodes (modelize the infinite value)
WEIGHT is a String allowing the access to the weight of an edge. It requires the edge to use the setValue method with the string KShortestPath.POIDS (equals to "poids"). You can change this value. If you use the GraphEditor software, you must put the value of the edge to poids by default.

WARNING: you may be faced with a java.lang.OutOfMemoryError with big graph. You can solve this problem by increasing the amount of memory used by the JVM. By default, 64M are used for the virtual machine. By typing "java -Xmx$$$m", you will launch the JVM with $$$M of memory, allowing to compute bigger graph.

Version:

30/08/2002

Author:

bourgoui@essi.fr

See Also:

getShortestPath

Field Summary

static String

WEIGHT

Constructor Summary

KShortestPath(mascoptLib.abstractGraph.AbstractGraph g)
Construct a KShortestPath object that compute only the first shortest path

KShortestPath(mascoptLib.abstractGraph.AbstractGraph g, int k)
Default constructor.

Method Summary

static int	getPathLength(mascoptLib.abstractGraph.AbstractPath chain) a static method to compute the length of an AbstractChain
Vector	getShortestPath(mascoptLib.abstractGraph.AbstractEdge e) allow the user to get the kshortest path for a demand request by an edge.
Vector	getShortestPath(mascoptLib.abstractGraph.AbstractVertex src, mascoptLib.abstractGraph.AbstractVertex dest) allow the user to get the kshortest path between 2 nodes.
Vector	getShortestPath(mascoptLib.abstractGraph.AbstractVertex src, mascoptLib.abstractGraph.AbstractVertex dest, int j) allow the user to get the kshortest path between 2 nodes.
int[]	getShortestPathLength(mascoptLib.abstractGraph.AbstractVertex src, mascoptLib.abstractGraph.AbstractVertex dest) allow the user to get the length of the kshortest path between 2 nodes you must have launched the run method before calling this method
int	getShortestPathLength(mascoptLib.abstractGraph.AbstractVertex src, mascoptLib.abstractGraph.AbstractVertex dest, int j) allow the user to get the length of the kshortest path between 2 nodes you must have launched the run method before calling this method
void	run() compute the k shortest path between each pairs of node
void	runNonDisjoint() compute the k shortest path between each pairs of node but the paths obtained are non-disjoint
void	write(String file) WARNING: this method is not implemented yet compute the k shortest path between each pairs of node but write the results in a file instead of writing them in memory
void	writenonDisjoint(String file) WARNING: this method is not implemented yet compute the k shortest path (non-disjoint) between each pairs of node but write the results in a file instead of writing them in memory

Methods inherited from class java.lang.Object

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

Field Detail

WEIGHT

public static final String WEIGHT

See Also:

Constant Field Values

Constructor Detail

KShortestPath

public KShortestPath(mascoptLib.abstractGraph.AbstractGraph g,
                     int k)

Default constructor. When constructed, execute the run function to compute the distances and path and then, get these results via other access method of the class.

Parameters:

g - the graph used by KShortestPath algorithm

k - the number of path we want to compute

KShortestPath

public KShortestPath(mascoptLib.abstractGraph.AbstractGraph g)

Construct a KShortestPath object that compute only the first shortest path

Parameters:

g - the graph used by KShortestPath algorithm

See Also:

KShortestPath(AbstractGraph g, int k)

Method Detail

run

public void run()

compute the k shortest path between each pairs of node

Specified by:

run in interface Runnable

getShortestPath

public Vector getShortestPath(mascoptLib.abstractGraph.AbstractVertex src,
                              mascoptLib.abstractGraph.AbstractVertex dest)

allow the user to get the kshortest path between 2 nodes. you must have launched the run method before calling this method

Parameters:

src - AbstractNode the source node

dest - AbstractNode the destination node

Returns:

java.util.Vector the k AbstractChain composing the paths

getShortestPath

public Vector getShortestPath(mascoptLib.abstractGraph.AbstractVertex src,
                              mascoptLib.abstractGraph.AbstractVertex dest,
                              int j)

allow the user to get the kshortest path between 2 nodes. you must have launched the run method before calling this method

Parameters:

src - AbstractNode the source node

dest - AbstractNode the destination node

j - int the rank of the path we want to get

Returns:

java.util.Vector the edges composing the path (a null AbstractEdge if no path)

getShortestPathLength

public int[] getShortestPathLength(mascoptLib.abstractGraph.AbstractVertex src,
                                   mascoptLib.abstractGraph.AbstractVertex dest)

allow the user to get the length of the kshortest path between 2 nodes you must have launched the run method before calling this method

Parameters:

src - AbstractNode the source node

dest - AbstractNode the destination node

Returns:

int[] the length of the paths (-1 if no path)

getShortestPathLength

public int getShortestPathLength(mascoptLib.abstractGraph.AbstractVertex src,
                                 mascoptLib.abstractGraph.AbstractVertex dest,
                                 int j)

allow the user to get the length of the kshortest path between 2 nodes you must have launched the run method before calling this method

Parameters:

src - AbstractNode the source node

dest - AbstractNode the destination node

j - int the rank of the path we want to get

Returns:

int the length of the path (-1 if no path)

getPathLength

public static int getPathLength(mascoptLib.abstractGraph.AbstractPath chain)

a static method to compute the length of an AbstractChain

Parameters:

chain - AbstractChain the path on which we want to find the length

Returns:

int the length of the path (-1 if null path)

write

public void write(String file)

WARNING: this method is not implemented yet
compute the k shortest path between each pairs of node but write the results in a file instead of writing them in memory

Parameters:

file - String the output file

writenonDisjoint

public void writenonDisjoint(String file)

WARNING: this method is not implemented yet
compute the k shortest path (non-disjoint) between each pairs of node but write the results in a file instead of writing them in memory

Parameters:

file - String the output file

runNonDisjoint

public void runNonDisjoint()

compute the k shortest path between each pairs of node but the paths obtained are non-disjoint

getShortestPath

public Vector getShortestPath(mascoptLib.abstractGraph.AbstractEdge e)

allow the user to get the kshortest path for a demand request by an edge. you must have launched the run method before calling this method the demand is an edge reaching the start node and the end node

Parameters:

e - the edge considered for the path

Returns:

java.util.Vector the k AbstractChain composing the paths (an empty Vector if no path)