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

Class DeltaSteppingShortestPath<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    ShortestPathAlgorithm<V,​E>
    public class DeltaSteppingShortestPath<V,​E>
extends BaseShortestPathAlgorithm<V,​E>
    Parallel implementation of a single-source shortest path algorithm: the delta-stepping algorithm. The algorithm computes single source shortest paths in a graphs with non-negative edge weights. When using multiple threads, this implementation typically outperforms DijkstraShortestPath and BellmanFordShortestPath.

    The delta-stepping algorithm is described in the paper: U. Meyer, P. Sanders, $\Delta$-stepping: a parallelizable shortest path algorithm, Journal of Algorithms, Volume 49, Issue 1, 2003, Pages 114-152, ISSN 0196-6774.

    The $\Delta$-stepping algorithm takes as input a weighted graph $G(V,E)$, a source node $s$ and a parameter $\Delta > 0$. Let $tent[v]$ be the best known shortest distance from $s$ to vertex $v\in V$. At the start of the algorithm, $tent[s]=0$, $tent[v]=\infty$ for $v\in V\setminus \{s\}$. The algorithm partitions vertices in a series of buckets $B=(B_0, B_1, B_2, \dots)$, where a vertex $v\in V$ is placed in bucket $B_{\lfloor\frac{tent[v]}{\Delta}\rfloor}$. During the execution of the algorithm, vertices in bucket $B_i$, for $i=0,1,2,\dots$, are removed one-by-one. For each removed vertex $v$, and for all its outgoing edges $(v,w)$, the algorithm checks whether $tent[v]+c(v,w) < tent[w]$. If so, $w$ is removed from its current bucket, $tent[w]$ is updated ($tent[w]=tent[v]+c(v,w)$), and $w$ is placed into bucket $B_{\lfloor\frac{tent[w]}{\Delta}\rfloor}$. Parallelism is achieved by processing all vertices belonging to the same bucket concurrently. The algorithm terminates when all buckets are empty. At this stage the array $tent$ contains the minimal cost from $s$ to every vertex $v \in V$. For a more detailed description of the algorithm, refer to the aforementioned paper.

    For a given graph $G(V,E)$ and parameter $\Delta$, let a $\Delta$-path be a path of total weight at most $\Delta$ with no repeated edges. The time complexity of the algorithm is $O(\frac{(|V| + |E| + n_{\Delta} + m_{\Delta})}{p} + \frac{L}{\Delta}\cdot d\cdot l_{\Delta}\cdot \log n)$, where

    • $n_{\Delta}$ - number of vertex pairs $(u,v)$, where $u$ and $v$ are connected by some $\Delta$-path.
    • $m_{\Delta}$ - number of vertex triples $(u,v^{\prime},v)$, where $u$ and $v^{\prime}$ are connected by some $\Delta$-path and edge $(v^{\prime},v)$ has weight at most $\Delta$.
    • $L$ - maximum weight of a shortest path from selected source to any sink.
    • $d$ - maximum vertex degree.
    • $l_{\Delta}$ - maximum number of edges in a $\Delta$-path $+1$.

    For parallelization, this implementation relies on the ThreadPoolExecutor which is supplied to this algorithm from outside.

    Since:
    January 2018

    • Field Detail

      • NEGATIVE_EDGE_WEIGHT_NOT_ALLOWED

        private static final java.lang.String NEGATIVE_EDGE_WEIGHT_NOT_ALLOWED
        Error message for reporting the existence of an edge with negative weight.
        See Also:
        Constant Field Values

      • DELTA_MUST_BE_NON_NEGATIVE

        private static final java.lang.String DELTA_MUST_BE_NON_NEGATIVE
        Error message for reporting that delta must be positive.
        See Also:
        Constant Field Values

      • DEFAULT_PARALLELISM

        private static final int DEFAULT_PARALLELISM
        Default value for parallelism.

      • TASKS_TO_THREADS_RATIO

        private static final int TASKS_TO_THREADS_RATIO
        Empirically computed amount of tasks per worker thread in the ForkJoinPool that yields good performance.
        See Also:
        Constant Field Values

      • delta

        private double delta
        The bucket width. A bucket with index $i$ therefore stores a vertex v if and only if v is queued and tentative distance to v $\in[i\cdot\Delta,(i+1)\cdot\Delta]$

      • parallelism

        private int parallelism
        Maximum number of threads used in the computations.

      • numOfBuckets

        private int numOfBuckets
        Number of buckets in the bucket structure.

      • distanceAndPredecessorMap

        private java.util.Map<V,​Pair<java.lang.Double,​E>> distanceAndPredecessorMap
        Map to store predecessor for each vertex in the shortest path tree.

      • bucketStructure

        private java.util.List<java.util.Set<V>> bucketStructure
        Buckets structure.

      • vertexComparator

        private java.util.Comparator<V> vertexComparator
        Comparator for vertices in the graph which is used to create ConcurrentSkipListSet instances for the bucketStructure.

      • bucketsSupplier

        private java.util.function.Supplier<java.util.Set<V>> bucketsSupplier
        Supplier of the buckets for the bucketStructure.

      • completionService

        private java.util.concurrent.ExecutorCompletionService<java.lang.Void> completionService
        Decorator for ThreadPoolExecutor supplied to this algorithm that enables to keep track of when all submitted tasks are finished.

      • verticesQueue

        private java.util.Queue<V> verticesQueue
        Queue of vertices which edges should be relaxed on current iteration.

      • lightRelaxTask

        private java.lang.Runnable lightRelaxTask
        Task for light edges relaxation.

      • heavyRelaxTask

        private java.lang.Runnable heavyRelaxTask
        Task for light edges relaxation.

      • allVerticesAdded

        private volatile boolean allVerticesAdded
        Indicates when all the vertices are been added to the verticesQueue on each iteration.

    • Constructor Detail

      • DeltaSteppingShortestPath

        public DeltaSteppingShortestPath​(Graph<V,​E> graph,
                                 java.util.concurrent.ThreadPoolExecutor executor)
        Constructs a new instance of the algorithm for a 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 parallelization

      • DeltaSteppingShortestPath

        public DeltaSteppingShortestPath​(Graph<V,​E> graph,
                                 java.util.concurrent.ThreadPoolExecutor executor,
                                 java.util.Comparator<V> vertexComparator)
        Constructs a new instance of the algorithm for a given graph, executor and vertexComparator. 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. vertexComparator provided via this constructor is used to create instances of ConcurrentSkipListSet for the individual buckets. This gives a gives a small performance benefit for shortest paths computation.
        Parameters:
        graph - graph
        executor - executor which will be used for parallelization
        vertexComparator - comparator for vertices of the graph

      • DeltaSteppingShortestPath

        public DeltaSteppingShortestPath​(Graph<V,​E> graph,
                                 double delta,
                                 java.util.concurrent.ThreadPoolExecutor executor)
        Constructs a new instance of the algorithm for a given graph, delta 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 - the graph
        delta - bucket width
        executor - executor which will be used for parallelization

      • DeltaSteppingShortestPath

        public DeltaSteppingShortestPath​(Graph<V,​E> graph,
                                 double delta,
                                 java.util.concurrent.ThreadPoolExecutor executor,
                                 java.util.Comparator<V> vertexComparator)
        Constructs a new instance of the algorithm for a given graph, delta, executor and vertexComparator. 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. vertexComparator provided via this constructor is used to create instances of ConcurrentSkipListSet for the individual buckets. This gives a gives a small performance benefit for shortest paths computation.
        Parameters:
        graph - the graph
        delta - bucket width
        executor - executor which will be used for parallelization
        vertexComparator - comparator for vertices of the graph

      • DeltaSteppingShortestPath

        @Deprecated
