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.). 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 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.private class
ContractionHierarchyPrecomputation.ContractionTask
Task that is used to perform computing of initial priorities, independent set and shortcuts, updating neighbours priorities and marking upward edges.static class
ContractionHierarchyPrecomputation.ContractionVertex<V1>
Vertex for building the contraction hierarchy, which contains an original vertex fromgraph
.private class
ContractionHierarchyPrecomputation.ToListConsumer
Caches passed shortcuts into a list.private class
ContractionHierarchyPrecomputation.ToStatisticsConsumer
Uses passed shortcuts to computeaddedContractionEdges
andaddedOriginalEdges
statistics.private static class
ContractionHierarchyPrecomputation.VertexData
Contains information of a vertex needed during the contraction.private static class
ContractionHierarchyPrecomputation.VertexStatistics
Contains statistics corresponding to a vertex incontractionGraph
needed to compute its priority.
-
Field Summary
Fields Modifier and Type Field Description private java.util.concurrent.ExecutorCompletionService<java.lang.Void>
completionService
Decorator forThreadPoolExecutor
supplied to this algorithm that enables to keep track of when all submitted tasks are finished.private java.util.function.Consumer<ContractionHierarchyPrecomputation.ContractionVertex<V>>
computeIndependentSetConsumer
Computes independent set during contraction.private java.util.List<java.util.function.Consumer<ContractionHierarchyPrecomputation.ContractionVertex<V>>>
computeInitialPrioritiesConsumers
Consumers that perform computation of initial priorities for vertices incontractionGraph
.private java.util.function.Consumer<ContractionHierarchyPrecomputation.ContractionVertex<V>>
computeShortcutsConsumer
Computes shortcuts for a vertex.private Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionEdge<E>>
contractionGraph
Graph that stores the computed contraction hierarchy.private java.util.concurrent.atomic.AtomicInteger
contractionLevelCounter
Counter of contraction level that should be assigned to vertex that is being contracted.private java.util.Map<V,ContractionHierarchyPrecomputation.ContractionVertex<V>>
contractionMapping
Mapping of the vertices in the original graph to the vertices in the contraction hierarchy graph.private Graph<V,E>
graph
The underlying graph.private java.util.function.Consumer<ContractionHierarchyPrecomputation.ContractionVertex<V>>
markUpwardEdgesConsumer
Sets value ofisUpward
for the outgoing edges of a vertex.private Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionEdge<E>>
maskedContractionGraph
The immutable view of thecontractionGraph
which masks already contracted vertices.private int
parallelism
Maximum number of threads used in the computations.private java.util.List<java.util.List<Pair<ContractionHierarchyPrecomputation.ContractionEdge<E>,ContractionHierarchyPrecomputation.ContractionEdge<E>>>>
shortcutEdges
Lists of shortcuts that correspond to vertices in thecontractionGraph
.private java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>>
shortcutsSearchHeapSupplier
Supplier for the preferable heap implementation.private java.util.List<ContractionHierarchyPrecomputation.ContractionTask>
tasks
Tasks that are submitted to theexecutor
.private java.util.function.Consumer<ContractionHierarchyPrecomputation.ContractionVertex<V>>
updateNeighboursConsumer
Updates neighbours priorities of a vertex.private java.util.List<ContractionHierarchyPrecomputation.ContractionVertex<V>>
vertices
Vertices of thecontractionGraph
.private java.util.List<ContractionHierarchyPrecomputation.VertexData>
verticesData
Data of each vertex int thecontractionGraph
.
-
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
.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
contractVertices()
Performs contraction of vertices incontractionGraph
.private void
fillContractionGraphAndVerticesArray()
FillscontractionGraph
andvertices
.private java.util.List<Pair<ContractionHierarchyPrecomputation.ContractionEdge<E>,ContractionHierarchyPrecomputation.ContractionEdge<E>>>
getShortcuts(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex)
Computes shortcuts for vertexvertex
wrt the overlay graph.private ContractionHierarchyPrecomputation.VertexStatistics
getStatistics(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex)
Computes statistics for specifiedvertex
.private ContractionHierarchyPrecomputation.VertexData
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, 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)
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, java.util.function.BiConsumer<ContractionHierarchyPrecomputation.ContractionEdge<E>,ContractionHierarchyPrecomputation.ContractionEdge<E>> shortcutConsumer)
Runs forward shortest-path searches in current overlay graph to find shortcuts ofvertex
.private java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,org.jheaps.AddressableHeap.Handle<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>>
iterateToSuccessors(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionEdge<E>> graph, ContractionHierarchyPrecomputation.ContractionVertex<V> source, java.util.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<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>> heap, java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,org.jheaps.AddressableHeap.Handle<java.lang.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, java.util.function.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, java.util.List<java.util.function.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
swap(java.util.List<T> list, int i, int j)
Swaps elements inlist
on the positionsi
andj
.private void
updateDistance(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex, double distance, org.jheaps.AddressableHeap<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>> heap, java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,org.jheaps.AddressableHeap.Handle<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>> distanceMap)
Updates distance forvertex
in theheap
if needed.private void
updateNeighboursData(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex)
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
vertexIsIndependent(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex)
Determines if avertex
is independent wrt the overlay graph.private void
waitForTasksCompletion(int numOfTasks)
TakesnumOfTasks
tasks from thecompletionService
.
-
-
-
Field Detail
-
contractionGraph
private Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraph
Graph that stores the computed contraction hierarchy.
-
contractionMapping
private java.util.Map<V,ContractionHierarchyPrecomputation.ContractionVertex<V>> 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>> maskedContractionGraph
The immutable view of thecontractionGraph
which masks already contracted vertices. It is used to determine overlay graph during the computations.
-
vertices
private java.util.List<ContractionHierarchyPrecomputation.ContractionVertex<V>> vertices
Vertices of thecontractionGraph
.
-
shortcutEdges
private java.util.List<java.util.List<Pair<ContractionHierarchyPrecomputation.ContractionEdge<E>,ContractionHierarchyPrecomputation.ContractionEdge<E>>>> shortcutEdges
Lists 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
private java.util.List<ContractionHierarchyPrecomputation.VertexData> verticesData
Data of each vertex int thecontractionGraph
. The id of a vertex is the position in this list, where corresponding data is stored.
-
contractionLevelCounter
private java.util.concurrent.atomic.AtomicInteger 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 java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>> shortcutsSearchHeapSupplier
Supplier for the preferable heap implementation.
-
completionService
private java.util.concurrent.ExecutorCompletionService<java.lang.Void> completionService
Decorator forThreadPoolExecutor
supplied to this algorithm that enables to keep track of when all submitted tasks are finished.
-
parallelism
private int parallelism
Maximum number of threads used in the computations.
-
tasks
private java.util.List<ContractionHierarchyPrecomputation.ContractionTask> tasks
Tasks that are submitted to theexecutor
.
-
computeInitialPrioritiesConsumers
private java.util.List<java.util.function.Consumer<ContractionHierarchyPrecomputation.ContractionVertex<V>>> computeInitialPrioritiesConsumers
Consumers 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 java.util.function.Consumer<ContractionHierarchyPrecomputation.ContractionVertex<V>> computeIndependentSetConsumer
Computes independent set during contraction.
-
computeShortcutsConsumer
private java.util.function.Consumer<ContractionHierarchyPrecomputation.ContractionVertex<V>> computeShortcutsConsumer
Computes shortcuts for a vertex.
-
updateNeighboursConsumer
private java.util.function.Consumer<ContractionHierarchyPrecomputation.ContractionVertex<V>> updateNeighboursConsumer
Updates neighbours priorities of a vertex.
-
markUpwardEdgesConsumer
private java.util.function.Consumer<ContractionHierarchyPrecomputation.ContractionVertex<V>> markUpwardEdgesConsumer
Sets value ofisUpward
for the outgoing edges of a vertex.
-
-
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
-
init
private void init(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)
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
public ContractionHierarchyPrecomputation.ContractionHierarchy<V,E> 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
private boolean vertexIsIndependent(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex)
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
private <T> void swap(java.util.List<T> list, int i, int j)
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
private void updateNeighboursData(ContractionHierarchyPrecomputation.ContractionVertex<V> vertex)
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 java.util.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, java.util.function.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 java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,org.jheaps.AddressableHeap.Handle<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>> iterateToSuccessors(Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionEdge<E>> graph, ContractionHierarchyPrecomputation.ContractionVertex<V> source, java.util.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<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>> heap, java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,org.jheaps.AddressableHeap.Handle<java.lang.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<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>> heap, java.util.Map<ContractionHierarchyPrecomputation.ContractionVertex<V>,org.jheaps.AddressableHeap.Handle<java.lang.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, java.util.function.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, java.util.List<java.util.function.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
-
-