public class IncrementalSSSP extends Object implements ProgramDescription
Incremental Single Sink Shortest Paths Example. Shortest Paths are incrementally updated upon edge removal.
The program takes as input the resultant graph after a SSSP computation, an edge to be removed and the initial graph (i.e. before SSSP was computed). In the following description, SP-graph is used as an abbreviation for the graph resulted from the SSSP computation. We denote the edges that belong to this graph by SP-edges. - If the removed edge does not belong to the SP-graph then no computation is necessary and the edge is simply removed from the graph. - If the removed edge is an SP-edge, then all nodes, whose shortest path contains the removed edge, potentially require re-computation.
When the edge <u, v>
is removed, v checks if it has another out-going SP-edge.
If yes, no further computation is required.
If v has no other out-going SP-edge, it invalidates its current value, by setting it to INF.
Then, it informs all its SP-in-neighbors by sending them an INVALIDATE message.
When a vertex u receives an INVALIDATE message from v, it checks whether it has another out-going SP-edge.
If not, it invalidates its current value and propagates the INVALIDATE message.
The propagation stops when a vertex with an alternative shortest path is reached
or when we reach a vertex with no SP-in-neighbors.
Usage IncrementalSSSP <vertex path> <edge path> <edges in SSSP>
<src id edge to be removed> <trg id edge to be removed> <val edge to be removed>
<result path> <number of iterations>
If no parameters are provided, the program is run with default data from
IncrementalSSSPData
Modifier and Type | Class and Description |
---|---|
static class |
IncrementalSSSP.InvalidateMessenger
Initiate or propagate INVALIDATE messages.
|
static class |
IncrementalSSSP.VertexDistanceUpdater
When an INVALIDATE message indicates that the only shortest path
containing this vertex has been removed then set the vertex distance to
infinity.
|
Constructor and Description |
---|
IncrementalSSSP() |
Modifier and Type | Method and Description |
---|---|
String |
getDescription()
Returns a description of the plan that is generated by the assembler and
also of the arguments if they are available.
|
static boolean |
isInSSSP(Edge<Long,Double> edgeToBeRemoved,
DataSet<Edge<Long,Double>> edgesInSSSP)
Function that verifies whether the edge to be removed is part of the SSSP or not.
|
static void |
main(String[] args) |
public String getDescription()
ProgramDescription
getDescription
in interface ProgramDescription
public static boolean isInSSSP(Edge<Long,Double> edgeToBeRemoved, DataSet<Edge<Long,Double>> edgesInSSSP) throws Exception
edgeToBeRemoved
- edgesInSSSP
- Exception
Copyright © 2014–2020 The Apache Software Foundation. All rights reserved.