drasys.or.graph.sp
Class Dijkstra

java.lang.Object
  |
  +--drasys.or.graph.sp.Dijkstra

public class Dijkstra

extends java.lang.Object

implements SingleVertexI

A single vertex shortest path implementation using Dijkstra's algorithm. This is an implementation that works well with both sparse and dense graphs but it ignores the connection properties. This algorithm finds all of the paths between a root vertex and a set of candidate vertices. This collection of paths forms a tree where the candidates that were reached from the root are leaves of the tree. The path generation can be constrained by count, length, cost, time and distance. The constraints all reduce the size of the path tree and can greatly improve performance.

References:

Introduction to Algorithms
    Thomas H. Cormen, et al / Hardcover / Published 1990
Graphs : Theory and Algorithms
    K. Thulasiraman, M.N.S. Swamy / Paperback / Published 1992

Constructor Summary

Dijkstra(GraphI graph)           A constructor that sets the target graph.

Dijkstra(GraphI graph, PriorityQueueI queue)           A constructor that sets the target graph and the 'PriorityQueueI' used by the algorithm.

 

Method Summary
java.util.Enumeration	candidates()           Creates an Enumeration on the candidate vertices that were reached in the path generation.
int	generatePathsFrom(java.lang.Object rootKey)           Creates the single source shortest path tree from the root vertex to the candidate vertices.
int	generatePathsTo(java.lang.Object rootKey)           Creates the single destination shortest path tree from the candidate vertices to the root vertex.
EdgeValueI	getEdgeValue(VertexI candidate)           Gets the edge value of the path between this candidate vertex and the root vertex.
VertexI	getNearestCandidate()           Returns the candidate vertex for the single shortest path generated.
java.util.Vector	getPath(VertexI candidate)           Creates a path Vector containing the elements in the path between the candidate vertex and the root.
java.util.Enumeration	pathElements(VertexI candidate)           Creates an Enumeration on the elements in the path from this candidate vertex to the root vertex.
void	setCandidate(boolean isCandidate)           Sets the candidate flags for all vertices.
void	setCandidate(java.lang.Object key, boolean isCandidate)           Sets the candidate flag for a specific vertex.
void	setListener(SingleVertexListenerI listener)           Sets the listener to receive the shortest path events.
void	setMaxCost(double maxCost)           Sets the maximum cost for any path.
void	setMaxDistance(double maxDistance)           Sets the maximum distance for any path.
void	setMaxLength(int maxLength)           Sets the maximum number of edges in any path.
void	setMaxPaths(int maxPaths)           Sets the maximum number of paths the the algorithm will generate.
void	setMaxTime(double maxTime)           Sets the maximum time for any path.
void	setProperties(PropertiesI properties)           Sets the properties object that is used to access vertex and edge properties.
java.lang.String	toString()
boolean	usesConnectionProperties()           Returns false because this algorithm ignores the connection properties.

 

Methods inherited from class java.lang.Object

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

 

Constructor Detail

Dijkstra

public Dijkstra(GraphI graph)

A constructor that sets the target graph.

Dijkstra

public Dijkstra(GraphI graph,
                PriorityQueueI queue)

A constructor that sets the target graph and the 'PriorityQueueI' used by the algorithm. The queue's compare function will be set to 'CompareNumberReverse'.

usesConnectionProperties

public boolean usesConnectionProperties()

Returns false because this algorithm ignores the connection properties.

Specified by:

usesConnectionProperties in interface SingleVertexI

Returns:

false

setListener

public void setListener(SingleVertexListenerI listener)

Sets the listener to receive the shortest path events. Passing a null argument disables events.

Specified by:

setListener in interface SingleVertexI

setProperties

public void setProperties(PropertiesI properties)

Sets the properties object that is used to access vertex and edge properties. If the argument is null, the algorithm behaves like it is using 'PropertiesAdapter'.

Specified by:

setProperties in interface SingleVertexI

setMaxPaths

public void setMaxPaths(int maxPaths)

Sets the maximum number of paths the the algorithm will generate. The paths generated will be the 'maxPaths' shortest paths. The default is Integer.MAX_VALUE.

Specified by:

setMaxPaths in interface SingleVertexI

setMaxLength

public void setMaxLength(int maxLength)

