- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
ManyToManyShortestPathsAlgorithm<V,
,E> ShortestPathAlgorithm<V,
E>
The algorithm is originally described in the article: Sebastian Knopp, Peter Sanders, Dominik Schultes, Frank Schulz, and Dorothea Wagner. 2007. Computing many-to-many shortest paths using highway hierarchies. In Proceedings of the Meeting on Algorithm Engineering & Expermiments. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 36-45.
First contraction hierarchy is constructed. Then for each target vertex a backward single source shortest paths search is performed on the contracted graph. During the searches a bucket $b(v)$ is associated with each vertex $v$ in the graph. A bucket stores a set of pairs $(t,d)$, where $t$ is a target vertex current search is performed from and $d$ is the computed distance from $v$ to this target. Then a forward single source shortest paths search is performed from every source vertex. When a search settles a vertex $v$ with distance $d(s,v)$, where $s$ is current source vertex, its bucket is scanned. For each entry $(t,d)$ if $d(s,t) > d(s,v) + d$ values of paths weight between $s$ and $t$ and its middle vertex is updated. The middle vertices are then used to restored actual path from the information in the shortest paths trees.
Additionally if $|S| > |T|$ the algorithm is executed on the reversed graph. This allows to reduce the number of buckets and optimize memory usage of the algorithm.
The efficiency of this algorithm is derived from the fact that contraction hierarchy produces fairly small shortest paths trees. This allows to both speedup the computations and decrease memory usage to store the paths. The bottleneck of the algorithm is the contraction hierarchy computation, which can lead to significant overhead for dense graphs both in terms of running time and space complexity. Therefore the ideal use cases for this algorithm are sparse graphs of any size with low average out-degree of vertices.
- See Also:
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate class
Stores data computed during the backward searches.private class
Implementation ofManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths
for many-to-many shortest paths algorithm based on contraction hierarchy.Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.ManyToManyShortestPathsAlgorithm
ManyToManyShortestPathsAlgorithm.BaseManyToManyShortestPathsImpl<V,
E>, ManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths<V, E> Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.ShortestPathAlgorithm
ShortestPathAlgorithm.SingleSourcePaths<V,
E> -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate Graph
<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> Contracted version ofgraph
.Contraction hierarchy ofgraph
.Mapping from vertices in the originalgraph
to vertices in thecontractionGraph
.Fields inherited from class org.jgrapht.alg.shortestpath.BaseManyToManyShortestPaths
graph
-
Constructor Summary
ConstructorsConstructorDescriptionCHManyToManyShortestPaths
(ContractionHierarchyPrecomputation.ContractionHierarchy<V, E> contractionHierarchy) Constructs an instance of the algorithm for a givencontractionHierarchy
.CHManyToManyShortestPaths
(Graph<V, E> graph, ThreadPoolExecutor executor) Constructs an instance of the algorithm for a givengraph
andexecutor
. -
Method Summary
Modifier and TypeMethodDescriptionprivate void
backwardSearch
(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraph, ContractionHierarchyPrecomputation.ContractionVertex<V> target, Set<ContractionHierarchyPrecomputation.ContractionVertex<V>> contractedSources, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, List<CHManyToManyShortestPaths<V, E>.BucketEntry>> bucketsMap, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Pair<Double, ContractionHierarchyPrecomputation.ContractionEdge<E>>>> backwardSearchSpaces, boolean reversed) Performs backward single source shortest paths search incontractionGraph
starting fromtarget
tosources
.private void
forwardSearch
(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraph, ContractionHierarchyPrecomputation.ContractionVertex<V> source, Set<ContractionHierarchyPrecomputation.ContractionVertex<V>> contractedTargets, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, List<CHManyToManyShortestPaths<V, E>.BucketEntry>> bucketsMap, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Pair<Double, ContractionHierarchyPrecomputation.ContractionEdge<E>>>> forwardSearchSpaces, Map<Pair<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionVertex<V>>, Pair<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> middleVerticesMap, boolean reversed) Performs forward search from the givensource
totargets
.private Map
<ContractionHierarchyPrecomputation.ContractionVertex<V>, Pair<Double, ContractionHierarchyPrecomputation.ContractionEdge<E>>> getDistanceAndPredecessorMap
(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraph, ContractionHierarchyPrecomputation.ContractionVertex<V> source, Set<ContractionHierarchyPrecomputation.ContractionVertex<V>> targets) Computes distance and predecessor map for a single source shortest paths search starting at source and finishing the search as soon as alltargets
are reached.getManyToManyPaths
(Set<V> sources, Set<V> targets) Computes shortest paths from all vertices insources
to all vertices intargets
.Methods inherited from class org.jgrapht.alg.shortestpath.BaseManyToManyShortestPaths
getPath, getPaths, getPathWeight, getShortestPathsTree
-
Field Details
-
contractionHierarchy
Contraction hierarchy ofgraph
. -
contractionGraph
private Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraphContracted version ofgraph
. -
contractionMapping
Mapping from vertices in the originalgraph
to vertices in thecontractionGraph
.
-
-
Constructor Details
-
CHManyToManyShortestPaths
Constructs an instance of the algorithm for a givengraph
andexecutor
. It is up to a user of this algorithm to handle the creation and termination of the providedexecutor
. For utility methods to manage aThreadPoolExecutor
seeConcurrencyUtil
.- Parameters:
graph
- a graphexecutor
- executor which will be used to computeContractionHierarchyPrecomputation.ContractionHierarchy
-
CHManyToManyShortestPaths
public CHManyToManyShortestPaths(ContractionHierarchyPrecomputation.ContractionHierarchy<V, E> contractionHierarchy) Constructs an instance of the algorithm for a givencontractionHierarchy
.- Parameters:
contractionHierarchy
- contraction of thegraph
-
-
Method Details
-
getManyToManyPaths
public ManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths<V,E> getManyToManyPaths(Set<V> sources, Set<V> targets) Computes shortest paths from all vertices insources
to all vertices intargets
.- Parameters:
sources
- list of sources verticestargets
- list of target vertices- Returns:
- computed shortest paths
-
backwardSearch
private void backwardSearch(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraph, ContractionHierarchyPrecomputation.ContractionVertex<V> target, Set<ContractionHierarchyPrecomputation.ContractionVertex<V>> contractedSources, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, List<CHManyToManyShortestPaths<V, E>.BucketEntry>> bucketsMap, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Pair<Double, ContractionHierarchyPrecomputation.ContractionEdge<E>>>> backwardSearchSpaces, boolean reversed) Performs backward single source shortest paths search incontractionGraph
starting fromtarget
tosources
. For each vertex $v$ incontractionGraph
a bucket is created that records entries $(t,d)$, where $t$ is a currenttarget
and $d$ is a distance computed during current search. A constructed shortest paths tree is then put inbackwardSearchSpaces
. Ifreversed
flag is set to $true$ the specifiedtarget
belongs to the original source vertices and therefore downward edges should be masked in the contraction graph instead of upward.- Parameters:
contractionGraph
- graph to perform search intarget
- search start vertexcontractedSources
- vertices to end search atbucketsMap
- map from vertices to their bucketsbackwardSearchSpaces
- map from vertices to their search spacesreversed
- indicates if current search is reversed
-
forwardSearch
private void forwardSearch(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraph, ContractionHierarchyPrecomputation.ContractionVertex<V> source, Set<ContractionHierarchyPrecomputation.ContractionVertex<V>> contractedTargets, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, List<CHManyToManyShortestPaths<V, E>.BucketEntry>> bucketsMap, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, Pair<Double, ContractionHierarchyPrecomputation.ContractionEdge<E>>>> forwardSearchSpaces, Map<Pair<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionVertex<V>>, Pair<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> middleVerticesMap, boolean reversed) Performs forward search from the givensource
totargets
. A constructed shortest paths tree is then put inforwardSearchSpaces
. Ifreversed
flag is set to $true$ the specifiedsource
belongs to the original target vertices and therefore upward edges should be masked in the contraction graph instead of the downward.- Parameters:
contractionGraph
- graph to perform search insource
- start vertex of the searchcontractedTargets
- vertices to end search atbucketsMap
- map from vertices to their bucketsforwardSearchSpaces
- map from vertices to their search spacesmiddleVerticesMap
- map from source-target pairs to theirs distances and middle nodesreversed
- indicates if current search is reversed
-
getDistanceAndPredecessorMap
private Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,Pair<Double, getDistanceAndPredecessorMapContractionHierarchyPrecomputation.ContractionEdge<E>>> (Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraph, ContractionHierarchyPrecomputation.ContractionVertex<V> source, Set<ContractionHierarchyPrecomputation.ContractionVertex<V>> targets) Computes distance and predecessor map for a single source shortest paths search starting at source and finishing the search as soon as alltargets
are reached.- Parameters:
contractionGraph
- a graphsource
- search start vertextargets
- search end vertices- Returns:
- distance and predecessor map
-