Class TransitNodeRoutingShortestPath<V,E>
 Type Parameters:
V
 graph vertex typeE
 graph edge type
 All Implemented Interfaces:
ShortestPathAlgorithm<V,
E>
TransitNodeRoutingPrecomputation
.
The algorithm is originally described the article: Arz, Julian & Luxen, Dennis & Sanders, Peter. (2013). Transit Node Routing Reconsidered. 7933. 10.1007/9783642385278_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:

TransitNodeRoutingPrecomputation
BidirectionalDijkstraShortestPath

Nested Class Summary
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.ShortestPathAlgorithm
ShortestPathAlgorithm.SingleSourcePaths<V,
E> 
Field Summary
Modifier and TypeFieldDescriptionThe underlying graph.protected static final String
Error message for reporting the existence of a negativeweight cycle.protected static final String
Error message for reporting that a sink vertex is missing.protected static final String
Error message for reporting that a source vertex is missing. 
Constructor Summary
ConstructorDescriptionTransitNodeRoutingShortestPath
(Graph<V, E> graph, ThreadPoolExecutor executor) Constructs a new instance for the givengraph
andexecutor
. 
Method Summary
Modifier and TypeMethodDescriptioncreateEmptyPath
(V source, V sink) Create an empty path.Get a shortest path from a source vertex to a sink vertex.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
This method performs precomputation for this algorithm in the lazy fashion.

Field Details

GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE
Error message for reporting the existence of a negativeweight cycle. See Also:

GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX
Error message for reporting that a source vertex is missing. See Also:

GRAPH_MUST_CONTAIN_THE_SINK_VERTEX
Error message for reporting that a sink vertex is missing. See Also:

graph
The underlying graph.


Constructor Details

TransitNodeRoutingShortestPath
Constructs a new instance for the givengraph
andexecutor
. It is up to a user of this algorithm to handle the creation and termination of the providedexecutor
. For utility methods to manage aThreadPoolExecutor
seeConcurrencyUtil
. Parameters:
graph
 graphexecutor
 executor which will be used for computingTransitNodeRouting


Method Details

performPrecomputation
public void performPrecomputation()This method performs precomputation for this algorithm in the lazy fashion. The result of the precomputation stage is theTransitNodeRouting
object which contains#contractionHierarchy
,#localityFilter
,#accessVertices
and#manyToManyShortestPaths
objects for this algorithm. If not called directly this method will be invoked in either ofgetPath()
orgetPathWeight()
methods. 
getPath
Get a shortest path from a source vertex to a sink vertex. Parameters:
source
 the source vertexsink
 the target vertex Returns:
 a shortest path or null if no path exists

getPathWeight
Get the weight of the shortest path from a source vertex to a sink vertex. ReturnsDouble.POSITIVE_INFINITY
if no path exists. Specified by:
getPathWeight
in interfaceShortestPathAlgorithm<V,
E>  Parameters:
source
 the source vertexsink
 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
Compute all shortest paths starting from a single source vertex. Specified by:
getPaths
in interfaceShortestPathAlgorithm<V,
E>  Parameters:
source
 the source vertex Returns:
 the shortest paths

createEmptyPath
Create an empty path. Returns null if the source vertex is different than the target vertex. Parameters:
source
 the source vertexsink
 the sink vertex Returns:
 an empty path or null null if the source vertex is different than the target vertex
