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

Class 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 BaseShortestPathAlgorithm<V,​E>
    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.

    See Also:
    TransitNodeRoutingPrecomputation, BidirectionalDijkstraShortestPath

    • 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

      • TransitNodeRoutingShortestPath

        TransitNodeRoutingShortestPath​(TransitNodeRoutingPrecomputation.TransitNodeRouting<V,​E> transitNodeRouting)
        Constructs a new instance of the algorithm for a given transitNodeRouting.
        Parameters:
        transitNodeRouting - transit node routing for graph

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

      • initialize

        private void initialize​(TransitNodeRoutingPrecomputation.TransitNodeRouting<V,​E> transitNodeRouting)
        Initializes fields contractionHierarchy, localityFilter, accessVertices, manyToManyShortestPaths and localQueriesAlgorithm.
        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 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>
        Overrides:
        getPathWeight in class BaseShortestPathAlgorithm<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

      • mergePaths

        private GraphPath<V,​E> mergePaths​(GraphPath<V,​E> first,
                                        GraphPath<V,​E> second,
                                        GraphPath<V,​E> third)
        Computes a path which consists of first, second and third paths.
        Parameters:
        first - first part of the path
        second - second part of the path
        third - third part of the path
        Returns:
        merged path