All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class drasys.or.graph.sp.Dijkstra 

drasys.or.graph.sp.Dijkstra
public class Dijkstra
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 path count, path length and path cost. The constraints all reduce the size of the path tree and can greatly improve performance. By default the properties object is set to 'null'. When the properties object is null, the algorithm behaves like it is using 'PropertiesAdapter'.

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

Copyright (C) 1997,1998 by DRA Systems all rights reserved.

Constructor Index

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

Method Index

o candidates()
Creates an Enumeration on the candidate vertices that were reached in the path generation.
o generatePathsFrom(Object)
Creates the single source shortest path tree from the root vertex to the candidate vertices.
o generatePathsTo(Object)
Creates the single destination shortest path tree from the candidate vertices to the root vertex.
o getCost(VertexI)
Gets the cost of the path between this candidate vertex and the root vertex.
o getNearestCandidate()
Returns the candidate vertex for the single shortest path generated.
o getPath(VertexI)
Creates a path Vector containing the elements in the path between the candidate vertex and the root.
o pathElements(VertexI)
Creates an Enumeration on the elements in the path from this candidate vertex to the root vertex.
o setCandidate(boolean)
Sets the candidate flags for all vertices.
o setCandidate(Object, boolean)
Sets the candidate flag for a specific vertex.
o setListener(SingleVertexListenerI)
Sets the listener to receive the shortest path events.
o setMaxCost(double)
Sets the maximum cost for any path.
o setMaxLength(int)
Sets the maximum number of edges in any path.
o setMaxPaths(int)
Sets the maximum number of paths the the algorithm will generate.
o setProperties(PropertiesI)
Sets the properties object that is used to access vertex and edge properties.
o toString()
o usesConnectionProperties()
Returns false because this algorithm ignores the connection properties.

Constructors

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

o 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'.

Methods

o usesConnectionProperties 
 public boolean usesConnectionProperties()
Returns false because this algorithm ignores the connection properties.

Returns:
false
o setListener 
 public void setListener(SingleVertexListenerI listener)
Sets the listener to receive the shortest path events. Passing a null argument disables events.

o 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'.

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

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

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

o setCandidate 
 public void setCandidate(boolean isCandidate)
Sets the candidate flags for all vertices. By default no vertices are marked as candidates.

o setCandidate 
 public void setCandidate(Object key,
                          boolean isCandidate) throws VertexNotFoundException
Sets the candidate flag for a specific vertex. By default no vertices are marked as candidates.

o generatePathsTo 
 public int generatePathsTo(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.

Returns:
The number of paths generated.
o generatePathsFrom 
 public int generatePathsFrom(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.

Returns:
The number of paths generated.
o getNearestCandidate 
 public VertexI getNearestCandidate()
Returns the candidate vertex for the single shortest path generated.

Returns:
Null if no paths were found.
o candidates 
 public 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.

o pathElements 
 public 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.

Throws: GraphError
if the candidate is not owned by the graph.
o getPath 
 public 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.

Throws: GraphError
if the candidate is not owned by the graph.
o getCost 
 public double getCost(VertexI candidate) throws VertexNotFoundException
Gets the cost of the path between this candidate vertex and the root vertex.

Returns:
Double.POSITIVE_INFINITY if no path was found, zero if the candidate is the root.
Throws: GraphError
if the candidate is not owned by the graph.
o toString 
 public String toString()

All Packages  Class Hierarchy  This Package  Previous  Next  Index