## Class CHManyToManyShortestPaths<V,​E>

• java.lang.Object
• org.jgrapht.alg.shortestpath.CHManyToManyShortestPaths<V,​E>
• Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
ManyToManyShortestPathsAlgorithm<V,​E>, ShortestPathAlgorithm<V,​E>

public class CHManyToManyShortestPaths<V,​E>
extends java.lang.Object
Efficient algorithm for the many-to-many shortest paths problem based on contraction hierarchy.

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.

Author:
Semen Chudakov
DefaultManyToManyShortestPaths, DijkstraManyToManyShortestPaths

• ### 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

Fields
Modifier and Type Field Description
protected Graph<V,​E> graph
• ### Constructor Summary

Constructors
Constructor Description
CHManyToManyShortestPaths​(ContractionHierarchyPrecomputation.ContractionHierarchy<V,​E> contractionHierarchy)
Constructs an instance of the algorithm for a given contractionHierarchy.
CHManyToManyShortestPaths​(Graph<V,​E> graph, java.util.concurrent.ThreadPoolExecutor executor)
Constructs an instance of the algorithm for a given graph and executor.
• ### Method Summary

All Methods
Modifier and Type Method Description
ManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths<V,​E> getManyToManyPaths​(java.util.Set<V> sources, java.util.Set<V> targets)
Computes shortest paths from all vertices in sources to all vertices in targets.
GraphPath<V,​E> getPath​(V source, V sink)
Get a shortest path from a source vertex to a sink vertex.
ShortestPathAlgorithm.SingleSourcePaths<V,​E> getPaths​(V source)
Compute all shortest paths starting from a single source vertex.
double getPathWeight​(V source, V sink)
Get the weight of the shortest path from a source vertex to a sink vertex.
protected static <V,​E>ShortestPathAlgorithm.SingleSourcePaths<V,​E> getShortestPathsTree​(Graph<V,​E> graph, V source, java.util.Set<V> targets)
Computes shortest paths tree starting at source and stopping as soon as all of the targets are reached.
• ### Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• ### Field Detail

• #### graph

protected final Graph<V,​E> graph
• ### Constructor Detail

• #### CHManyToManyShortestPaths

public CHManyToManyShortestPaths​(Graph<V,​E> graph,
java.util.concurrent.ThreadPoolExecutor executor)
Constructs an instance of the algorithm for a given graph and executor. It is up to a user of this algorithm to handle the creation and termination of the provided executor. For utility methods to manage a ThreadPoolExecutor see ConcurrencyUtil.
Parameters:
graph - a graph
executor - executor which will be used to compute ContractionHierarchyPrecomputation.ContractionHierarchy
• #### CHManyToManyShortestPaths

public CHManyToManyShortestPaths​(ContractionHierarchyPrecomputation.ContractionHierarchy<V,​E> contractionHierarchy)
Constructs an instance of the algorithm for a given contractionHierarchy.
Parameters:
contractionHierarchy - contraction of the graph
• ### Method Detail

• #### getManyToManyPaths

public ManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths<V,​E> getManyToManyPaths​(java.util.Set<V> sources,
java.util.Set<V> targets)
Computes shortest paths from all vertices in sources to all vertices in targets.
Parameters:
sources - list of sources vertices
targets - list of target vertices
Returns:
computed shortest paths
• #### getPath

public GraphPath<V,​E> getPath​(V source,
V sink)
Get a shortest path from a source vertex to a sink vertex.
Specified by:
getPath in interface ShortestPathAlgorithm<V,​E>
Parameters:
source - the source vertex
sink - the target vertex
Returns:
a shortest path or null if no path exists
• #### getPathWeight

public double getPathWeight​(V source,
V sink)
Get the weight of the shortest path from a source vertex to a sink vertex. Returns Double.POSITIVE_INFINITY if no path exists.
Specified by:
getPathWeight in interface ShortestPathAlgorithm<V,​E>
Parameters:
source - the source vertex
sink - the sink vertex
Returns:
the weight of the shortest path from a source vertex to a sink vertex, or Double.POSITIVE_INFINITY if no path exists
• #### getPaths

public ShortestPathAlgorithm.SingleSourcePaths<V,​E> getPaths​(V source)
Compute all shortest paths starting from a single source vertex.
Specified by:
getPaths in interface ShortestPathAlgorithm<V,​E>
Parameters:
source - the source vertex
Returns:
the shortest paths
• #### getShortestPathsTree

protected static <V,​E> ShortestPathAlgorithm.SingleSourcePaths<V,​E> getShortestPathsTree​(Graph<V,​E> graph,
V source,
java.util.Set<V> targets)
Computes shortest paths tree starting at source and stopping as soon as all of the targets are reached. Here the DijkstraClosestFirstIterator is used.
Type Parameters:
V - the graph vertex type
E - the graph edge type
Parameters:
graph - a graph
source - source vertex
targets - target vertices
Returns:
shortest paths starting from source and reaching all targets