Class TransitNodeRoutingPrecomputation<V,E>
- java.lang.Object
-
- org.jgrapht.alg.shortestpath.TransitNodeRoutingPrecomputation<V,E>
-
- Type Parameters:
V
- graph vertex typeE
- graph edge type
class TransitNodeRoutingPrecomputation<V,E> extends java.lang.Object
Parallel implementation of the transit node routing route planning precomputation technique.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:
ContractionHierarchyPrecomputation
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static class
TransitNodeRoutingPrecomputation.AccessVertex<V,E>
Forward or backward access vertex computed for a certain vertex $v$ in the graph.static class
TransitNodeRoutingPrecomputation.AccessVertices<V,E>
Stores forward and backward access vertices computed for the transit node routing.private class
TransitNodeRoutingPrecomputation.AccessVerticesBuilder
Provides API to build anAccessVertices
object.private class
TransitNodeRoutingPrecomputation.AVAndLFConstructionTask
Task which is used to performContractionHierarchyBFS
in parallel.private class
TransitNodeRoutingPrecomputation.ContractionHierarchyBFS
BFS algorithm which is used to compute access vertices and locality filter.static class
TransitNodeRoutingPrecomputation.LocalityFilter<V>
Search space based locality filter.private class
TransitNodeRoutingPrecomputation.LocalityFilterBuilder
Provides API to build aLocalityFilter
object.private class
TransitNodeRoutingPrecomputation.PathsUnpackingTask
Task which is used to unpack contracted many-to-many shortest paths between transit vertices.(package private) static class
TransitNodeRoutingPrecomputation.TransitNodeRouting<V,E>
This class represents return type of this algorithm and contains all data computed during the execution of the algorithm.static class
TransitNodeRoutingPrecomputation.VoronoiDiagram<V>
Voronoi diagram for a graph.private class
TransitNodeRoutingPrecomputation.VoronoiDiagramComputation
Algorithm which computes Voronoi diagram for thecontractionGraph
.
-
Field Summary
Fields Modifier and Type Field Description private java.util.concurrent.ExecutorCompletionService<java.lang.Void>
completionService
Decorator forexecutor
that allows to keep track of when all submitted tasks are finished.private java.util.Set<ContractionHierarchyPrecomputation.ContractionVertex<V>>
contractedTransitVerticesSet
Set of contracted transit vertices.private Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionEdge<E>>
contractionGraph
Contracted graph.private ContractionHierarchyPrecomputation.ContractionHierarchy<V,E>
contractionHierarchy
Contraction hierarchy which is used to compute transit node routing.private java.util.Map<V,ContractionHierarchyPrecomputation.ContractionVertex<V>>
contractionMapping
Mapping of vertices in the initial graph to contracted vertices.private java.util.List<ContractionHierarchyPrecomputation.ContractionVertex<V>>
contractionVertices
List of contracted vertices.private java.util.concurrent.ExecutorService
executor
Executor to which parallel computation tasks are submitted.private java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>>
heapSupplier
Supplier for the preferable heap implementation.private ManyToManyShortestPathsAlgorithm<V,E>
manyToManyShortestPathsAlgorithm
Algorithm which is used to compute many-to-many shortest paths between transit vertices.private static int
NO_VORONOI_CELL
Special Voronoi diagram cell id to indicate, that a vertex does not belong to any cells.private int
numberOfTransitVertices
Number of transit vertices in the graph.private int
parallelism
Maximum number of threads used in the computations.private java.util.List<V>
transitVerticesList
List of transit vertices.private ManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths<V,E>
transitVerticesPaths
Many-to-many shortest paths between transit vertices.private java.util.Set<V>
transitVerticesSet
Set of transit vertices.private TransitNodeRoutingPrecomputation.VoronoiDiagram<V>
voronoiDiagram
Voronoi diagram for the contraction graph.
-
Constructor Summary
Constructors Constructor Description TransitNodeRoutingPrecomputation(ContractionHierarchyPrecomputation.ContractionHierarchy<V,E> hierarchy, int numberOfTransitVertices, java.util.concurrent.ThreadPoolExecutor executor)
Constructs an instance of the algorithm for a givencontractionHierarchy
,numberOfTransitVertices
andexecutor
.TransitNodeRoutingPrecomputation(ContractionHierarchyPrecomputation.ContractionHierarchy<V,E> hierarchy, int numberOfTransitVertices, java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>> heapSupplier, java.util.concurrent.ThreadPoolExecutor executor)
Constructs an instance of the algorithm for a givencontractionHierarchy
,parallelism
,numberOfTransitVertices
,heapSupplier
andexecutor
.TransitNodeRoutingPrecomputation(ContractionHierarchyPrecomputation.ContractionHierarchy<V,E> hierarchy, java.util.concurrent.ThreadPoolExecutor executor)
Constructs an instance of the algorithm for the givencontractionHierarchy
andexecutor
.TransitNodeRoutingPrecomputation(Graph<V,E> graph, java.util.concurrent.ThreadPoolExecutor executor)
Constructs an instance of the algorithm for a givengraph
andexecutor
.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private Pair<TransitNodeRoutingPrecomputation.AccessVertices<V,E>,TransitNodeRoutingPrecomputation.LocalityFilter<V>>
computeAVAndLF()
Computes in parallel access vertices and locality filter for the transit node routing.TransitNodeRoutingPrecomputation.TransitNodeRouting<V,E>
computeTransitNodeRouting()
Computes transit node routing based oncontractionHierarchy
.private void
fillContractionVerticesList()
FillscontractionVertices
with vertices fromcontractionGraph
.private java.util.Set<ContractionHierarchyPrecomputation.ContractionVertex<V>>
selectTopKTransitVertices(int numberOfTransitVertices)
Selects topnumberOfTransitVertices
vertices in the contraction hierarchy as transit vertices.private ManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths<V,E>
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 Detail
-
NO_VORONOI_CELL
private static final int NO_VORONOI_CELL
Special 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:
- Constant Field Values
-
contractionHierarchy
private ContractionHierarchyPrecomputation.ContractionHierarchy<V,E> contractionHierarchy
Contraction hierarchy which is used to compute transit node routing.
-
contractionGraph
private Graph<ContractionHierarchyPrecomputation.ContractionVertex<V>,ContractionHierarchyPrecomputation.ContractionEdge<E>> contractionGraph
Contracted graph.
-
contractionMapping
private java.util.Map<V,ContractionHierarchyPrecomputation.ContractionVertex<V>> contractionMapping
Mapping of vertices in the initial graph to contracted vertices.
-
numberOfTransitVertices
private int numberOfTransitVertices
Number of transit vertices in the graph.
-
parallelism
private int parallelism
Maximum number of threads used in the computations.
-
heapSupplier
private java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>> heapSupplier
Supplier for the preferable heap implementation. Provided heap is used to build Voronoi diagram.
-
contractionVertices
private java.util.List<ContractionHierarchyPrecomputation.ContractionVertex<V>> contractionVertices
List of contracted vertices. It is used to evenly distribute work between threads in the parallel computations.
-
manyToManyShortestPathsAlgorithm
private ManyToManyShortestPathsAlgorithm<V,E> manyToManyShortestPathsAlgorithm
Algorithm which is used to compute many-to-many shortest paths between transit vertices.
-
contractedTransitVerticesSet
private java.util.Set<ContractionHierarchyPrecomputation.ContractionVertex<V>> contractedTransitVerticesSet
Set of contracted transit vertices.
-
transitVerticesSet
private java.util.Set<V> transitVerticesSet
Set of transit vertices.
-
transitVerticesList
private java.util.List<V> transitVerticesList
List of transit vertices.
-
voronoiDiagram
private TransitNodeRoutingPrecomputation.VoronoiDiagram<V> voronoiDiagram
Voronoi diagram for the contraction graph. Here the transit vertices are used as cells centers.
-
transitVerticesPaths
private ManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths<V,E> transitVerticesPaths
Many-to-many shortest paths between transit vertices.
-
executor
private java.util.concurrent.ExecutorService executor
Executor to which parallel computation tasks are submitted.
-
completionService
private java.util.concurrent.ExecutorCompletionService<java.lang.Void> completionService
Decorator forexecutor
that allows to keep track of when all submitted tasks are finished.
-
-
Constructor Detail
-
TransitNodeRoutingPrecomputation
public TransitNodeRoutingPrecomputation(Graph<V,E> graph, java.util.concurrent.ThreadPoolExecutor executor)
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, java.util.concurrent.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, java.util.concurrent.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, java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>> heapSupplier, java.util.concurrent.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 Detail
-
computeTransitNodeRouting
public TransitNodeRoutingPrecomputation.TransitNodeRouting<V,E> 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 java.util.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>,TransitNodeRoutingPrecomputation.LocalityFilter<V>> computeAVAndLF()
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
-
-