Package org.jgrapht.alg.shortestpath
Class TreeSingleSourcePathsImpl<V,E>
- java.lang.Object
-
- org.jgrapht.alg.shortestpath.TreeSingleSourcePathsImpl<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
java.io.Serializable
,ShortestPathAlgorithm.SingleSourcePaths<V,E>
public class TreeSingleSourcePathsImpl<V,E> extends java.lang.Object implements ShortestPathAlgorithm.SingleSourcePaths<V,E>, java.io.Serializable
An implementation ofShortestPathAlgorithm.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 ofgetPath(Object)
is linear to the number of edges of the path while the complexity ofgetWeight(Object)
is $O(1)$.- Author:
- Dimitrios Michail
- See Also:
- Serialized Form
-
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description java.util.Map<V,Pair<java.lang.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.
-
-
-
Constructor Detail
-
TreeSingleSourcePathsImpl
public TreeSingleSourcePathsImpl(Graph<V,E> g, V source, java.util.Map<V,Pair<java.lang.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 Detail
-
getGraph
public Graph<V,E> getGraph()
Returns the graph over which this set of paths is defined.- Specified by:
getGraph
in interfaceShortestPathAlgorithm.SingleSourcePaths<V,E>
- Returns:
- the graph
-
getSourceVertex
public V getSourceVertex()
Returns the single source vertex.- Specified by:
getSourceVertex
in interfaceShortestPathAlgorithm.SingleSourcePaths<V,E>
- Returns:
- the single source vertex
-
getDistanceAndPredecessorMap
public java.util.Map<V,Pair<java.lang.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 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
public GraphPath<V,E> getPath(V targetVertex)
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
-
-