Class TransitNodeRoutingPrecomputation<V,E>
- Type Parameters:
V
- graph vertex typeE
- graph edge type
This implementation is based on the ContractionHierarchyPrecomputation
.
The precomputation algorithm is described in the article: Arz, Julian & Luxen, Dennis & Sanders, Peter. (2013). Transit Node Routing Reconsidered. 7933. 10.1007/978-3-642-38527-8_7.
As mentioned is the original paper, TNR in itself is not a complete algorithm, but a framework which is used to speed up shortest paths computations. Formally the framework consists of the following parts:
- set $T ⊆ V$ of transit vertices;
- distance table $D_{T} : T × T → {\rm I\!R}^{+}_{0}$ of shortest path distances between the transit vertices;
- forward (backward) access vertex mapping $A^{↑} : V → 2^{T}$ ($A^{↓} : V → 2^{T}$). For any shortest $s$–$t$-path $P$ containing transit vertices, $A^{↑}(s)$ ($A^{↓}(t)$) must contain the first (last) transit vertex on $P$;
- locality filter $L : V × V → \{true, false\}$. $L(s, t)$ must be $true$ when no shortest path between $s$ and $t$ contains a transit vertex. False positives are allowed, i.e., $L(s, t)$ may sometimes be $true$ even when a shortest path contains a transit vertex.
To implement the TNR framework means to define how to select transit vertices and how to compute distance table $D_{T}$, access vertices and locality filter. This implementation selects transit vertices to be to $k$ vertices form the contraction hierarchy. For the details of how other parts of this TNR work please refer to the original paper.
For parallelization, this implementation relies on the ThreadPoolExecutor
which is
supplied to this algorithm from outside.
- See Also:
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionstatic class
Forward or backward access vertex computed for a certain vertex $v$ in the graph.static class
Stores forward and backward access vertices computed for the transit node routing.private class
Provides API to build anAccessVertices
object.private class
Task which is used to performContractionHierarchyBFS
in parallel.private class
BFS algorithm which is used to compute access vertices and locality filter.static class
Search space based locality filter.private class
Provides API to build aLocalityFilter
object.private class
Task which is used to unpack contracted many-to-many shortest paths between transit vertices.(package private) static class
This class represents return type of this algorithm and contains all data computed during the execution of the algorithm.static class
Voronoi diagram for a graph.private class
Algorithm which computes Voronoi diagram for thecontractionGraph
. -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate ExecutorCompletionService
<Void> Decorator forexecutor
that allows to keep track of when all submitted tasks are finished.Set of contracted transit vertices.private Graph
<ContractionHierarchyPrecomputation.ContractionVertex<V>, ContractionHierarchyPrecomputation.ContractionEdge<E>> Contracted graph.Contraction hierarchy which is used to compute transit node routing.Mapping of vertices in the initial graph to contracted vertices.List of contracted vertices.private ExecutorService
Executor to which parallel computation tasks are submitted.private Supplier
<org.jheaps.AddressableHeap<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> Supplier for the preferable heap implementation.private ManyToManyShortestPathsAlgorithm
<V, E> Algorithm which is used to compute many-to-many shortest paths between transit vertices.private static final int
Special Voronoi diagram cell id to indicate, that a vertex does not belong to any cells.private int
Number of transit vertices in the graph.private int
Maximum number of threads used in the computations.List of transit vertices.Many-to-many shortest paths between transit vertices.Set of transit vertices.Voronoi diagram for the contraction graph. -
Constructor Summary
ConstructorsConstructorDescriptionTransitNodeRoutingPrecomputation
(ContractionHierarchyPrecomputation.ContractionHierarchy<V, E> hierarchy, int numberOfTransitVertices, ThreadPoolExecutor executor) Constructs an instance of the algorithm for a givencontractionHierarchy
,numberOfTransitVertices
andexecutor
.TransitNodeRoutingPrecomputation
(ContractionHierarchyPrecomputation.ContractionHierarchy<V, E> hierarchy, int numberOfTransitVertices, Supplier<org.jheaps.AddressableHeap<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> heapSupplier, ThreadPoolExecutor executor) Constructs an instance of the algorithm for a givencontractionHierarchy
,parallelism
,numberOfTransitVertices
,heapSupplier
andexecutor
.TransitNodeRoutingPrecomputation
(ContractionHierarchyPrecomputation.ContractionHierarchy<V, E> hierarchy, ThreadPoolExecutor executor) Constructs an instance of the algorithm for the givencontractionHierarchy
andexecutor
.TransitNodeRoutingPrecomputation
(Graph<V, E> graph, ThreadPoolExecutor executor) Constructs an instance of the algorithm for a givengraph
andexecutor
. -
Method Summary
Modifier and TypeMethodDescriptionprivate Pair
<TransitNodeRoutingPrecomputation.AccessVertices<V, E>, TransitNodeRoutingPrecomputation.LocalityFilter<V>> Computes in parallel access vertices and locality filter for the transit node routing.Computes transit node routing based oncontractionHierarchy
.private void
FillscontractionVertices
with vertices fromcontractionGraph
.selectTopKTransitVertices
(int numberOfTransitVertices) Selects topnumberOfTransitVertices
vertices in the contraction hierarchy as transit vertices.unpackPaths
(ManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths<V, E> shortestPaths) Unpacks in parallel contracted paths stored inshortestPaths
.private void
waitForTasksCompletion
(int numberOfTasks) TakesnumberOfTasks
tasks from thecompletionService
.private int
workerSegmentEnd
(int segmentStart, int segmentEnd, int taskId) Computes end of the working chunk for this task.private int
workerSegmentStart
(int segmentStart, int segmentEnd, int taskId) Computes start of the working chunk for this task.
-
Field Details
-
NO_VORONOI_CELL
private static final int NO_VORONOI_CELLSpecial Voronoi diagram cell id to indicate, that a vertex does not belong to any cells. For usual Voronoi cell the ids of contracted vertices are used. Once those ids are non-negative, this value is guaranteed to be unique.- See Also:
-
contractionHierarchy
Contraction hierarchy which is used to compute transit node routing. -
contractionGraph
private Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraphContracted graph. -
contractionMapping
Mapping of vertices in the initial graph to contracted vertices. -
numberOfTransitVertices
private int numberOfTransitVerticesNumber of transit vertices in the graph. -
parallelism
private int parallelismMaximum number of threads used in the computations. -
heapSupplier
private Supplier<org.jheaps.AddressableHeap<Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>> heapSupplierSupplier for the preferable heap implementation. Provided heap is used to build Voronoi diagram. -
contractionVertices
List of contracted vertices. It is used to evenly distribute work between threads in the parallel computations. -
manyToManyShortestPathsAlgorithm
Algorithm which is used to compute many-to-many shortest paths between transit vertices. -
contractedTransitVerticesSet
Set of contracted transit vertices. -
transitVerticesSet
Set of transit vertices. -
transitVerticesList
List of transit vertices. -
voronoiDiagram
Voronoi diagram for the contraction graph. Here the transit vertices are used as cells centers. -
transitVerticesPaths
Many-to-many shortest paths between transit vertices. -
executor
Executor to which parallel computation tasks are submitted. -
completionService
Decorator forexecutor
that allows to keep track of when all submitted tasks are finished.
-
-
Constructor Details
-
TransitNodeRoutingPrecomputation
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
. Utility methods to manage aThreadPoolExecutor
seeConcurrencyUtil
.- Parameters:
graph
- graphexecutor
- executor which will be used for parallelization
-
TransitNodeRoutingPrecomputation
public TransitNodeRoutingPrecomputation(ContractionHierarchyPrecomputation.ContractionHierarchy<V, E> hierarchy, ThreadPoolExecutor executor) Constructs an instance of the algorithm for the givencontractionHierarchy
andexecutor
. 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:
hierarchy
- contraction hierarchyexecutor
- executor which will be used for parallelization
-
TransitNodeRoutingPrecomputation
public TransitNodeRoutingPrecomputation(ContractionHierarchyPrecomputation.ContractionHierarchy<V, E> hierarchy, int numberOfTransitVertices, ThreadPoolExecutor executor) Constructs an instance of the algorithm for a givencontractionHierarchy
,numberOfTransitVertices
andexecutor
. 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:
hierarchy
- contraction hierarchynumberOfTransitVertices
- number of transit verticesexecutor
- executor which will be used for parallelization
-
TransitNodeRoutingPrecomputation
public TransitNodeRoutingPrecomputation(ContractionHierarchyPrecomputation.ContractionHierarchy<V, E> hierarchy, int numberOfTransitVertices, Supplier<org.jheaps.AddressableHeap<Double, ContractionHierarchyPrecomputation.ContractionVertex<V>>> heapSupplier, ThreadPoolExecutor executor) Constructs an instance of the algorithm for a givencontractionHierarchy
,parallelism
,numberOfTransitVertices
,heapSupplier
andexecutor
. Heap provided by theheapSupplier
is used which computing the Voronoi diagram. 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:
hierarchy
- contraction hierarchynumberOfTransitVertices
- number of transit verticesheapSupplier
- supplier for preferable heap implementationexecutor
- executor which will be used for parallelization
-
-
Method Details
-
computeTransitNodeRouting
Computes transit node routing based oncontractionHierarchy
.- Returns:
- transit node routing
-
fillContractionVerticesList
private void fillContractionVerticesList()FillscontractionVertices
with vertices fromcontractionGraph
. For each vertex its position in the list is equal to itsid
. -
unpackPaths
private ManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths<V,E> unpackPaths(ManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths<V, E> shortestPaths) Unpacks in parallel contracted paths stored inshortestPaths
. Unpacked path are returned asDefaultManyToManyShortestPaths.DefaultManyToManyShortestPathsImpl
.- Parameters:
shortestPaths
- contracted many-to-many shortest paths- Returns:
- unpacked paths
-
selectTopKTransitVertices
private Set<ContractionHierarchyPrecomputation.ContractionVertex<V>> selectTopKTransitVertices(int numberOfTransitVertices) Selects topnumberOfTransitVertices
vertices in the contraction hierarchy as transit vertices.- Parameters:
numberOfTransitVertices
- number of transit vertices to select- Returns:
- set of transit vertices
-
computeAVAndLF
private Pair<TransitNodeRoutingPrecomputation.AccessVertices<V,E>, computeAVAndLF()TransitNodeRoutingPrecomputation.LocalityFilter<V>> Computes in parallel access vertices and locality filter for the transit node routing.- Returns:
- pair of access vertices and locality filter.
-
waitForTasksCompletion
private void waitForTasksCompletion(int numberOfTasks) TakesnumberOfTasks
tasks from thecompletionService
.- Parameters:
numberOfTasks
- number of tasks
-
workerSegmentStart
private int workerSegmentStart(int segmentStart, int segmentEnd, int taskId) Computes start of the working chunk for this task.- Parameters:
segmentStart
- working segment startsegmentEnd
- working segment end- Returns:
- working chunk start
-
workerSegmentEnd
private int workerSegmentEnd(int segmentStart, int segmentEnd, int taskId) Computes end of the working chunk for this task.- Parameters:
segmentStart
- working segment startsegmentEnd
- working segment end- Returns:
- working chunk end
-