Module org.jgrapht.core
Package org.jgrapht.alg.shortestpath
Class CHManyToManyShortestPaths.CHManyToManyShortestPathsImpl
- java.lang.Object
-
- org.jgrapht.alg.interfaces.ManyToManyShortestPathsAlgorithm.BaseManyToManyShortestPathsImpl<V,E>
-
- org.jgrapht.alg.shortestpath.CHManyToManyShortestPaths.CHManyToManyShortestPathsImpl
-
- All Implemented Interfaces:
ManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths<V,E>
- Enclosing class:
- CHManyToManyShortestPaths<V,E>
private class CHManyToManyShortestPaths.CHManyToManyShortestPathsImpl extends ManyToManyShortestPathsAlgorithm.BaseManyToManyShortestPathsImpl<V,E>
Implementation ofManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths
for many-to-many shortest paths algorithm based on contraction hierarchy. Paths are stored in form of bidirectional single source shortest paths trees. When a path weight is queried a value that is stored indistanceAndMiddleVertexMap
is returned. When an actual paths is required it is constructed by recursively unpacking edges stored in the shortest paths trees corresponding to source and target vertices.
-
-
Field Summary
-
Constructor Summary
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description GraphPath<V,E>
getPath(V source, V target)
Return the path from thesource
vertex to thetarget
vertex.double
getWeight(V source, V target)
Return the weight of the path from thesource
vertex to thetarget
vertex orDouble.POSITIVE_INFINITY
if there is no such path in the graph.-
Methods inherited from class org.jgrapht.alg.interfaces.ManyToManyShortestPathsAlgorithm.BaseManyToManyShortestPathsImpl
assertCorrectSourceAndTarget, getSources, getTargets
-
-
-
-
Field Detail
-
contractionGraph
private final Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraph
Contraction hierarchy forgraph
.
-
contractionMapping
private final java.util.Map<V,ContractionHierarchyPrecomputation.ContractionVertex<V>> contractionMapping
Mapping from original to contracted vertices.
-
forwardSearchSpaces
private java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Pair<java.lang.Double,ContractionHierarchyPrecomputation.ContractionEdge<E>>>> forwardSearchSpaces
Stores forward search space for each start vertex.
-
backwardSearchSpaces
private java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Pair<java.lang.Double,ContractionHierarchyPrecomputation.ContractionEdge<E>>>> backwardSearchSpaces
Stores backward search space for each target vertex.
-
distanceAndMiddleVertexMap
private java.util.Map<Pair<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionVertex<V>>,Pair<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>> distanceAndMiddleVertexMap
Stores pair of path weight and middle vertex for each source-target pair.
-
-
Constructor Detail
-
CHManyToManyShortestPathsImpl
public CHManyToManyShortestPathsImpl(Graph<V,E> graph, ContractionHierarchyPrecomputation.ContractionHierarchy<V,E> hierarchy, java.util.Set<V> sources, java.util.Set<V> targets, java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Pair<java.lang.Double,ContractionHierarchyPrecomputation.ContractionEdge<E>>>> forwardSearchSpaces, java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Pair<java.lang.Double,ContractionHierarchyPrecomputation.ContractionEdge<E>>>> backwardSearchSpaces, java.util.Map<Pair<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionVertex<V>>,Pair<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>> distanceAndMiddleVertexMap)
Constructs a new instance for the givengraph
,contractionGraph
,contractionMapping
,forwardSearchSpaces
,backwardSearchSpaces
anddistanceAndMiddleVertexMap
.- Parameters:
graph
- underlying graph.hierarchy
- contraction hierarchyforwardSearchSpaces
- search spaces of source verticesbackwardSearchSpaces
- search spaces of target verticesdistanceAndMiddleVertexMap
- weights and middle vertices of paths
-
-
Method Detail
-
getPath
public GraphPath<V,E> getPath(V source, V target)
Return the path from thesource
vertex to thetarget
vertex. If no such path exists, null is returned.- Parameters:
source
- source vertextarget
- target vertex- Returns:
- path between
source
andtarget
or null if no such path exists
-
getWeight
public double getWeight(V source, V target)
Return the weight of the path from thesource
vertex to thetarget
vertex orDouble.POSITIVE_INFINITY
if there is no such path in the graph. The weight of the path between a vertex and itself is always zero.- Parameters:
source
- source vertextarget
- target vertex- Returns:
- the weight of the path between source and sink vertices or
Double.POSITIVE_INFINITY
in case no such path exists
-
-