Class ContractionHierarchyPrecomputation<V,E>
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
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 it`s 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 ThreadPoolExecutor
which is
supplied to this algorithm from outside.
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionstatic class
Edge for building the contraction hierarchy.static class
Return type of this algorithm.private class
Task that is used to perform computing of initial priorities, independent set and shortcuts, updating neighbours priorities and marking upward edges.static class
Vertex for building the contraction hierarchy, which contains an original vertex fromgraph
.private class
Caches passed shortcuts into a list.private class
Uses passed shortcuts to computeaddedContractionEdges
andaddedOriginalEdges
statistics.private static class
Contains information of a vertex needed during the contraction.private static class
Contains statistics corresponding to a vertex incontractionGraph
needed to compute its priority. -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate ExecutorCompletionService
<Void> Decorator forThreadPoolExecutor
supplied to this algorithm that enables to keep track of when all submitted tasks are finished.Computes independent set during contraction.Consumers that perform computation of initial priorities for vertices incontractionGraph
.Computes shortcuts for a vertex.private Graph
<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> Graph that stores the computed contraction hierarchy.private AtomicInteger
Counter of contraction level that should be assigned to vertex that is being contracted.Mapping of the vertices in the original graph to the vertices in the contraction hierarchy graph.The underlying graph.Sets value ofisUpward
for the outgoing edges of a vertex.private Graph
<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> The immutable view of thecontractionGraph
which masks already contracted vertices.private int
Maximum number of threads used in the computations.private List
<List<Pair<ContractionHierarchyPrecomputation.ContractionEdge<E>, ContractionHierarchyPrecomputation.ContractionEdge<E>>>> Lists of shortcuts that correspond to vertices in thecontractionGraph
.private Supplier
<org.jheaps.AddressableHeap<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> Supplier for the preferable heap implementation.private List
<ContractionHierarchyPrecomputation<V, E>.ContractionTask> Tasks that are submitted to theexecutor
.Updates neighbours priorities of a vertex.Vertices of thecontractionGraph
.Data of each vertex int thecontractionGraph
. -
Constructor Summary
ConstructorsConstructorDescriptionContractionHierarchyPrecomputation
(Graph<V, E> graph, ThreadPoolExecutor executor) Constructs a new instance of the algorithm for a givengraph
andexecutor
.ContractionHierarchyPrecomputation
(Graph<V, E> graph, Supplier<Random> randomSupplier, ThreadPoolExecutor executor) Constructs a new instance of the algorithm for a givengraph
,randomSupplier
andexecutor
.ContractionHierarchyPrecomputation
(Graph<V, E> graph, Supplier<Random> randomSupplier, Supplier<org.jheaps.AddressableHeap<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> shortcutsSearchHeapSupplier, ThreadPoolExecutor executor) Constructs a new instance of the algorithm for a givengraph
,parallelism
,randomSupplier
,shortcutsSearchHeapSupplier
andexecutor
. -
Method Summary
Modifier and TypeMethodDescriptionComputes contraction hierarchy forgraph
.private void
contractIndependentSet
(int independentSetStart, int independentSetEnd) Contracts vertices in the current independent set.private void
contractVertex
(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, int contractionLevel) Contracts providedvertex
and assigns the specifiedcontractionLevel
to it.private void
Performs contraction of vertices incontractionGraph
.private void
FillscontractionGraph
andvertices
.private List
<Pair<ContractionHierarchyPrecomputation.ContractionEdge<E>, ContractionHierarchyPrecomputation.ContractionEdge<E>>> Computes shortcuts for vertexvertex
wrt the overlay graph.Computes statistics for specifiedvertex
.getVertexData
(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, int random) Creates an instance ofVertexData
forvertex
using specified random number and sets itspriority
value.private void
init
(Graph<V, E> graph, Supplier<Random> randomSupplier, Supplier<org.jheaps.AddressableHeap<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> shortcutsSearchHeapSupplier, ThreadPoolExecutor executor) Initialized field of this algorithm.private boolean
isGreater
(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex1, ContractionHierarchyPrecomputation.ContractionVertex<V> vertex2) Determines if priority ofvertex1
is greater than the priority ofvertex2
.private void
iterateShortcutEdges
(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, BiConsumer<ContractionHierarchyPrecomputation.ContractionEdge<E>, ContractionHierarchyPrecomputation.ContractionEdge<E>> shortcutConsumer) Runs forward shortest-path searches in current overlay graph to find shortcuts ofvertex
.private Map
<ContractionHierarchyPrecomputation.ContractionVertex<V>, org.jheaps.AddressableHeap.Handle<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> iterateToSuccessors
(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> graph, ContractionHierarchyPrecomputation.ContractionVertex<V> source, Set<ContractionHierarchyPrecomputation.ContractionVertex<V>> successors, ContractionHierarchyPrecomputation.ContractionVertex<V> vertexToIgnore, double radius) Performs Dijkstra search in thegraph
starting at vertexsource
ignoring vertexvertexToIgnore
.private void
markContracted
(int independentSetStart, int independentSetEnd) Sets value ofisContracted
field ofVertexData
for each vertex in the segment $[independentSetStart,independentSetEnd)$ to $true$.private int
partitionIndependentSet
(int notContractedVerticesEnd) Partitions vertices invertices
on the segment $[0,notContractedVerticesEnd)$ into correspondingly not independent and independent.private void
relaxNode
(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> graph, org.jheaps.AddressableHeap<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>> heap, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, org.jheaps.AddressableHeap.Handle<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> distanceMap, ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, double vertexDistance, ContractionHierarchyPrecomputation.ContractionVertex<V> vertexToIgnore) Relaxes outgoing edges ofvertex
ingraph
ignoring successors marked as independent andvertexToIgnore
.private void
submitTasks
(int segmentStart, int segmentEnd, Consumer<ContractionHierarchyPrecomputation.ContractionVertex<V>> consumer) Submitstasks
to thecompletionService
setting start and end of the working segment and consumer for themprivate void
submitTasks
(int segmentStart, int segmentEnd, List<Consumer<ContractionHierarchyPrecomputation.ContractionVertex<V>>> consumers) Submitstasks
to thecompletionService
setting start and end of the working segment and an individual instance of consumer provided inconsumers
.private <T> void
Swaps elements inlist
on the positionsi
andj
.private void
updateDistance
(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, double distance, org.jheaps.AddressableHeap<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>> heap, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, org.jheaps.AddressableHeap.Handle<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> distanceMap) Updates distance forvertex
in theheap
if needed.private void
Updates neighbours priorities and theirsdepth
values for a givenvertex
.private void
updatePriority
(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, ContractionHierarchyPrecomputation.VertexData data) Updatespriority
field value ofdata
, which corresponds to thevertex
.private boolean
Determines if avertex
is independent wrt the overlay graph.private void
waitForTasksCompletion
(int numOfTasks) TakesnumOfTasks
tasks from thecompletionService
.
-
Field Details
-
graph
The underlying graph. -
contractionGraph
private Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraphGraph that stores the computed contraction hierarchy. -
contractionMapping
Mapping of the vertices in the original graph to the vertices in the contraction hierarchy graph. -
maskedContractionGraph
private Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionEdge<E>> maskedContractionGraphThe immutable view of thecontractionGraph
which masks already contracted vertices. It is used to determine overlay graph during the computations. -
vertices
Vertices of thecontractionGraph
. -
shortcutEdges
private List<List<Pair<ContractionHierarchyPrecomputation.ContractionEdge<E>,ContractionHierarchyPrecomputation.ContractionEdge<E>>>> shortcutEdgesLists of shortcuts that correspond to vertices in thecontractionGraph
. The id of a vertex is the position in this array, where corresponding shortcuts are stored. -
verticesData
Data of each vertex int thecontractionGraph
. The id of a vertex is the position in this list, where corresponding data is stored. -
contractionLevelCounter
Counter of contraction level that should be assigned to vertex that is being contracted. Variable is made atomic due to the concurrent updates in the computations. -
shortcutsSearchHeapSupplier
private Supplier<org.jheaps.AddressableHeap<Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>> shortcutsSearchHeapSupplierSupplier for the preferable heap implementation. -
completionService
Decorator forThreadPoolExecutor
supplied to this algorithm that enables to keep track of when all submitted tasks are finished. -
parallelism
private int parallelismMaximum number of threads used in the computations. -
tasks
Tasks that are submitted to theexecutor
. -
computeInitialPrioritiesConsumers
private List<Consumer<ContractionHierarchyPrecomputation.ContractionVertex<V>>> computeInitialPrioritiesConsumersConsumers that perform computation of initial priorities for vertices incontractionGraph
. Each consumer holds an instance of theRandom
class to avoid concurrent calls to single instance. -
computeIndependentSetConsumer
private Consumer<ContractionHierarchyPrecomputation.ContractionVertex<V>> computeIndependentSetConsumerComputes independent set during contraction. -
computeShortcutsConsumer
Computes shortcuts for a vertex. -
updateNeighboursConsumer
Updates neighbours priorities of a vertex. -
markUpwardEdgesConsumer
Sets value ofisUpward
for the outgoing edges of a vertex.
-
-
Constructor Details
-
ContractionHierarchyPrecomputation
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, Supplier<Random> randomSupplier, 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, Supplier<Random> randomSupplier, Supplier<org.jheaps.AddressableHeap<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> shortcutsSearchHeapSupplier, 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 Details
-
init
private void init(Graph<V, E> graph, Supplier<Random> randomSupplier, Supplier<org.jheaps.AddressableHeap<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> shortcutsSearchHeapSupplier, ThreadPoolExecutor executor) Initialized field of this algorithm.- Parameters:
graph
- a graphrandomSupplier
- supplier for preferable instances ofRandom
shortcutsSearchHeapSupplier
- supplier for the preferable heap implementation.executor
- executor which will be used for parallelization
-
computeContractionHierarchy
Computes contraction hierarchy forgraph
.- Returns:
- contraction hierarchy and mapping of original to contracted vertices
-
fillContractionGraphAndVerticesArray
private void fillContractionGraphAndVerticesArray()FillscontractionGraph
andvertices
. If there exist multiple edges between two vertices in the original graph, the shortest is added to thecontractionGraph
. Self loops of the original graph are ignored. If original graph is undirected, each edge is transformed into two directed edges in the contraction graph. -
contractVertices
private void contractVertices()Performs contraction of vertices incontractionGraph
. -
vertexIsIndependent
Determines if avertex
is independent wrt the overlay graph.- Parameters:
vertex
- vertex- Returns:
- true iff vertex is independent
-
isGreater
private boolean isGreater(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex1, ContractionHierarchyPrecomputation.ContractionVertex<V> vertex2) Determines if priority ofvertex1
is greater than the priority ofvertex2
. If priorities stored inverticesData
are equal, the tie breaking rule is used. First random values inverticesData
are checked. If they are also equal, ids of vertices are inspected. Each vertex has a unique id which guaranties that on each iteration there exists at least one independent vertex.- Returns:
- true iff priority of
vertex1
is greater thanvertex2
-
partitionIndependentSet
private int partitionIndependentSet(int notContractedVerticesEnd) Partitions vertices invertices
on the segment $[0,notContractedVerticesEnd)$ into correspondingly not independent and independent.- Parameters:
notContractedVerticesEnd
- position after the last not yet contracted vertex invertices
- Returns:
- position of first independent vertex in created partition
-
swap
Swaps elements inlist
on the positionsi
andj
.- Parameters:
list
- listi
- position of first elementj
- position of second element
-
contractIndependentSet
private void contractIndependentSet(int independentSetStart, int independentSetEnd) Contracts vertices in the current independent set. This step should be performed sequentially because thecontractionGraph
is not thread-safe.- Parameters:
independentSetStart
- first vertex in the independent setindependentSetEnd
- position after the last vertex in the independent set
-
contractVertex
private void contractVertex(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, int contractionLevel) Contracts providedvertex
and assigns the specifiedcontractionLevel
to it.- Parameters:
vertex
- vertex to contractcontractionLevel
- vertex contraction level
-
updateNeighboursData
Updates neighbours priorities and theirsdepth
values for a givenvertex
. MethodGraphs.neighborSetOf(Graph, Object)
is used to traverse neighbours.- Parameters:
vertex
- a vertex in thecontractionGraph
-
getVertexData
private ContractionHierarchyPrecomputation.VertexData getVertexData(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, int random) Creates an instance ofVertexData
forvertex
using specified random number and sets itspriority
value.- Parameters:
vertex
- a vertex incontractionGraph
random
- random number- Returns:
- created
VertexData
-
updatePriority
private void updatePriority(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, ContractionHierarchyPrecomputation.VertexData data) Updatespriority
field value ofdata
, which corresponds to thevertex
.- Parameters:
vertex
- a vertex in thecontractionGraph
data
- data of vertex
-
getStatistics
private ContractionHierarchyPrecomputation.VertexStatistics getStatistics(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex) Computes statistics for specifiedvertex
.- Parameters:
vertex
- a vertex in thecontractionGraph
- Returns:
- statistics of
vertex
-
getShortcuts
private List<Pair<ContractionHierarchyPrecomputation.ContractionEdge<E>,ContractionHierarchyPrecomputation.ContractionEdge<E>>> getShortcuts(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex) Computes shortcuts for vertexvertex
wrt the overlay graph.- Parameters:
vertex
- a vertex incontractionGraph
- Returns:
- list of shortcuts
-
iterateShortcutEdges
private void iterateShortcutEdges(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, BiConsumer<ContractionHierarchyPrecomputation.ContractionEdge<E>, ContractionHierarchyPrecomputation.ContractionEdge<E>> shortcutConsumer) Runs forward shortest-path searches in current overlay graph to find shortcuts ofvertex
. Thevertex
itself is ignored. AppliesshortcutConsumer
whenever a new shortcut is found. To prune the search, keeps track of the value $d(u, v) + max {c(v, w) : (v, w) \in E^{\prime}}$, where $d(u,v)$ denotes distance between vertex $u$ and $v$, $c(v,w)$ is weight of the edge $(v,w)$, $E^{\prime}$ is the set of edges of the overlay graph. If the original graph is undirected each predecessor ofvertex
is considered only once and for each found shortcut in the forward direction another one in the backward direction is generated.- Parameters:
vertex
- a vertex incontractionGraph
shortcutConsumer
- consumer to supply shortcuts to
-
iterateToSuccessors
private Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,org.jheaps.AddressableHeap.Handle<Double, iterateToSuccessorsContractionHierarchyPrecomputation.ContractionVertex<V>>> (Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> graph, ContractionHierarchyPrecomputation.ContractionVertex<V> source, Set<ContractionHierarchyPrecomputation.ContractionVertex<V>> successors, ContractionHierarchyPrecomputation.ContractionVertex<V> vertexToIgnore, double radius) Performs Dijkstra search in thegraph
starting at vertexsource
ignoring vertexvertexToIgnore
. The search is limited byradius
. The search is proceeded until all vertices insuccessors
are reached or there is no vertex left to traverse.- Parameters:
graph
- graph to traversesource
- search start vertexsuccessors
- vertices to reachvertexToIgnore
- vertex to ignoreradius
- search distance limit- Returns:
- computed distances for reached vertices
-
relaxNode
private void relaxNode(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> graph, org.jheaps.AddressableHeap<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>> heap, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, org.jheaps.AddressableHeap.Handle<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> distanceMap, ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, double vertexDistance, ContractionHierarchyPrecomputation.ContractionVertex<V> vertexToIgnore) Relaxes outgoing edges ofvertex
ingraph
ignoring successors marked as independent andvertexToIgnore
.- Parameters:
graph
- graphheap
- search priority queuedistanceMap
- vertex distancesvertex
- vertex to relaxvertexDistance
- update distance forvertex
vertexToIgnore
- vertex to ignore
-
updateDistance
private void updateDistance(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, double distance, org.jheaps.AddressableHeap<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>> heap, Map<ContractionHierarchyPrecomputation.ContractionVertex<V>, org.jheaps.AddressableHeap.Handle<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> distanceMap) Updates distance forvertex
in theheap
if needed.- Parameters:
vertex
- vertexdistance
- updated distanceheap
- search priority queuedistanceMap
- vertex distances
-
markContracted
private void markContracted(int independentSetStart, int independentSetEnd) Sets value ofisContracted
field ofVertexData
for each vertex in the segment $[independentSetStart,independentSetEnd)$ to $true$. This step should not interfere with other steps during the contraction because it alters themaskedContractionGraph
.- Parameters:
independentSetStart
- start of independent setindependentSetEnd
- end of independent set
-
submitTasks
private void submitTasks(int segmentStart, int segmentEnd, Consumer<ContractionHierarchyPrecomputation.ContractionVertex<V>> consumer) Submitstasks
to thecompletionService
setting start and end of the working segment and consumer for them- Parameters:
segmentStart
- start of working segment inclusivelysegmentEnd
- start of working segment exclusivelyconsumer
- consumer
-
submitTasks
private void submitTasks(int segmentStart, int segmentEnd, List<Consumer<ContractionHierarchyPrecomputation.ContractionVertex<V>>> consumers) Submitstasks
to thecompletionService
setting start and end of the working segment and an individual instance of consumer provided inconsumers
.- Parameters:
segmentStart
- start of working segment inclusivelysegmentEnd
- start of working segment exclusivelyconsumers
- consumers
-
waitForTasksCompletion
private void waitForTasksCompletion(int numOfTasks) TakesnumOfTasks
tasks from thecompletionService
.- Parameters:
numOfTasks
- number of tasks
-