drasys.or.graph.sp
Interface SingleVertexI

All Known Implementing Classes:

Connections, Dijkstra

public interface SingleVertexI

The interface used by all algorithms to access single vertex shortest path algorithms. These algorithms find 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 the 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 the performance of the algorithm.

See Also:

Dijkstra, Connections

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 values 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 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.
boolean	usesConnectionProperties()           Returns true if an algorithm uses the connection properties.

 

Method Detail

usesConnectionProperties

public boolean usesConnectionProperties()

Returns true if an algorithm uses the connection properties.

setListener

public void setListener(SingleVertexListenerI listener)

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

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

setMaxPaths

public void setMaxPaths(int maxPaths)

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

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.

setMaxCost

public void setMaxCost(double maxCost)

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

setMaxTime

public void setMaxTime(double maxTime)

Sets the maximum time for any path. The cost of no path will be greater than this value.

setMaxDistance

public void setMaxDistance(double maxDistance)

Sets the maximum distance for any path. The cost of no path will be greater than this value.

setCandidate

public void setCandidate(boolean isCandidate)

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

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.

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.

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.

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.

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.

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.

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.

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.

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 values of the path between this candidate vertex and the root vertex.

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.