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 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
    See Also:
    TransitNodeRoutingPrecomputation, BidirectionalDijkstraShortestPath

    • Field Detail

      • GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE

        protected static final String GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE
        Error message for reporting the existence of a negative-weight cycle.
        See Also:
        Constant Field Values

      • GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX

        protected static final String GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX
        Error message for reporting that a source vertex is missing.
        See Also:
        Constant Field Values

      • GRAPH_MUST_CONTAIN_THE_SINK_VERTEX

        protected static final String GRAPH_MUST_CONTAIN_THE_SINK_VERTEX
        Error message for reporting that a sink vertex is missing.
        See Also:
        Constant Field Values

      • graph

        protected final Graph<V,​E> graph
        The underlying graph.

    • Constructor Detail

      • TransitNodeRoutingShortestPath

        public TransitNodeRoutingShortestPath​(Graph<V,​E> graph,
                                      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

      • 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