All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
DynSSSP.h
Go to the documentation of this file.
1 /*
2  * DynSSSP.h
3  *
4  * Created on: 17.07.2014
5  * Author: cls, ebergamini
6  */
7 
8 #ifndef DYNSSSP_H_
9 #define DYNSSSP_H_
10 
11 #include <set>
12 
13 #include "../graph/Graph.h"
14 #include "../dynamics/GraphEvent.h"
15 #include "../base/DynAlgorithm.h"
16 #include "SSSP.h"
17 
18 namespace NetworKit {
19 
24 class DynSSSP: public SSSP, public DynAlgorithm {
25 
26 friend class DynApproxBetweenness;
27 
28 public:
37  DynSSSP(const Graph& G, node source, bool storePredecessors = true, node target = none);
38 
39  virtual ~DynSSSP() = default;
40 
47  bool modified();
55  void setTargetNode(const node t = 0);
56 
62  std::vector<node> getPredecessors(node t) const;
63 
64 protected:
65  bool storePreds = true;
66  bool mod = false;
68 };
69 
70 inline bool DynSSSP::modified() {
71  return mod;
72 }
73 
74 inline void DynSSSP::setTargetNode(const node t) {
75  target = t;
76 }
77 
78 inline std::vector<node> DynSSSP::getPredecessors(node t) const {
79  if (! storePreds) {
80  throw std::runtime_error("predecessors have not been stored");
81  }
82  return previous[t];
83 }
84 
85 } /* namespace NetworKit */
86 
87 #endif /* DYNSSSP_H_ */
Interface for dynamic approximated betweenness centrality algorithm.
Definition: DynApproxBetweenness.h:27
const node source
Definition: SSSP.h:128
bool storePreds
Definition: DynSSSP.h:65
std::vector< node > getPredecessors(node t) const
Returns the predecessor nodes of t on all shortest paths from source to t.
Definition: DynSSSP.h:78
const Graph & G
Definition: SSSP.h:127
bool modified()
Returns true or false depending on whether the node previoulsy specified with setTargetNode has been ...
Definition: DynSSSP.h:70
void setTargetNode(const node t=0)
Set a target node to be observed during the update.
Definition: DynSSSP.h:74
virtual ~DynSSSP()=default
Abstract base class for single-source shortest path algorithms.
Definition: SSSP.h:23
Definition: DynAlgorithm.h:10
DynSSSP(const Graph &G, node source, bool storePredecessors=true, node target=none)
The algorithm computes a dynamic SSSP starting from the specified source vertex.
Definition: DynSSSP.cpp:13
std::vector< std::vector< node > > previous
Definition: SSSP.h:131
node target
Definition: DynSSSP.h:67
constexpr index none
Constants.
Definition: Globals.h:28
index node
Definition: Globals.h:23
Interface for dynamic single-source shortest path algorithms.
Definition: DynSSSP.h:24
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79
bool mod
Definition: DynSSSP.h:66