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 of
ManyToManyShortestPathsAlgorithm.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 in distanceAndMiddleVertexMap
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
FieldsModifier and TypeFieldDescriptionprivate Map
<ContractionHierarchyPrecomputation.ContractionVertex<V>, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Pair<Double, ContractionHierarchyPrecomputation.ContractionEdge<E>>>> Stores backward search space for each target vertex.private final Graph
<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> Contraction hierarchy forgraph
.private final Map
<V, ContractionHierarchyPrecomputation.ContractionVertex<V>> Mapping from original to contracted vertices.private Map
<Pair<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionVertex<V>>, Pair<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> Stores pair of path weight and middle vertex for each source-target pair.private Map
<ContractionHierarchyPrecomputation.ContractionVertex<V>, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Pair<Double, ContractionHierarchyPrecomputation.ContractionEdge<E>>>> Stores forward search space for each start vertex.The underlying graph. -
Constructor Summary
ConstructorsConstructorDescriptionCHManyToManyShortestPathsImpl
(Graph<V, E> graph, ContractionHierarchyPrecomputation.ContractionHierarchy<V, E> hierarchy, Set<V> sources, Set<V> targets, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Pair<Double, ContractionHierarchyPrecomputation.ContractionEdge<E>>>> forwardSearchSpaces, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Pair<Double, ContractionHierarchyPrecomputation.ContractionEdge<E>>>> backwardSearchSpaces, Map<Pair<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionVertex<V>>, Pair<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> distanceAndMiddleVertexMap) Constructs a new instance for the givengraph
,contractionGraph
,contractionMapping
,forwardSearchSpaces
,backwardSearchSpaces
anddistanceAndMiddleVertexMap
. -
Method Summary
Modifier and TypeMethodDescriptionReturn the path from thesource
vertex to thetarget
vertex.double
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 Details
-
graph
The underlying graph. -
contractionGraph
private final Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraphContraction hierarchy forgraph
. -
contractionMapping
Mapping from original to contracted vertices. -
forwardSearchSpaces
private Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, forwardSearchSpacesPair<Double, ContractionHierarchyPrecomputation.ContractionEdge<E>>>> Stores forward search space for each start vertex. -
backwardSearchSpaces
private Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, backwardSearchSpacesPair<Double, ContractionHierarchyPrecomputation.ContractionEdge<E>>>> Stores backward search space for each target vertex. -
distanceAndMiddleVertexMap
private Map<Pair<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionVertex<V>>, distanceAndMiddleVertexMapPair<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> Stores pair of path weight and middle vertex for each source-target pair.
-
-
Constructor Details
-
CHManyToManyShortestPathsImpl
public CHManyToManyShortestPathsImpl(Graph<V, E> graph, ContractionHierarchyPrecomputation.ContractionHierarchy<V, E> hierarchy, Set<V> sources, Set<V> targets, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Pair<Double, ContractionHierarchyPrecomputation.ContractionEdge<E>>>> forwardSearchSpaces, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Pair<Double, ContractionHierarchyPrecomputation.ContractionEdge<E>>>> backwardSearchSpaces, Map<Pair<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionVertex<V>>, Pair<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 Details
-
getPath
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
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
-