## Class TreeSingleSourcePathsImpl<V,​E>

• java.lang.Object
• org.jgrapht.alg.shortestpath.TreeSingleSourcePathsImpl<V,​E>
• Type Parameters:
V - the graph vertex type
E - 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
Serialized Form
• ### Field Summary

Fields
Modifier and Type Field 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 Summary

Constructors
Constructor Description
TreeSingleSourcePathsImpl​(Graph<V,​E> g, V source, Map<V,​Pair<Double,​E>> distanceAndPredecessorMap)
Construct a new instance.
• ### Method Summary

All Methods
Modifier and Type Method 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.
• ### Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• ### Field Detail

• #### g

protected Graph<V,​E> g
The graph
• #### source

protected V source
The source vertex
• #### map

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.
• ### Constructor Detail

• #### TreeSingleSourcePathsImpl

public TreeSingleSourcePathsImpl​(Graph<V,​E> g,
V source,
Map<V,​Pair<Double,​E>> distanceAndPredecessorMap)
Construct a new instance.
Parameters:
g - the graph
source - the source vertex
distanceAndPredecessorMap - 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 Detail

• #### getGraph

public Graph<V,​E> getGraph()
Returns the graph over which this set of paths is defined.
Specified by:
getGraph in interface ShortestPathAlgorithm.SingleSourcePaths<V,​E>
Returns:
the graph
• #### getSourceVertex

public V getSourceVertex()
Returns the single source vertex.
Specified by:
getSourceVertex in interface ShortestPathAlgorithm.SingleSourcePaths<V,​E>
Returns:
the single source vertex
• #### getDistanceAndPredecessorMap

public Map<V,​Pair<Double,​E>> getDistanceAndPredecessorMap()
Get the internal map used for representing the paths.
Returns:
the internal distance and predecessor map used for representing the paths.
• #### getWeight

public double getWeight​(V targetVertex)
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 interface ShortestPathAlgorithm.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

public GraphPath<V,​E> getPath​(V targetVertex)
Return the path from the source vertex to the sink vertex.
Specified by:
getPath in interface ShortestPathAlgorithm.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