Sets the maximum number of edges in any path. The length of no path will be greater than this value. The default is Integer.MAX_VALUE.

Specified by:

setMaxLength in interface SingleVertexI

setMaxCost

public void setMaxCost(double maxCost)

Sets the maximum cost for any path. The cost of no path will be greater than this value. The default is Double.POSITIVE_INFINITY.

Specified by:

setMaxCost in interface SingleVertexI

setMaxTime

public void setMaxTime(double maxTime)

Sets the maximum time for any path. The time of no path will be greater than this value. The default is Double.POSITIVE_INFINITY.

Specified by:

setMaxTime in interface SingleVertexI

setMaxDistance

public void setMaxDistance(double maxDistance)

Sets the maximum distance for any path. The distance of no path will be greater than this value. The default is Double.POSITIVE_INFINITY.

Specified by:

setMaxDistance in interface SingleVertexI

setCandidate

public void setCandidate(boolean isCandidate)

Sets the candidate flags for all vertices. By default no vertices are marked as candidates.

Specified by:

setCandidate in interface SingleVertexI

setCandidate

public void setCandidate(java.lang.Object key,
                         boolean isCandidate)
                  throws VertexNotFoundException

Sets the candidate flag for a specific vertex. By default no vertices are marked as candidates.

Specified by:

setCandidate in interface SingleVertexI

generatePathsTo

public int generatePathsTo(java.lang.Object rootKey)
                    throws VertexNotFoundException,
                           InvalidPropertyException

Creates the single destination shortest path tree from the candidate vertices to the root vertex. The paths will be directed from the candidate vertices to the root vertex.

Specified by:

generatePathsTo in interface SingleVertexI

Returns:

The number of paths generated.

Throws:

VertexNotFoundException - if the root vertex key isn't in the graph.

InvalidAttributeException - if a vertex or edge attrubute is invalid for the algorithm.

generatePathsFrom

public int generatePathsFrom(java.lang.Object rootKey)
                      throws VertexNotFoundException,
                             InvalidPropertyException

Creates the single source shortest path tree from the root vertex to the candidate vertices. The paths will be directed from the root vertex to the candidate vertices.

Specified by:

generatePathsFrom in interface SingleVertexI

Returns:

The number of paths generated.

Throws:

VertexNotFoundException - if the root vertex key isn't in the graph.

InvalidAttributeException - if a vertex or edge attrubute is invalid for the algorithm.

getNearestCandidate

public VertexI getNearestCandidate()

Returns the candidate vertex for the single shortest path generated.

Specified by:

getNearestCandidate in interface SingleVertexI

Returns:

Null if no paths were found.

candidates

public java.util.Enumeration candidates()

Creates an Enumeration on the candidate vertices that were reached in the path generation. The candidates are returned in order of the nearest first.

Specified by:

candidates in interface SingleVertexI

pathElements

public java.util.Enumeration pathElements(VertexI candidate)
                                   throws VertexNotFoundException

Creates an Enumeration on the elements in the path from this candidate vertex to the root vertex. The enumeration returns all the edges and the vertices in alternating order starting and ending with a vertex. The edges are returned in order starting from the candidate vertex and ending at the root vertex. Note that this is the most efficient way to sequence through a path. The elements are returned in reverse path order if the root vertex is the source vertex.

Specified by:

pathElements in interface SingleVertexI

Throws:

VertexNotFoundException - if the candidate vertex is not in the solution.

GraphError - if the candidate is not owned by the graph.

getPath

public java.util.Vector getPath(VertexI candidate)
                         throws VertexNotFoundException

Creates a path Vector containing the elements in the path between the candidate vertex and the root. The vector contains all the edges and the vertices in alternating order starting and ending with a vertex. The elements will always be arranged in the order of forward path traversal.

Specified by:

getPath in interface SingleVertexI

Throws:

VertexNotFoundException - if the candidate vertex is not in the solution.

GraphError - if the candidate is not owned by the graph.

getEdgeValue

public EdgeValueI getEdgeValue(VertexI candidate)
                        throws VertexNotFoundException

Gets the edge value of the path between this candidate vertex and the root vertex.

Specified by:

getEdgeValue in interface SingleVertexI

Returns:

'null' if no path was found.

Throws:

VertexNotFoundException - if the vertex is not in the solution.

GraphError - if the candidate is not owned by the graph.

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object