java.lang.Object
org.jgrapht.alg.shortestpath.TreeSingleSourcePathsImpl<V,E>
 Type Parameters:
V
 the graph vertex typeE
 the graph edge type
 All Implemented Interfaces:
Serializable
,ShortestPathAlgorithm.SingleSourcePaths<V,
E>
public class TreeSingleSourcePathsImpl<V,E>
extends Object
implements ShortestPathAlgorithm.SingleSourcePaths<V,E>, Serializable
An implementation of
ShortestPathAlgorithm.SingleSourcePaths
which uses linear space.
This implementation uses the traditional representation of maintaining for each vertex the
predecessor in the shortest path tree. In order to keep space to linear, the paths are recomputed
in each invocation of the getPath(Object)
method. The complexity of
getPath(Object)
is linear to the number of edges of the path while the complexity of
getWeight(Object)
is $O(1)$.
 Author:
 Dimitrios Michail
 See Also:

Field Summary

Constructor Summary

Method Summary
Modifier and TypeMethodDescriptionGet the internal map used for representing the paths.getGraph()
Returns the graph over which this set of paths is defined.Return the path from the source vertex to the sink vertex.Returns the single source vertex.double
Return the weight of the path from the source vertex to the sink vertex.

Field Details

g
The graph 
source
The source vertex 
map
A map which keeps for each target vertex the predecessor edge and the total length of the shortest path.


Constructor Details

TreeSingleSourcePathsImpl
public TreeSingleSourcePathsImpl(Graph<V, E> g, V source, Map<V, Pair<Double, E>> distanceAndPredecessorMap) Construct a new instance. Parameters:
g
 the graphsource
 the source vertexdistanceAndPredecessorMap
 a map which contains for each vertex the distance and the last edge that was used to discover the vertex. The map does not need to contain any entry for the source vertex. In case it does contain the predecessor at the source vertex must be null.


Method Details

getGraph
Returns the graph over which this set of paths is defined. Specified by:
getGraph
in interfaceShortestPathAlgorithm.SingleSourcePaths<V,
E>  Returns:
 the graph

getSourceVertex
Returns the single source vertex. Specified by:
getSourceVertex
in interfaceShortestPathAlgorithm.SingleSourcePaths<V,
E>  Returns:
 the single source vertex

getDistanceAndPredecessorMap
Get the internal map used for representing the paths. Returns:
 the internal distance and predecessor map used for representing the paths.

getWeight
Return the weight of the path from the source vertex to the sink vertex. If no such path exists,Double.POSITIVE_INFINITY
is returned. The weight of the path between a vertex and itself is always zero. Specified by:
getWeight
in interfaceShortestPathAlgorithm.SingleSourcePaths<V,
E>  Parameters:
targetVertex
 the sink vertex Returns:
 the weight of the path between source and sink vertices or
Double.POSITIVE_INFINITY
in case no such path exists

getPath
Return the path from the source vertex to the sink vertex. Specified by:
getPath
in interfaceShortestPathAlgorithm.SingleSourcePaths<V,
E>  Parameters:
targetVertex
 the sink vertex Returns:
 the path from the source vertex to the sink vertex or null if no such path exists
