Class TransitNodeRoutingPrecomputation<V,E>

java.lang.Object
org.jgrapht.alg.shortestpath.TransitNodeRoutingPrecomputation<V,E>
Type Parameters:
V - graph vertex type
E - graph edge type

class TransitNodeRoutingPrecomputation<V,E> extends 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:
  • Field Details

  • Constructor Details

    • TransitNodeRoutingPrecomputation

      public TransitNodeRoutingPrecomputation(Graph<V,E> graph, 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, 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, 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, Supplier<org.jheaps.AddressableHeap<Double,ContractionHierarchyPrecomputation.ContractionVertex<V>>> heapSupplier, 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 Details

    • computeTransitNodeRouting

      public TransitNodeRoutingPrecomputation.TransitNodeRouting<V,E> computeTransitNodeRouting()
      Computes transit node routing based on contractionHierarchy.
      Returns:
      transit node routing
    • fillContractionVerticesList

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

      Unpacks in parallel contracted paths stored in shortestPaths. Unpacked path are returned as DefaultManyToManyShortestPaths.DefaultManyToManyShortestPathsImpl.
      Parameters:
      shortestPaths - contracted many-to-many shortest paths
      Returns:
      unpacked paths
    • selectTopKTransitVertices

      private 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
    • 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)
      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