All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
ApproxCloseness.h
Go to the documentation of this file.
1 /*
2  * ApproxCloseness.h
3  *
4  * Created on: Dec 8, 2015
5  * Author: Sarah Lutteropp (uwcwa@student.kit.edu) and Michael Wegner (michael.wegner@student.kit.edu)
6  */
7 
8 #ifndef NETWORKIT_CPP_CENTRALITY_APPROXCLOSENESS_H_
9 #define NETWORKIT_CPP_CENTRALITY_APPROXCLOSENESS_H_
10 
11 #include "Centrality.h"
12 #include <limits>
13 
14 namespace NetworKit {
15 
22 
23 public:
25 
39  ApproxCloseness(const Graph& G, count nSamples, double epsilon = 0.1, bool normalized=false, CLOSENESS_TYPE type = OUTBOUND);
40 
41 
45  void run() override;
46 
50  double maximum() override;
51 
55  std::vector<double> getSquareErrorEstimates();
56 
57 private:
58  count nSamples;
59  double epsilon;
60 
62  std::vector<double> LCSum;
63 
65  std::vector<count> LCNum;
66 
68  std::vector<double> LCSumSQ;
69 
71  std::vector<double> HCSum;
72 
74  std::vector<double> HCSumSQErr;
75 
77  std::vector<double> HSum;
78 
80  std::vector<count> HNum;
81 
83  std::vector<double> R;
84 
85  std::vector<double> SQErrEst;
86  const edgeweight infDist = floor(std::numeric_limits<edgeweight>::max() / 2.0); // divided by two s.t. infDist + infDist produces no overflow
87 
88  CLOSENESS_TYPE type;
89 
90  void estimateClosenessForUndirectedGraph();
91  void estimateClosenessForDirectedGraph(bool outbound);
92  inline void computeClosenessForDirectedWeightedGraph(bool outbound);
93  inline void computeClosenessForDirectedUnweightedGraph(bool outbound);
94 
102  void computeClosestPivot(const std::vector<node> &samples, std::vector<node> &pivot, std::vector<edgeweight> &delta);
103 
111  void runOnPivot(index i, const std::vector<node> &pivot, const std::vector<edgeweight> &delta, const std::vector<node> &samples);
112 
119  void orderNodesByIncreasingDistance(node pivot, std::vector<node> &order, std::vector<edgeweight> &pivotDist);
120 
121 };
122 
123 } /* namespace NetworKit */
124 
125 #endif /* NETWORKIT_CPP_CENTRALITY_APPROXCLOSENESS_H_ */
void run() override
Computes closeness approximation on the graph passed in constructor.
Definition: ApproxCloseness.cpp:24
bool normalized
Definition: Centrality.h:94
uint64_t index
Typedefs.
Definition: Globals.h:20
Definition: ApproxCloseness.h:24
double maximum() override
Returns the maximum possible Closeness a node can have in a graph with the same amount of nodes (=a s...
Definition: ApproxCloseness.cpp:410
const Graph & G
Definition: Centrality.h:91
ApproxCloseness(const Graph &G, count nSamples, double epsilon=0.1, bool normalized=false, CLOSENESS_TYPE type=OUTBOUND)
Constructs an instance of the ApproxCloseness class for graph using nSamples during the run() method...
Definition: ApproxCloseness.cpp:20
Definition: ApproxCloseness.h:24
Abstract base class for centrality measures.
Definition: Centrality.h:20
uint64_t count
Definition: Globals.h:21
CLOSENESS_TYPE
Definition: ApproxCloseness.h:24
index node
Definition: Globals.h:23
Approximation of closeness centrality according to algorithm described in Cohen et al...
Definition: ApproxCloseness.h:21
Definition: ApproxCloseness.h:24
std::vector< double > getSquareErrorEstimates()
Definition: ApproxCloseness.cpp:414
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79
double edgeweight
Definition: Globals.h:24