- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
ShortestPathAlgorithm<V,
E>
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
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescription(package private) class
Task that is submitted to thecompletionService
during shortest path computation for heavy relax requests relaxation.(package private) class
Task that is submitted to thecompletionService
during shortest path computation for light relax requests relaxation.(package private) class
Is used during the algorithm to compute maximum edge weight of theBaseShortestPathAlgorithm.graph
.Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.ShortestPathAlgorithm
ShortestPathAlgorithm.SingleSourcePaths<V,
E> -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate boolean
Indicates when all the vertices are been added to theverticesQueue
on each iteration.Supplier of the buckets for thebucketStructure
.Buckets structure.private ExecutorCompletionService
<Void> Decorator forThreadPoolExecutor
supplied to this algorithm that enables to keep track of when all submitted tasks are finished.private static final int
Default value forparallelism
.private double
The bucket width.private static final String
Error message for reporting that delta must be positive.Map to store predecessor for each vertex in the shortest path tree.private Runnable
Task for light edges relaxation.private Runnable
Task for light edges relaxation.private double
Maximum edge weight in theBaseShortestPathAlgorithm.graph
.private static final String
Error message for reporting the existence of an edge with negative weight.private int
Number of buckets in the bucket structure.private int
Maximum number of threads used in the computations.private static final int
Empirically computed amount of tasks per worker thread in theForkJoinPool
that yields good performance.private Comparator
<V> Comparator for vertices in the graph which is used to createConcurrentSkipListSet
instances for thebucketStructure
.Queue of vertices which edges should be relaxed on current iteration.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
ConstructorsConstructorDescriptionDeltaSteppingShortestPath
(Graph<V, E> graph, double delta) Deprecated.DeltaSteppingShortestPath
(Graph<V, E> graph, double delta, int parallelism) Deprecated.DeltaSteppingShortestPath
(Graph<V, E> graph, double delta, ThreadPoolExecutor executor) Constructs a new instance of the algorithm for a given graph, delta andexecutor
.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
andvertexComparator
.DeltaSteppingShortestPath
(Graph<V, E> graph, int parallelism) Deprecated.replaced withDeltaSteppingShortestPath(Graph, ThreadPoolExecutor)
DeltaSteppingShortestPath
(Graph<V, E> graph, ThreadPoolExecutor executor) Constructs a new instance of the algorithm for a given graph andexecutor
.DeltaSteppingShortestPath
(Graph<V, E> graph, ThreadPoolExecutor executor, Comparator<V> vertexComparator) Constructs a new instance of the algorithm for a givengraph
,executor
andvertexComparator
. -
Method Summary
Modifier and TypeMethodDescriptionprivate void
addSetRemaining
(Iterator<V> iterator) Adds all remaining vertices to theverticesQueue
provided by theiterator
.private void
addSetsRemaining
(Iterator<Set<V>> setIterator) Adds all remaining vertices to theverticesQueue
that are contained in the sets provided by thesetIterator
.addSetsVertices
(Iterator<Set<V>> setIterator, int numOfVertices) AddsnumOfVertices
vertices to theverticesQueue
that are contained in the sets provided by thesetIterator
.private void
addSetVertices
(Iterator<V> iterator, int numOfVertices) private int
bucketIndex
(double distance) Calculates bucket index for a givendistance
.private void
computeShortestPaths
(V source) Performs shortest path computations.private void
FillsdistanceAndPredecessorMap
concurrently.private void
findAndRelaxHeavyRequests
(List<Set<V>> verticesSets) Manages execution of edges relaxation.private void
findAndRelaxLightRequests
(Set<V> vertices) Manages edge relaxations.private double
Calculates value ofdelta
.getBucketsSupplier
(V vertex) Creates a supplier of sets for thebucketStructure
.getContentAndReplace
(int bucketIndex) Replaces the bucket at thebucketIndex
with a new instance of the concurrent set.private double
Calculates max edge weight in theBaseShortestPathAlgorithm.graph
.Get a shortest path from a source vertex to a sink vertex.Compute all shortest paths starting from a single source vertex.private void
init
(Graph<V, E> graph, double delta, ThreadPoolExecutor executor, Comparator<V> vertexComparator) Initializesdelta
,parallelism
,distanceAndPredecessorMap
,completionService
,verticesQueue
,lightRelaxTask
andheavyRelaxTask
fields.private void
Performs relaxation in parallel-safe fashion.private void
submitTasks
(Runnable task, int numOfTasks) private void
waitForTasksCompletion
(int numOfTasks) TakesnumOfTasks
tasks from thecompletionService
.Methods inherited from class org.jgrapht.alg.shortestpath.BaseShortestPathAlgorithm
createEmptyPath, getPathWeight
-
Field Details
-
NEGATIVE_EDGE_WEIGHT_NOT_ALLOWED
Error message for reporting the existence of an edge with negative weight.- See Also:
-
DELTA_MUST_BE_NON_NEGATIVE
Error message for reporting that delta must be positive.- See Also:
-
DEFAULT_PARALLELISM
private static final int DEFAULT_PARALLELISMDefault value forparallelism
. -
TASKS_TO_THREADS_RATIO
private static final int TASKS_TO_THREADS_RATIOEmpirically computed amount of tasks per worker thread in theForkJoinPool
that yields good performance.- See Also:
-
delta
private double deltaThe 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 parallelismMaximum number of threads used in the computations. -
numOfBuckets
private int numOfBucketsNumber of buckets in the bucket structure. -
maxEdgeWeight
private double maxEdgeWeightMaximum edge weight in theBaseShortestPathAlgorithm.graph
. -
distanceAndPredecessorMap
Map to store predecessor for each vertex in the shortest path tree. -
bucketStructure
Buckets structure. -
vertexComparator
Comparator for vertices in the graph which is used to createConcurrentSkipListSet
instances for thebucketStructure
. -
bucketsSupplier
Supplier of the buckets for thebucketStructure
. -
completionService
Decorator forThreadPoolExecutor
supplied to this algorithm that enables to keep track of when all submitted tasks are finished. -
verticesQueue
Queue of vertices which edges should be relaxed on current iteration. -
lightRelaxTask
Task for light edges relaxation. -
heavyRelaxTask
Task for light edges relaxation. -
allVerticesAdded
private volatile boolean allVerticesAddedIndicates when all the vertices are been added to theverticesQueue
on each iteration.
-
-
Constructor Details
-
DeltaSteppingShortestPath
Constructs a new instance of the algorithm for a given graph 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 parallelization
-
DeltaSteppingShortestPath
public DeltaSteppingShortestPath(Graph<V, E> graph, ThreadPoolExecutor executor, Comparator<V> vertexComparator) Constructs a new instance of the algorithm for a givengraph
,executor
andvertexComparator
. 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
.vertexComparator
provided via this constructor is used to create instances ofConcurrentSkipListSet
for the individual buckets. This gives a gives a small performance benefit for shortest paths computation.- Parameters:
graph
- graphexecutor
- executor which will be used for parallelizationvertexComparator
- comparator for vertices of thegraph
-
DeltaSteppingShortestPath
Deprecated.Constructs a new instance of the algorithm for a given graph, delta.- Parameters:
graph
- the graphdelta
- bucket width
-
DeltaSteppingShortestPath
Constructs a new instance of the algorithm for a given graph, delta 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
- the graphdelta
- bucket widthexecutor
- 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
andvertexComparator
. 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
.vertexComparator
provided via this constructor is used to create instances ofConcurrentSkipListSet
for the individual buckets. This gives a gives a small performance benefit for shortest paths computation.- Parameters:
graph
- the graphdelta
- bucket widthexecutor
- executor which will be used for parallelizationvertexComparator
- comparator for vertices of thegraph
-
DeltaSteppingShortestPath
Deprecated.replaced withDeltaSteppingShortestPath(Graph, ThreadPoolExecutor)
Constructs a new instance of the algorithm for a given graph, parallelism.- Parameters:
graph
- the graphparallelism
- maximum number of threads used in the computations
-
DeltaSteppingShortestPath
Deprecated.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 graphdelta
- bucket widthparallelism
- 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) Initializesdelta
,parallelism
,distanceAndPredecessorMap
,completionService
,verticesQueue
,lightRelaxTask
andheavyRelaxTask
fields.- Parameters:
graph
- a graphdelta
- bucket widthexecutor
- executor which will be used for parallelization
-
getMaxEdgeWeight
private double getMaxEdgeWeight()Calculates max edge weight in theBaseShortestPathAlgorithm.graph
.- Returns:
- max edge weight
-
getPath
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
-
getPaths
Compute all shortest paths starting from a single source vertex.- Specified by:
getPaths
in interfaceShortestPathAlgorithm<V,
E> - Overrides:
getPaths
in classBaseShortestPathAlgorithm<V,
E> - Parameters:
source
- the source vertex- Returns:
- the shortest paths
-
getBucketsSupplier
Creates a supplier of sets for thebucketStructure
.- Parameters:
vertex
- a vertex in the graph- Returns:
- supplier of buckets
-
findDelta
private double findDelta()Calculates value ofdelta
. The value is calculated as the maximal edge weight divided by maximal out-degree in theBaseShortestPathAlgorithm.graph
or $1.0$ if edge set of theBaseShortestPathAlgorithm.graph
is empty.- Returns:
- bucket width
-
fillDistanceAndPredecessorMap
private void fillDistanceAndPredecessorMap()FillsdistanceAndPredecessorMap
concurrently. -
computeShortestPaths
Performs shortest path computations.- Parameters:
source
- the source vertex
-
findAndRelaxLightRequests
Manages edge relaxations. Adds all elements fromvertices
to theverticesQueue
and submits as manylightRelaxTask
to thecompletionService
as needed.- Parameters:
vertices
- vertices
-
findAndRelaxHeavyRequests
Manages execution of edges relaxation. Adds all elements fromvertices
to theverticesQueue
and submits as manyheavyRelaxTask
to thecompletionService
as needed.- Parameters:
verticesSets
- set of sets of vertices
-
addSetVertices
- Parameters:
iterator
- vertices iteratornumOfVertices
- vertices amount
-
addSetRemaining
Adds all remaining vertices to theverticesQueue
provided by theiterator
.- Parameters:
iterator
- vertices iterator
-
addSetsVertices
AddsnumOfVertices
vertices to theverticesQueue
that are contained in the sets provided by thesetIterator
. Returns iterator of the set which vertex was added last.- Parameters:
setIterator
- sets of vertices iteratornumOfVertices
- vertices amount- Returns:
- iterator of the last set
-
addSetsRemaining
Adds all remaining vertices to theverticesQueue
that are contained in the sets provided by thesetIterator
.- Parameters:
setIterator
- sets of vertices iterator
-
submitTasks
- Parameters:
task
- task to be submittednumOfTasks
- amount of times task should be submitted
-
waitForTasksCompletion
private void waitForTasksCompletion(int numOfTasks) TakesnumOfTasks
tasks from thecompletionService
.- Parameters:
numOfTasks
- amount of tasks
-
relax
Performs relaxation in parallel-safe fashion. Synchronises byvertex
, then if new tentative distance is less then removesv
from the old bucket, adds is to the new bucket and updatesdistanceAndPredecessorMap
value forv
.- Parameters:
v
- vertexe
- edge to predecessordistance
- distance
-
bucketIndex
private int bucketIndex(double distance) Calculates bucket index for a givendistance
.- Parameters:
distance
- distance- Returns:
- bucket index
-
getContentAndReplace
Replaces the bucket at thebucketIndex
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
-
DeltaSteppingShortestPath(Graph, double, ThreadPoolExecutor)