Class DeltaSteppingShortestPath<V,E>

java.lang.Object
org.jgrapht.alg.shortestpath.BaseShortestPathAlgorithm<V,E>
org.jgrapht.alg.shortestpath.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 Details

    • NEGATIVE_EDGE_WEIGHT_NOT_ALLOWED

      private static final String NEGATIVE_EDGE_WEIGHT_NOT_ALLOWED
      Error message for reporting the existence of an edge with negative weight.
      See Also:
    • DELTA_MUST_BE_NON_NEGATIVE

      private static final String DELTA_MUST_BE_NON_NEGATIVE
      Error message for reporting that delta must be positive.
      See Also:
    • 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:
    • 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.
    • maxEdgeWeight

      private double maxEdgeWeight
      Maximum edge weight in the BaseShortestPathAlgorithm.graph.
    • distanceAndPredecessorMap

      private Map<V,Pair<Double,E>> distanceAndPredecessorMap
      Map to store predecessor for each vertex in the shortest path tree.
    • bucketStructure

      private List<Set<V>> bucketStructure
      Buckets structure.
    • vertexComparator

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

      private Supplier<Set<V>> bucketsSupplier
      Supplier of the buckets for the bucketStructure.
    • completionService

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

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

      private Runnable lightRelaxTask
      Task for light edges relaxation.
    • heavyRelaxTask

      private 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 Details

    • DeltaSteppingShortestPath

      public DeltaSteppingShortestPath(Graph<V,E> graph, 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, ThreadPoolExecutor executor, 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

      @Deprecated public DeltaSteppingShortestPath(Graph<V,E> graph, double delta)
      Constructs a new instance of the algorithm for a given graph, delta.
      Parameters:
      graph - the graph
      delta - bucket width
    • DeltaSteppingShortestPath

      public DeltaSteppingShortestPath(Graph<V,E> graph, double delta, 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, ThreadPoolExecutor executor, 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)
      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)
      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 Details

    • init

      private void init(Graph<V,E> graph, double delta, ThreadPoolExecutor executor, 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
    • getMaxEdgeWeight

      private double getMaxEdgeWeight()
      Calculates max edge weight in the BaseShortestPathAlgorithm.graph.
      Returns:
      max edge weight
    • 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
    • getPaths

      public ShortestPathAlgorithm.SingleSourcePaths<V,E> getPaths(V source)
      Compute all shortest paths starting from a single source vertex.
      Specified by:
      getPaths in interface ShortestPathAlgorithm<V,E>
      Overrides:
      getPaths in class BaseShortestPathAlgorithm<V,E>
      Parameters:
      source - the source vertex
      Returns:
      the shortest paths
    • getBucketsSupplier

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

      private double findDelta()
      Calculates value of delta. The value is calculated as the maximal edge weight divided by maximal out-degree in the BaseShortestPathAlgorithm.graph or $1.0$ if edge set of the BaseShortestPathAlgorithm.graph is empty.
      Returns:
      bucket width
    • fillDistanceAndPredecessorMap

      private void fillDistanceAndPredecessorMap()
      Fills distanceAndPredecessorMap concurrently.
    • computeShortestPaths

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

      private void findAndRelaxLightRequests(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(List<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(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(Iterator<V> iterator)
      Adds all remaining vertices to the verticesQueue provided by the iterator.
      Parameters:
      iterator - vertices iterator
    • addSetsVertices

      private Iterator<V> addSetsVertices(Iterator<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(Iterator<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(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 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