public class IncrementalSSSP extends Object implements ProgramDescription
<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>
IncrementalSSSPData
Modifier and Type | Class and Description |
---|---|
static class |
IncrementalSSSP.InvalidateMessenger |
static class |
IncrementalSSSP.VertexDistanceUpdater |
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–2017 The Apache Software Foundation. All rights reserved.