Class ContractionHierarchyPrecomputation<V,E>
 java.lang.Object

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

 Type Parameters:
V
 the graph vertex typeE
 the graph edge type
public class ContractionHierarchyPrecomputation<V,E> extends java.lang.Object
Parallel implementation of the contraction hierarchy route planning precomputation technique.The original algorithm is described the article: Robert Geisberger, Peter Sanders, Dominik Schultes, and Daniel Delling. 2008. Contraction hierarchies: faster and simpler hierarchical routing in road networks. In Proceedings of the 7th international conference on Experimental algorithms (WEA'08), Catherine C. McGeoch (Ed.). SpringerVerlag, Berlin, Heidelberg, 319333.
Parallel version of the algorithm is described in the article: Vetter, Christian. "Parallel TimeDependent Contraction Hierarchies." (2009).
This algorithm speeds up shortest paths computation by contracting graph vertices. To contract a vertex means to remove it from the graph in such a way that shortest paths in the remaining overlay graph are preserved. This property is achieved by replacing paths of the form $\langle u, v, w\rangle$ by a shortcut edge $(u, w)$. Note that the shortcut $(u, w)$ is only required if $\langle u, v, w\rangle$ is the only shortest path from $u$ to $w$.
Contraction is performed as follows. First a priority is computed for each vertex in the graph. This implementation uses edge quotient, complexity quotient and hierarchical depth metrics for computing priority. A hierarchy is then generated by iteratively contracting independent sets of vertices. A vertex is independent iff it`s priority is less than the priority of every vertex in its 2neighbourhood. A 2neighbourhood of a vertex $v$ is defined as a set of vertices that are reachable from $v$ using at most 2 hops. After contraction each vertex gets its unique contraction level  its position in the computed hierarchy. Finally, after all vertices are contracted each edge is set to be either upward if its source has lower level that its target, or downward if vice versa.
Computing initial priorities, independent sets and shortcuts, updating neighbours priorities and marking upward edges is performed in parallel what gives this implementation performance speedup comparing to the sequential approach.
For parallelization, this implementation relies on the
ThreadPoolExecutor
which is supplied to this algorithm from outside. Author:
 Semen Chudakov


Nested Class Summary
Nested Classes Modifier and Type Class Description static class
ContractionHierarchyPrecomputation.ContractionEdge<E1>
Edge for building the contraction hierarchy.static class
ContractionHierarchyPrecomputation.ContractionHierarchy<V,E>
Return type of this algorithm.static class
ContractionHierarchyPrecomputation.ContractionVertex<V1>
Vertex for building the contraction hierarchy, which contains an original vertex fromgraph
.

Constructor Summary
Constructors Constructor Description ContractionHierarchyPrecomputation(Graph<V,E> graph, java.util.concurrent.ThreadPoolExecutor executor)
Constructs a new instance of the algorithm for a givengraph
andexecutor
.ContractionHierarchyPrecomputation(Graph<V,E> graph, java.util.function.Supplier<java.util.Random> randomSupplier, java.util.concurrent.ThreadPoolExecutor executor)
Constructs a new instance of the algorithm for a givengraph
,randomSupplier
andexecutor
.ContractionHierarchyPrecomputation(Graph<V,E> graph, java.util.function.Supplier<java.util.Random> randomSupplier, java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>> shortcutsSearchHeapSupplier, java.util.concurrent.ThreadPoolExecutor executor)
Constructs a new instance of the algorithm for a givengraph
,parallelism
,randomSupplier
,shortcutsSearchHeapSupplier
andexecutor
.

Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description ContractionHierarchyPrecomputation.ContractionHierarchy<V,E>
computeContractionHierarchy()
Computes contraction hierarchy forgraph
.



Constructor Detail

ContractionHierarchyPrecomputation
public ContractionHierarchyPrecomputation(Graph<V,E> graph, java.util.concurrent.ThreadPoolExecutor executor)
Constructs a new 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
 graphexecutor
 executor which will be used for parallelization

ContractionHierarchyPrecomputation
public ContractionHierarchyPrecomputation(Graph<V,E> graph, java.util.function.Supplier<java.util.Random> randomSupplier, java.util.concurrent.ThreadPoolExecutor executor)
Constructs a new instance of the algorithm for a givengraph
,randomSupplier
andexecutor
. ProvidedrandomSupplier
should return different random generators instances, because they are used by different threads. It is up to a user of this algorithm to handle the creation and termination of the providedexecutor
. Utility methods to manage aThreadPoolExecutor
seeConcurrencyUtil
. Parameters:
graph
 graphrandomSupplier
 supplier for preferable instances ofRandom
executor
 executor which will be used for parallelization

ContractionHierarchyPrecomputation
public ContractionHierarchyPrecomputation(Graph<V,E> graph, java.util.function.Supplier<java.util.Random> randomSupplier, java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>> shortcutsSearchHeapSupplier, java.util.concurrent.ThreadPoolExecutor executor)
Constructs a new instance of the algorithm for a givengraph
,parallelism
,randomSupplier
,shortcutsSearchHeapSupplier
andexecutor
. ProvidedrandomSupplier
should return different random generators instances, because they are used by different threads. 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
 graphrandomSupplier
 supplier for preferable instances ofRandom
shortcutsSearchHeapSupplier
 supplier for the preferable heap implementation.executor
 executor which will be used for parallelization


Method Detail

computeContractionHierarchy
public ContractionHierarchyPrecomputation.ContractionHierarchy<V,E> computeContractionHierarchy()
Computes contraction hierarchy forgraph
. Returns:
 contraction hierarchy and mapping of original to contracted vertices

