All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
DynBetweenness.h
Go to the documentation of this file.
1 /*
2  * DynBetweenness.h
3  *
4  * Created on: 12.08.2015
5  * Author: Arie Slobbe, Elisabetta Bergamini
6  */
7 
8 #ifndef DYNBETWEENNESS_H_
9 #define DYNBETWEENNESS_H_
10 
11 #include "Centrality.h"
12 #include <queue>
13 #include <memory>
14 #include "../dynamics/GraphEvent.h"
15 #include "../base/DynAlgorithm.h"
16 #include "../auxiliary/PrioQueue.h"
17 #include "../auxiliary/PrioQueueForInts.h"
18 
19 namespace NetworKit {
20 
22 {
23 public:
24  bool operator()(std::pair<double,node> n1,std::pair<double,node> n2) {
25  return n1.first > n2.first;
26  }
27 };
28 
29 
34 class DynBetweenness: public Centrality, public DynAlgorithm {
35 
36 public:
43 
47  void run() override;
48 
55  void update(GraphEvent e) override;
56 
63  void updateBatch(const std::vector<GraphEvent>& batch) override;
64 
65 
67  count visPairs();
68 
71 
73 
75 
76  double getTimeDep();
77 
78 
79 private:
80  void increaseScore(std::vector<bool> & affected, node y, std::priority_queue<std::pair<double, node>, std::vector<std::pair<double,node>>, CompareDist> & Q);
81  void decreaseScore(std::vector<bool> & affected, node y, std::priority_queue<std::pair<double, node>, std::vector<std::pair<double,node>>, CompareDist> & Q);
82  node u;
83  node v;
84  count diameter = 0;
85  const edgeweight infDist = std::numeric_limits<edgeweight>::max();
86  const edgeweight epsilon = 0.0000000001; //make sure that no legitimate edge weight is below that.
87  count visitedPairs = 0;
88  std::vector<std::vector<edgeweight>> distances;
89  std::vector<std::vector<edgeweight>> distancesOld;
90  // total number of shortest paths between two nodes
91  std::vector<std::vector<edgeweight>> sigma;
92  std::vector<std::vector<edgeweight>> sigmaOld;
93 
94  count affectedAPSP = 0;
95  count affectedDep = 0;
96  double timeDep = 0;
97 };
98 
99 } /* namespace NetworKit */
100 
101 #endif /* DynBETWEENNESS_H_ */
void update(GraphEvent e) override
Updates the betweenness centralities after an edge insertions on the graph.
Definition: DynBetweenness.cpp:163
count numAffectedDep()
Definition: DynBetweenness.cpp:360
count numAffectedAPSP()
Definition: DynBetweenness.cpp:356
bool operator()(std::pair< double, node > n1, std::pair< double, node > n2)
Definition: DynBetweenness.h:24
Definition: DynAlgorithm.h:10
DynBetweenness(Graph &G)
Creates the object for G.
Definition: DynBetweenness.cpp:33
const Graph & G
Definition: Centrality.h:91
Definition: GraphEvent.h:19
Definition: DynBetweenness.h:21
count visPairs()
Returns number of visited pairs.
Definition: DynBetweenness.cpp:352
Abstract base class for centrality measures.
Definition: Centrality.h:20
uint64_t count
Definition: Globals.h:21
index node
Definition: Globals.h:23
Dynamic APSP.
Definition: DynBetweenness.h:34
edgeweight getDistance(node u, node v)
Definition: DynBetweenness.cpp:344
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79
double getTimeDep()
Definition: DynBetweenness.cpp:364
edgeweight getSigma(node u, node v)
Definition: DynBetweenness.cpp:348
void run() override
Runs static betweenness centrality algorithm on the initial graph.
Definition: DynBetweenness.cpp:42
void updateBatch(const std::vector< GraphEvent > &batch) override
Updates the betweenness centralities after a batch of edge insertions on the graph.
Definition: DynBetweenness.cpp:338
double edgeweight
Definition: Globals.h:24