## 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 java.lang.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
TransitNodeRoutingPrecomputation, BidirectionalDijkstraShortestPath

• ### Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.ShortestPathAlgorithm

ShortestPathAlgorithm.SingleSourcePaths<V,​E>
• ### Field Summary

Fields
Modifier and Type Field Description
protected Graph<V,​E> graph
The underlying graph.
protected static java.lang.String GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE
Error message for reporting the existence of a negative-weight cycle.
protected static java.lang.String GRAPH_MUST_CONTAIN_THE_SINK_VERTEX
Error message for reporting that a sink vertex is missing.
protected static java.lang.String GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX
Error message for reporting that a source vertex is missing.
• ### Constructor Summary

Constructors
Constructor Description
TransitNodeRoutingShortestPath​(Graph<V,​E> graph, java.util.concurrent.ThreadPoolExecutor executor)
Constructs a new instance for the given graph and executor.
• ### Method Summary

All Methods
Modifier and Type Method Description
protected GraphPath<V,​E> createEmptyPath​(V source, V sink)
Create an empty path.
GraphPath<V,​E> getPath​(V source, V sink)
Get a shortest path from a source vertex to a sink vertex.
ShortestPathAlgorithm.SingleSourcePaths<V,​E> getPaths​(V source)
Compute all shortest paths starting from a single source vertex.
double getPathWeight​(V source, V sink)
Get the weight of the shortest path from a source vertex to a sink vertex.
void performPrecomputation()
This method performs precomputation for this algorithm in the lazy fashion.
• ### Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• ### Field Detail

• #### GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE

protected static final java.lang.String GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE
Error message for reporting the existence of a negative-weight cycle.
Constant Field Values
• #### GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX

protected static final java.lang.String GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX
Error message for reporting that a source vertex is missing.
Constant Field Values
• #### GRAPH_MUST_CONTAIN_THE_SINK_VERTEX

protected static final java.lang.String GRAPH_MUST_CONTAIN_THE_SINK_VERTEX
Error message for reporting that a sink vertex is missing.
Constant Field Values
• #### graph

protected final Graph<V,​E> graph
The underlying graph.
• ### Constructor Detail

• #### TransitNodeRoutingShortestPath

public TransitNodeRoutingShortestPath​(Graph<V,​E> graph,
java.util.concurrent.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 Detail

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