 java.lang.Object

 org.jgrapht.alg.shortestpath.CHManyToManyShortestPaths<V,E>

 Type Parameters:
V
 the graph vertex typeE
 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 manytomany 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 manytomany shortest paths using highway hierarchies. In Proceedings of the Meeting on Algorithm Engineering & Expermiments. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 3645.
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 outdegree of vertices.
 Author:
 Semen Chudakov
 See Also:
DefaultManyToManyShortestPaths
,DijkstraManyToManyShortestPaths


Nested Class Summary

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>


Constructor Summary
Constructors Constructor Description CHManyToManyShortestPaths(ContractionHierarchyPrecomputation.ContractionHierarchy<V,E> contractionHierarchy)
Constructs an instance of the algorithm for a givencontractionHierarchy
.CHManyToManyShortestPaths(Graph<V,E> graph, java.util.concurrent.ThreadPoolExecutor executor)
Constructs an instance of the algorithm for a givengraph
andexecutor
.

Method Summary
All Methods Static Methods Instance Methods Concrete 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 insources
to all vertices intargets
.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 atsource
and stopping as soon as all of thetargets
are reached.



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 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 Detail

getManyToManyPaths
public ManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths<V,E> getManyToManyPaths(java.util.Set<V> sources, java.util.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

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 interfaceShortestPathAlgorithm<V,E>
 Parameters:
source
 the source vertexsink
 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. ReturnsDouble.POSITIVE_INFINITY
if no path exists. Specified by:
getPathWeight
in interfaceShortestPathAlgorithm<V,E>
 Parameters:
source
 the source vertexsink
 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 interfaceShortestPathAlgorithm<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 atsource
and stopping as soon as all of thetargets
are reached. Here theDijkstraClosestFirstIterator
is used. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
graph
 a graphsource
 source vertextargets
 target vertices Returns:
 shortest paths starting from
source
and reaching alltargets

