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, SPgraph is used as an abbreviation for the graph resulted from the SSSP computation. We denote the edges that belong to this graph by SPedges.  If the removed edge does not belong to the SPgraph then no computation is necessary and the edge is simply removed from the graph.  If the removed edge is an SPedge, then all nodes, whose shortest path contains the removed edge, potentially require recomputation.
When the edge <u, v>
is removed, v checks if it has another outgoing
SPedge. If yes, no further computation is required. If v has no other outgoing SPedge, it
invalidates its current value, by setting it to INF. Then, it informs all its SPinneighbors by
sending them an INVALIDATE message. When a vertex u receives an INVALIDATE message from v, it
checks whether it has another outgoing SPedge. 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 SPinneighbors.
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–2023 The Apache Software Foundation. All rights reserved.