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

Class TransitNodeRoutingShortestPath<V,E>

java.lang.Object
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 Object
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.

Author:
Semen Chudakov
See Also:

  • Field Details

    • GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE

      protected static final String GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE
      Error message for reporting the existence of a negative-weight cycle.
      See Also:

    • GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX

      protected static final String GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX
      Error message for reporting that a source vertex is missing.
      See Also:

    • GRAPH_MUST_CONTAIN_THE_SINK_VERTEX

      protected static final String GRAPH_MUST_CONTAIN_THE_SINK_VERTEX
      Error message for reporting that a sink vertex is missing.
      See Also:

    • graph

      protected final Graph<V,E> graph
      The underlying graph.

  • 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

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

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

    • getPaths

      public ShortestPathAlgorithm.SingleSourcePaths<V,E> getPaths(V source)
      Compute all shortest paths starting from a single source vertex.
      Specified by:
      getPaths in interface ShortestPathAlgorithm<V,E>
      Parameters:
      source - the source vertex
      Returns:
      the shortest paths

    • createEmptyPath

      protected final GraphPath<V,E> createEmptyPath(V source, V sink)
      Create an empty path. Returns null if the source vertex is different than the target vertex.
      Parameters:
      source - the source vertex
      sink - the sink vertex
      Returns:
      an empty path or null null if the source vertex is different than the target vertex