V
 the graph vertex typeE
 the graph edge typepublic class TreeSingleSourcePathsImpl<V,E> extends Object implements ShortestPathAlgorithm.SingleSourcePaths<V,E>, Serializable
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)$.
Modifier and Type  Field and Description 

protected Graph<V,E> 
g
The graph

protected Map<V,Pair<Double,E>> 
map
A map which keeps for each target vertex the predecessor edge and the total length of the
shortest path.

protected V 
source
The source vertex

Constructor and Description 

TreeSingleSourcePathsImpl(Graph<V,E> g,
V source,
Map<V,Pair<Double,E>> distanceAndPredecessorMap)
Construct a new instance.

Modifier and Type  Method and Description 

Map<V,Pair<Double,E>> 
getDistanceAndPredecessorMap()
Get the internal map used for representing the paths.

Graph<V,E> 
getGraph()
Returns the graph over which this set of paths is defined.

GraphPath<V,E> 
getPath(V targetVertex)
Return the path from the source vertex to the sink vertex.

V 
getSourceVertex()
Returns the single source vertex.

double 
getWeight(V targetVertex)
Return the weight of the path from the source vertex to the sink vertex.

protected V source
public TreeSingleSourcePathsImpl(Graph<V,E> g, V source, Map<V,Pair<Double,E>> distanceAndPredecessorMap)
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.public Graph<V,E> getGraph()
getGraph
in interface ShortestPathAlgorithm.SingleSourcePaths<V,E>
public V getSourceVertex()
getSourceVertex
in interface ShortestPathAlgorithm.SingleSourcePaths<V,E>
public Map<V,Pair<Double,E>> getDistanceAndPredecessorMap()
public double getWeight(V targetVertex)
Double.POSITIVE_INFINITY
is returned. The weight of the path between a
vertex and itself is always zero.getWeight
in interface ShortestPathAlgorithm.SingleSourcePaths<V,E>
targetVertex
 the sink vertexDouble.POSITIVE_INFINITY
in case no such path existspublic GraphPath<V,E> getPath(V targetVertex)
getPath
in interface ShortestPathAlgorithm.SingleSourcePaths<V,E>
targetVertex
 the sink vertexCopyright © 2019. All rights reserved.