Class TransitNodeRoutingShortestPath<V,E>

java.lang.Object
org.jgrapht.alg.shortestpath.BaseShortestPathAlgorithm<V,E>
org.jgrapht.alg.shortestpath.TransitNodeRoutingShortestPath<V,E>
Type Parameters:
V - graph vertex type
E - graph edge type
All Implemented Interfaces:
ShortestPathAlgorithm<V,E>
public class TransitNodeRoutingShortestPath<V,E> extends BaseShortestPathAlgorithm<V,E>
Implementation of the shortest paths algorithm based on TransitNodeRoutingPrecomputation.

The algorithm is originally described the article: Arz, Julian & Luxen, Dennis & Sanders, Peter. (2013). Transit Node Routing Reconsidered. 7933. 10.1007/978-3-642-38527-8_7.

The shortest paths between vertices $u$ and $v$ is computed in the following way. First, a locality filter is used to determine if the vertices are local to each other. If so, a fallback shortest path algorithm is used to compute the path. Otherwise, there is a shortest path between the vertices which contains a transit vertex. Therefore the forward access vertices of $u$ and backward access vertices of $v$ are inspected to find a pair of such access vertices $(a_u, a_v)$ so that the value of $d(u,a_u) + d(a_u, a_v) + d(a_u, v)$ is minimum over all such pairs. Here $d(s,t)$ is the distance from vertex $s$ to vertex $t$.

The algorithm is designed to operate on sparse graphs with low average outdegree. Comparing to ContractionHierarchyBidirectionalDijkstra it uses significantly more time on the precomputation stage. Because of that it makes sense to use this algorithm on large instances (i.e. with more than 10.000 vertices), where it shows substantially better performance results than ContractionHierarchyBidirectionalDijkstra. Typically this algorithm is used as the backend for large scale shortest path search engines, e.g. OpenStreetMap.

The precomputation in this algorithm is performed in a lazy fashion. It can be performed by directly calling the #performPrecomputation() method. Otherwise, this method is called during the first call to either the #getPath() or #getPathWeight() methods.

See Also:

  • Field Details

  • Constructor Details

    • TransitNodeRoutingShortestPath

      public TransitNodeRoutingShortestPath(Graph<V,E> graph, ThreadPoolExecutor executor)
      Constructs a new instance for the given graph and executor. It is up to a user of this algorithm to handle the creation and termination of the provided executor. For utility methods to manage a ThreadPoolExecutor see ConcurrencyUtil.
      Parameters:
      graph - graph
      executor - executor which will be used for computing TransitNodeRouting

    • TransitNodeRoutingShortestPath

      TransitNodeRoutingShortestPath(TransitNodeRoutingPrecomputation.TransitNodeRouting<V,E> transitNodeRouting)
      Constructs a new instance of the algorithm for a given transitNodeRouting.
      Parameters:
      transitNodeRouting - transit node routing for graph

  • Method Details

    • performPrecomputation

      public void performPrecomputation()
      This method performs precomputation for this algorithm in the lazy fashion. The result of the precomputation stage is the TransitNodeRouting object which contains #contractionHierarchy, #localityFilter, #accessVertices and #manyToManyShortestPaths objects for this algorithm. If not called directly this method will be invoked in either of getPath() or getPathWeight() methods.

    • initialize

      private void initialize(TransitNodeRoutingPrecomputation.TransitNodeRouting<V,E> transitNodeRouting)
      Initializes fields contractionHierarchy, localityFilter, accessVertices, manyToManyShortestPaths and localQueriesAlgorithm.
      Parameters:
      transitNodeRouting - transit node routing.

    • getPath

      public GraphPath<V,E> getPath(V source, V sink)
      Get a shortest path from a source vertex to a sink vertex.
      Parameters:
      source - the source vertex
      sink - the target vertex
      Returns:
      a shortest path or null if no path exists

    • getPathWeight

      public double getPathWeight(V source, V sink)
      Get the weight of the shortest path from a source vertex to a sink vertex. Returns Double.POSITIVE_INFINITY if no path exists.
      Specified by:
      getPathWeight in interface ShortestPathAlgorithm<V,E>
      Overrides:
      getPathWeight in class BaseShortestPathAlgorithm<V,E>
      Parameters:
      source - the source vertex
      sink - the sink vertex
      Returns:
      the weight of the shortest path from a source vertex to a sink vertex, or Double.POSITIVE_INFINITY if no path exists

    • getMinWeightAccessVertices

      private Pair<TransitNodeRoutingPrecomputation.AccessVertex<V,E>, TransitNodeRoutingPrecomputation.AccessVertex<V,E>> getMinWeightAccessVertices(V source, V sink)
      For vertices source and sink finds pair of access vertices with smallest weight over all pairs.
      Parameters:
      source - source vertex
      sink - sink vertex
      Returns:
      pair of access vertices with shortest path between them

    • mergePaths

      private GraphPath<V,E> mergePaths(GraphPath<V,E> first, GraphPath<V,E> second, GraphPath<V,E> third)
      Computes a path which consists of first, second and third paths.
      Parameters:
      first - first part of the path
      second - second part of the path
      third - third part of the path
      Returns:
      merged path