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 typeE
- 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 onTransitNodeRoutingPrecomputation
.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 thanContractionHierarchyBidirectionalDijkstra
. 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.
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.ShortestPathAlgorithm
ShortestPathAlgorithm.SingleSourcePaths<V,E>
-
-
Field Summary
Fields Modifier and Type Field Description private TransitNodeRoutingPrecomputation.AccessVertices<V,E>
accessVertices
Stores access vertices for each vertex in thegraph
.private ContractionHierarchyPrecomputation.ContractionHierarchy<V,E>
contractionHierarchy
Contraction hierarchy which is used to compute shortest paths.private java.util.concurrent.ThreadPoolExecutor
executor
Executor which is used for parallelization in this algorithm.private TransitNodeRoutingPrecomputation.LocalityFilter<V>
localityFilter
Locality filter which is used to determine if two vertices in the graph are local to each other or not.private ShortestPathAlgorithm<V,E>
localQueriesAlgorithm
Fallback shortest path algorithm for local queries.private ManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths<V,E>
manyToManyShortestPaths
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
Constructors Constructor Description TransitNodeRoutingShortestPath(TransitNodeRoutingPrecomputation.TransitNodeRouting<V,E> transitNodeRouting)
Constructs a new instance of the algorithm for a giventransitNodeRouting
.TransitNodeRoutingShortestPath(Graph<V,E> graph, java.util.concurrent.ThreadPoolExecutor executor)
Constructs a new instance for the givengraph
andexecutor
.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private 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.GraphPath<V,E>
getPath(V source, V sink)
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
.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.void
performPrecomputation()
This method performs precomputation for this algorithm in the lazy fashion.-
Methods inherited from class org.jgrapht.alg.shortestpath.BaseShortestPathAlgorithm
createEmptyPath, getPaths
-
-
-
-
Field Detail
-
executor
private java.util.concurrent.ThreadPoolExecutor executor
Executor which is used for parallelization in this algorithm.
-
contractionHierarchy
private ContractionHierarchyPrecomputation.ContractionHierarchy<V,E> contractionHierarchy
Contraction hierarchy which is used to compute shortest paths.
-
localQueriesAlgorithm
private ShortestPathAlgorithm<V,E> localQueriesAlgorithm
Fallback shortest path algorithm for local queries.
-
manyToManyShortestPaths
private ManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths<V,E> manyToManyShortestPaths
Many-to-many shortest paths between transit vertices.
-
accessVertices
private TransitNodeRoutingPrecomputation.AccessVertices<V,E> accessVertices
Stores access vertices for each vertex in thegraph
.
-
localityFilter
private TransitNodeRoutingPrecomputation.LocalityFilter<V> localityFilter
Locality filter which is used to determine if two vertices in the graph are local to each other or not.
-
-
Constructor Detail
-
TransitNodeRoutingShortestPath
public TransitNodeRoutingShortestPath(Graph<V,E> graph, java.util.concurrent.ThreadPoolExecutor executor)
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 Detail
-
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
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 vertexsink
- 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. 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>,TransitNodeRoutingPrecomputation.AccessVertex<V,E>> getMinWeightAccessVertices(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
-
-