public DeltaSteppingShortestPath​(Graph<V,​E> graph,
                                 int parallelism)
        Deprecated.
        replaced with DeltaSteppingShortestPath(Graph, ThreadPoolExecutor)
        Constructs a new instance of the algorithm for a given graph, parallelism.
        Parameters:
        graph - the graph
        parallelism - maximum number of threads used in the computations

      • DeltaSteppingShortestPath

        @Deprecated
public DeltaSteppingShortestPath​(Graph<V,​E> graph,
                                 double delta,
                                 int parallelism)
        Deprecated.
        replaced with DeltaSteppingShortestPath(Graph, double, ThreadPoolExecutor)
        Constructs a new instance of the algorithm for a given graph, delta, parallelism. If delta is $0.0$ it will be computed during the algorithm execution. In general if the value of $\frac{maximum edge weight}{maximum outdegree}$ is known beforehand, it is preferable to specify it via this constructor, because processing the whole graph to compute this value may significantly slow down the algorithm.
        Parameters:
        graph - the graph
        delta - bucket width
        parallelism - maximum number of threads used in the computations

    • Method Detail

      • init

        private void init​(Graph<V,​E> graph,
                  double delta,
                  java.util.concurrent.ThreadPoolExecutor executor,
                  java.util.Comparator<V> vertexComparator)
        Initializes delta, parallelism, distanceAndPredecessorMap, completionService, verticesQueue, lightRelaxTask and heavyRelaxTask fields.
        Parameters:
        graph - a graph
        delta - bucket width
        executor - executor which will be used for parallelization

      • 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

      • getBucketsSupplier

        private java.util.function.Supplier<java.util.Set<V>> getBucketsSupplier​(V vertex)
        Creates a supplier of sets for the bucketStructure.
        Parameters:
        vertex - a vertex in the graph
        Returns:
        supplier of buckets

      • computeShortestPaths

        private void computeShortestPaths​(V source)
        Performs shortest path computations.
        Parameters:
        source - the source vertex

      • findAndRelaxLightRequests

        private void findAndRelaxLightRequests​(java.util.Set<V> vertices)
        Manages edge relaxations. Adds all elements from vertices to the verticesQueue and submits as many lightRelaxTask to the completionService as needed.
        Parameters:
        vertices - vertices

      • findAndRelaxHeavyRequests

        private void findAndRelaxHeavyRequests​(java.util.List<java.util.Set<V>> verticesSets)
        Manages execution of edges relaxation. Adds all elements from vertices to the verticesQueue and submits as many heavyRelaxTask to the completionService as needed.
        Parameters:
        verticesSets - set of sets of vertices

      • addSetVertices

        private void addSetVertices​(java.util.Iterator<V> iterator,
                            int numOfVertices)
        Adds numOfVertices vertices to the verticesQueue provided by the iterator.
        Parameters:
        iterator - vertices iterator
        numOfVertices - vertices amount

      • addSetRemaining

        private void addSetRemaining​(java.util.Iterator<V> iterator)
        Adds all remaining vertices to the verticesQueue provided by the iterator.
        Parameters:
        iterator - vertices iterator

      • addSetsVertices

        private java.util.Iterator<V> addSetsVertices​(java.util.Iterator<java.util.Set<V>> setIterator,
                                              int numOfVertices)
        Adds numOfVertices vertices to the verticesQueue that are contained in the sets provided by the setIterator. Returns iterator of the set which vertex was added last.
        Parameters:
        setIterator - sets of vertices iterator
        numOfVertices - vertices amount
        Returns:
        iterator of the last set

      • addSetsRemaining

        private void addSetsRemaining​(java.util.Iterator<java.util.Set<V>> setIterator)
        Adds all remaining vertices to the verticesQueue that are contained in the sets provided by the setIterator.
        Parameters:
        setIterator - sets of vertices iterator

      • submitTasks

        private void submitTasks​(java.lang.Runnable task,
                         int numOfTasks)
        Submits the task numOfTasks times to the completionService.
        Parameters:
        task - task to be submitted
        numOfTasks - amount of times task should be submitted

      • waitForTasksCompletion

        private void waitForTasksCompletion​(int numOfTasks)
        Takes numOfTasks tasks from the completionService.
        Parameters:
        numOfTasks - amount of tasks

      • relax

        private void relax​(V v,
                   E e,
                   double distance)
        Performs relaxation in parallel-safe fashion. Synchronises by vertex, then if new tentative distance is less then removes v from the old bucket, adds is to the new bucket and updates distanceAndPredecessorMap value for v.
        Parameters:
        v - vertex
        e - edge to predecessor
        distance - distance

      • bucketIndex

        private int bucketIndex​(double distance)
        Calculates bucket index for a given distance.
        Parameters:
        distance - distance
        Returns:
        bucket index

      • getContentAndReplace

        private java.util.Set<V> getContentAndReplace​(int bucketIndex)
        Replaces the bucket at the bucketIndex with a new instance of the concurrent set. Return the reference to the set that was previously in the bucket.
        Parameters:
        bucketIndex - bucket index
        Returns:
        content of the bucket