## Class ContractionHierarchyPrecomputation<V,​E>

• java.lang.Object
• org.jgrapht.alg.shortestpath.ContractionHierarchyPrecomputation<V,​E>
• Type Parameters:
V - the graph vertex type
E - the graph edge type

public class ContractionHierarchyPrecomputation<V,​E>
extends 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.). Springer-Verlag, Berlin, Heidelberg, 319-333.

Parallel version of the algorithm is described in the article: Vetter, Christian. "Parallel Time-Dependent 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 its priority is less than the priority of every vertex in its 2-neighbourhood. A 2-neighbourhood 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 ExecutorService.

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 from graph.
• ### Constructor Summary

Constructors
Constructor Description
ContractionHierarchyPrecomputation​(Graph<V,​E> graph)
Constructs a new instance of the algorithm for a given graph.
ContractionHierarchyPrecomputation​(Graph<V,​E> graph, int parallelism)
Constructs a new instance of the algorithm for a given graph and parallelism.
ContractionHierarchyPrecomputation​(Graph<V,​E> graph, int parallelism, Supplier<Random> randomSupplier)
Constructs a new instance of the algorithm for a given graph, parallelism and randomSupplier.
ContractionHierarchyPrecomputation​(Graph<V,​E> graph, int parallelism, Supplier<Random> randomSupplier, Supplier<org.jheaps.AddressableHeap<Double,​ContractionHierarchyPrecomputation.ContractionVertex<V>>> shortcutsSearchHeapSupplier)
Constructs a new instance of the algorithm for a given graph, parallelism, randomSupplier and shortcutsSearchHeapSupplier.
ContractionHierarchyPrecomputation​(Graph<V,​E> graph, Supplier<Random> randomSupplier)
Constructs a new instance of the algorithm for a given graph and randomSupplier.
• ### Method Summary

All Methods
Modifier and Type Method Description
ContractionHierarchyPrecomputation.ContractionHierarchy<V,​E> computeContractionHierarchy()
Computes contraction hierarchy for graph.
• ### Methods inherited from class java.lang.Object

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

• #### ContractionHierarchyPrecomputation

public ContractionHierarchyPrecomputation​(Graph<V,​E> graph)
Constructs a new instance of the algorithm for a given graph.
Parameters:
graph - graph
• #### ContractionHierarchyPrecomputation

public ContractionHierarchyPrecomputation​(Graph<V,​E> graph,
int parallelism)
Constructs a new instance of the algorithm for a given graph and parallelism.
Parameters:
graph - graph
parallelism - maximum number of threads used in the computations
• #### ContractionHierarchyPrecomputation

public ContractionHierarchyPrecomputation​(Graph<V,​E> graph,
Supplier<Random> randomSupplier)
Constructs a new instance of the algorithm for a given graph and randomSupplier. Provided randomSupplier should return different random generators instances, because they are used by different threads.
Parameters:
graph - graph
randomSupplier - supplier for preferable instances of Random
• #### ContractionHierarchyPrecomputation

public ContractionHierarchyPrecomputation​(Graph<V,​E> graph,
int parallelism,
Supplier<Random> randomSupplier)
Constructs a new instance of the algorithm for a given graph, parallelism and randomSupplier.
Parameters:
graph - graph
parallelism - maximum number of threads used in the computations
randomSupplier - supplier for preferable instances of Random
• #### ContractionHierarchyPrecomputation

public ContractionHierarchyPrecomputation​(Graph<V,​E> graph,
int parallelism,
Supplier<Random> randomSupplier,
Supplier<org.jheaps.AddressableHeap<Double,​ContractionHierarchyPrecomputation.ContractionVertex<V>>> shortcutsSearchHeapSupplier)
Constructs a new instance of the algorithm for a given graph, parallelism, randomSupplier and shortcutsSearchHeapSupplier. Provided randomSupplier should return different random generators instances, because they are used by different threads.
Parameters:
graph - graph
parallelism - maximum number of threads used in the computations
randomSupplier - supplier for preferable instances of Random
shortcutsSearchHeapSupplier - supplier for the preferable heap implementation.
• ### Method Detail

• #### computeContractionHierarchy

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