Module org.jgrapht.core
Package org.jgrapht.alg.shortestpath

Class TransitNodeRoutingPrecomputation<V,​E>

  • Type Parameters:
    V - graph vertex type
    E - 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

    • 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

      • 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.

      • manyToManyShortestPathsAlgorithm

        private ManyToManyShortestPathsAlgorithm<V,​E> manyToManyShortestPathsAlgorithm
        Algorithm which is used to compute many-to-many shortest paths between transit vertices.

      • transitVerticesSet

        private java.util.Set<V> transitVerticesSet
        Set of transit vertices.

      • transitVerticesList

        private java.util.List<V> transitVerticesList
        List of 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 for executor 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 given graph and executor. It is up to a user of this algorithm to handle the creation and termination of the provided executor. Utility methods to manage a ThreadPoolExecutor see ConcurrencyUtil.
        Parameters:
        graph - graph
        executor - 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 given contractionHierarchy and executor. It is up to a user of this algorithm to handle the creation and termination of the provided executor. Utility methods to manage a ThreadPoolExecutor see ConcurrencyUtil.
        Parameters:
        hierarchy - contraction hierarchy
        executor - 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 given contractionHierarchy, numberOfTransitVertices and executor. It is up to a user of this algorithm to handle the creation and termination of the provided executor. Utility methods to manage a ThreadPoolExecutor see ConcurrencyUtil.
        Parameters:
        hierarchy - contraction hierarchy
        numberOfTransitVertices - number of transit vertices
        executor - 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 given contractionHierarchy, parallelism, numberOfTransitVertices, heapSupplier and executor. Heap provided by the heapSupplier is used which computing the Voronoi diagram. It is up to a user of this algorithm to handle the creation and termination of the provided executor. Utility methods to manage a ThreadPoolExecutor see ConcurrencyUtil.
        Parameters:
        hierarchy - contraction hierarchy
        numberOfTransitVertices - number of transit vertices
        heapSupplier - supplier for preferable heap implementation
        executor - executor which will be used for parallelization

    • Method Detail

      • fillContractionVerticesList

        private void fillContractionVerticesList()
        Fills contractionVertices with vertices from contractionGraph. For each vertex its position in the list is equal to its id.

      • selectTopKTransitVertices

        private java.util.Set<ContractionHierarchyPrecomputation.ContractionVertex<V>> selectTopKTransitVertices​(int numberOfTransitVertices)
        Selects top numberOfTransitVertices vertices in the contraction hierarchy as transit vertices.
        Parameters:
        numberOfTransitVertices - number of transit vertices to select
        Returns:
        set of transit vertices

      • waitForTasksCompletion

        private void waitForTasksCompletion​(int numberOfTasks)
        Takes numberOfTasks tasks from the completionService.
        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 start
        segmentEnd - 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 start
        segmentEnd - working segment end
        Returns:
        working chunk end