All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
TopCloseness.h
Go to the documentation of this file.
1 /*
2  * TopCloseness.h
3  *
4  * Created on: 03.10.2014
5  * Author: ebergamini, michele borassi
6  */
7 
8 #ifndef TOPCLOSENESS_H_
9 #define TOPCLOSENESS_H_
10 #include "../graph/Graph.h"
11 #include "../base/Algorithm.h"
12 #include "../auxiliary/PrioQueue.h"
13 
14 namespace NetworKit {
15 
19 class TopCloseness : public Algorithm {
20 public:
21 
35  TopCloseness(const Graph& G, count k = 1, bool first_heu = true, bool sec_heu = true);
36 
40  void run();
41 
46  std::vector<node> topkNodesList();
47 
52  std::vector<edgeweight> topkScoresList();
53 
54 protected:
59  std::vector<node> topk;
61  count n_op = 0;
62  std::vector<std::vector<node>> levels;
63  std::vector<count> nodesPerLev;
64  count nLevs = 0;
65  std::vector<edgeweight> topkScores;
66  std::vector<count> maxlevel;
67  std::vector<count> maxlevelSize;
68  std::vector<std::vector<count>> subtree;
69  std::vector<double> farness;
70  std::vector<count> reachL;
71  std::vector<count> reachU;
72  std::vector<count> component;
73 
74  void init();
75  double BFScut(node v, double x, bool *visited, count *distances, node *pred, count *visEdges);
76  void computelBound1(std::vector<double> &S);
77  void BFSbound(node x, std::vector<double> &S, count *visEdges, const std::vector<bool> & toAnalyze);
78  void computeReachable();
81 };
82 
83 
84 inline std::vector<node> TopCloseness::topkNodesList() {
85  if (!hasRun) throw std::runtime_error("Call run method first");
86  return topk;
87 }
88 
89 inline std::vector<edgeweight> TopCloseness::topkScoresList() {
90  if (!hasRun) throw std::runtime_error("Call run method first");
91  return topkScores;
92 }
93 
94 } /* namespace NetworKit */
95 #endif /* TOPCLOSENESS_H_ */
std::vector< double > farness
Definition: TopCloseness.h:69
std::vector< count > reachU
Definition: TopCloseness.h:71
std::vector< std::vector< node > > levels
Definition: TopCloseness.h:62
count n_op
Definition: TopCloseness.h:61
Definition: TopCloseness.h:19
bool first_heu
Definition: TopCloseness.h:58
void init()
Definition: TopCloseness.cpp:30
TopCloseness(const Graph &G, count k=1, bool first_heu=true, bool sec_heu=true)
Finds the top k nodes with highest closeness centrality faster than computing it for all nodes...
Definition: TopCloseness.cpp:26
std::vector< std::vector< count > > subtree
Definition: TopCloseness.h:68
count n
Definition: TopCloseness.h:56
double BFScut(node v, double x, bool *visited, count *distances, node *pred, count *visEdges)
Definition: TopCloseness.cpp:330
std::vector< node > topk
Definition: TopCloseness.h:59
count k
Definition: TopCloseness.h:57
void computeReachableNodesDir()
Definition: TopCloseness.cpp:52
bool hasRun
A boolean variable indicating whether an algorithm has finished its computation or not...
Definition: Algorithm.h:14
count visEdges
Definition: TopCloseness.h:60
std::vector< edgeweight > topkScoresList()
Returns a list with the scores of the k nodes with highest closeness.
Definition: TopCloseness.h:89
Graph G
Definition: TopCloseness.h:55
bool sec_heu
Definition: TopCloseness.h:58
void computeReachableNodesUndir()
Definition: TopCloseness.cpp:162
std::vector< count > maxlevel
Definition: TopCloseness.h:66
uint64_t count
Definition: Globals.h:21
std::vector< count > nodesPerLev
Definition: TopCloseness.h:63
index node
Definition: Globals.h:23
std::vector< node > topkNodesList()
Returns a list with the k nodes with highest closeness.
Definition: TopCloseness.h:84
std::vector< edgeweight > topkScores
Definition: TopCloseness.h:65
count nLevs
Definition: TopCloseness.h:64
std::vector< count > maxlevelSize
Definition: TopCloseness.h:67
std::vector< count > component
Definition: TopCloseness.h:72
Definition: Algorithm.h:9
void computelBound1(std::vector< double > &S)
Definition: TopCloseness.cpp:175
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79
void computeReachable()
Definition: TopCloseness.cpp:44
std::vector< count > reachL
Definition: TopCloseness.h:70
void BFSbound(node x, std::vector< double > &S, count *visEdges, const std::vector< bool > &toAnalyze)
Definition: TopCloseness.cpp:260
void run()
Computes top-k closeness on the graph passed in the constructor.
Definition: TopCloseness.cpp:406