All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
DynApproxBetweenness.h
Go to the documentation of this file.
1 /*
2  * DynApproxBetweenness.h
3  *
4  * Created on: 31.07.2014
5  * Author: ebergamini
6  */
7 
8 #ifndef DYNAPPROXBETW_H_
9 #define DYNAPPROXBETW_H_
10 
11 #include "Centrality.h"
12 #include "../base/DynAlgorithm.h"
13 #include "../dynamics/GraphEvent.h"
14 #include "../distance/DynSSSP.h"
15 
16 #include <math.h>
17 #include <algorithm>
18 #include <memory>
19 #include <omp.h>
20 
21 namespace NetworKit {
22 
28 
29 public:
43  DynApproxBetweenness(const Graph& G, const double epsilon=0.01, const double delta=0.1, const bool storePredecessors = true, const double universalConstant = 1.0);
44 
48  void run() override;
49 
56  void update(GraphEvent e) override;
57 
64  void updateBatch(const std::vector<GraphEvent>& batch) override;
65 
70 
71 private:
72  bool storePreds = true;
73  double epsilon;
74  double delta;
75  double universalConstant;
76  count r;
77  std::vector<std::unique_ptr<DynSSSP>> sssp;
78  std::vector<node> u;
79  std::vector<node> v;
80  std::vector <std::vector<node>> sampledPaths;
81 };
82 
83 } /* namespace NetworKit */
84 
85 #endif /* DYNAPPROXBETW_H_ */
Interface for dynamic approximated betweenness centrality algorithm.
Definition: DynApproxBetweenness.h:27
void run() override
Runs the static approximated betweenness centrality algorithm on the initial graph.
Definition: DynApproxBetweenness.cpp:30
count getNumberOfSamples()
Get number of path samples used for last calculation.
Definition: DynApproxBetweenness.cpp:25
DynApproxBetweenness(const Graph &G, const double epsilon=0.01, const double delta=0.1, const bool storePredecessors=true, const double universalConstant=1.0)
The algorithm approximates the betweenness of all vertices so that the scores are within an additive ...
Definition: DynApproxBetweenness.cpp:20
Definition: DynAlgorithm.h:10
const Graph & G
Definition: Centrality.h:91
Definition: GraphEvent.h:19
void updateBatch(const std::vector< GraphEvent > &batch) override
Updates the betweenness centralities after a batch of edge insertions on the graph.
Definition: DynApproxBetweenness.cpp:125
Abstract base class for centrality measures.
Definition: Centrality.h:20
uint64_t count
Definition: Globals.h:21
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79
void update(GraphEvent e) override
Updates the betweenness centralities after an edge insertions on the graph.
Definition: DynApproxBetweenness.cpp:118