- Type Parameters:
V- the graph vertex type
E- the graph edge type
- All Implemented Interfaces:
public class TreeSingleSourcePathsImpl<V,E> extends java.lang.Object implements ShortestPathAlgorithm.SingleSourcePaths<V,E>, java.io.SerializableAn implementation of
ShortestPathAlgorithm.SingleSourcePathswhich 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
- Dimitrios Michail
- See Also:
- Serialized Form
All Methods Instance Methods Concrete Methods Modifier and Type Method Description
getDistanceAndPredecessorMap()Get the internal map used for representing the paths.
getGraph()Returns the graph over which this set of paths is defined.
getPath(V targetVertex)Return the path from the source vertex to the sink vertex.
getSourceVertex()Returns the single source vertex.
getWeight(V targetVertex)Return the weight of the path from the source vertex to the sink vertex.
public TreeSingleSourcePathsImpl(Graph<V,E> g, V source, java.util.Map<V,Pair<java.lang.Double,E>> distanceAndPredecessorMap)Construct a new instance.
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.
getGraphReturns the graph over which this set of paths is defined.
public V getSourceVertex()Returns the single source vertex.
getDistanceAndPredecessorMapGet the internal map used for representing the paths.
- the internal distance and predecessor map used for representing the paths.
public double getWeight(V targetVertex)
Double.POSITIVE_INFINITYis returned. The weight of the path between a vertex and itself is always zero.
getPathReturn the path from the source vertex to the sink vertex.