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/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:
-
Nested Class Summary
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.ShortestPathAlgorithm
ShortestPathAlgorithm.SingleSourcePaths<V,
E> -
Field Summary
FieldsModifier and TypeFieldDescriptionStores access vertices for each vertex in thegraph
.Contraction hierarchy which is used to compute shortest paths.private ThreadPoolExecutor
Executor which is used for parallelization in this algorithm.Locality filter which is used to determine if two vertices in the graph are local to each other or not.private ShortestPathAlgorithm
<V, E> Fallback shortest path algorithm for local queries.Many-to-many shortest paths between transit vertices.Fields inherited from class org.jgrapht.alg.shortestpath.BaseShortestPathAlgorithm
graph, GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE, GRAPH_MUST_CONTAIN_THE_SINK_VERTEX, GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX
-
Constructor Summary
ConstructorsConstructorDescriptionTransitNodeRoutingShortestPath
(TransitNodeRoutingPrecomputation.TransitNodeRouting<V, E> transitNodeRouting) Constructs a new instance of the algorithm for a giventransitNodeRouting
.TransitNodeRoutingShortestPath
(Graph<V, E> graph, ThreadPoolExecutor executor) Constructs a new instance for the givengraph
andexecutor
. -
Method Summary
Modifier and TypeMethodDescriptionprivate Pair
<TransitNodeRoutingPrecomputation.AccessVertex<V, E>, TransitNodeRoutingPrecomputation.AccessVertex<V, E>> getMinWeightAccessVertices
(V source, V sink) For verticessource
andsink
finds pair of access vertices with smallest weight over all pairs.Get a shortest path from a source vertex to a sink vertex.double
getPathWeight
(V source, V sink) Get the weight of the shortest path from a source vertex to a sink vertex.private void
initialize
(TransitNodeRoutingPrecomputation.TransitNodeRouting<V, E> transitNodeRouting) Initializes fieldscontractionHierarchy
,localityFilter
,accessVertices
,manyToManyShortestPaths
andlocalQueriesAlgorithm
.Computes a path which consists offirst
,second
andthird
paths.void
This method performs precomputation for this algorithm in the lazy fashion.Methods inherited from class org.jgrapht.alg.shortestpath.BaseShortestPathAlgorithm
createEmptyPath, getPaths
-
Field Details
-
executor
Executor which is used for parallelization in this algorithm. -
contractionHierarchy
Contraction hierarchy which is used to compute shortest paths. -
localQueriesAlgorithm
Fallback shortest path algorithm for local queries. -
manyToManyShortestPaths
Many-to-many shortest paths between transit vertices. -
accessVertices
Stores access vertices for each vertex in thegraph
. -
localityFilter
Locality filter which is used to determine if two vertices in the graph are local to each other or not.
-
-
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
-
TransitNodeRoutingShortestPath
TransitNodeRoutingShortestPath(TransitNodeRoutingPrecomputation.TransitNodeRouting<V, E> transitNodeRouting) Constructs a new instance of the algorithm for a giventransitNodeRouting
.- Parameters:
transitNodeRouting
- transit node routing forgraph
-
-
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. -
initialize
private void initialize(TransitNodeRoutingPrecomputation.TransitNodeRouting<V, E> transitNodeRouting) Initializes fieldscontractionHierarchy
,localityFilter
,accessVertices
,manyToManyShortestPaths
andlocalQueriesAlgorithm
.- Parameters:
transitNodeRouting
- transit node routing.
-
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> - Overrides:
getPathWeight
in classBaseShortestPathAlgorithm<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
-
getMinWeightAccessVertices
private Pair<TransitNodeRoutingPrecomputation.AccessVertex<V,E>, getMinWeightAccessVerticesTransitNodeRoutingPrecomputation.AccessVertex<V, E>> (V source, V sink) For verticessource
andsink
finds pair of access vertices with smallest weight over all pairs.- Parameters:
source
- source vertexsink
- 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 offirst
,second
andthird
paths.- Parameters:
first
- first part of the pathsecond
- second part of the paththird
- third part of the path- Returns:
- merged path
-