LocalFilterScore.h
Go to the documentation of this file.
1 /*
2  * LocalFilterScore.h
3  *
4  * Created on: 20.11.2014
5  * Author: Michael Hamann, Gerd Lindner
6  */
7
8 #ifndef LOCALLOGSCORE_H
9 #define LOCALLOGSCORE_H
10
11 #include "../edgescores/EdgeScore.h"
12 #include "../auxiliary/Parallel.h"
13
14 namespace NetworKit {
15
22 template<typename InType>
23 class LocalFilterScore : public EdgeScore<double> {
24
25 public:
33  LocalFilterScore(const Graph& G, const std::vector< InType > &attribute, bool logarithmic = true) :
34  EdgeScore<double>(G), attribute(attribute), logarithmic(logarithmic) {}
35
39  virtual void run() {
40  if (!G.hasEdgeIds()) {
41  throw std::runtime_error("edges have not been indexed - call indexEdges first");
42  }
43
44  /*
45  * For each edge, we calculate the minimum required sparsification exponent e
46  * such that the edge is contained in the sparse graph.
47  */
48
49  std::vector<std::atomic<double>> sparsificationExp(G.upperEdgeIdBound());
50
52  count d = G.degree(i);
53
54  /*
55  * The top d^e edges (sorted by similarity in descending order)
56  * are to be kept in the sparse graph.
57  */
58
59  std::vector<edgeid> neighbors;
60  neighbors.reserve(d);
61  G.forNeighborsOf(i, [&](node _i, node j, edgeid eid) {
62  neighbors.emplace_back(eid);
63  });
64
65  std::sort(neighbors.begin(), neighbors.end(), [&](const edgeid& e1, const edgeid& e2) {
66  return attribute[e1] > attribute[e2];
67  });
68
69  count rank = 0;
70  count numSame = 1;
71  InType oldValue = std::numeric_limits<InType>::lowest();
72
73  for (edgeid eid : neighbors) {
74  if (attribute[eid] != oldValue) {
75  rank += numSame;
76  numSame = 1;
77  } else {
78  ++numSame;
79  }
80
81  double e = 1.0;
82
83  if (d > 1) {
84  if (logarithmic) {
85  e = 1.0 - log(rank) / log(d);
86  } else {
87  e = 1.0 - (rank-1) * 1.0 / (d - 1); // Keep top 1 + e * (d-1) edges
88  }
89  }
90
91  Aux::Parallel::atomic_max(sparsificationExp[eid], e);
92  }
93
94  });
95
96  scoreData.clear();
97  scoreData.resize(G.upperEdgeIdBound());
98
99  #pragma omp parallel for
100  for (index i = 0; i < scoreData.size(); ++i) {
101  scoreData[i] = sparsificationExp[i];
102  }
103
104  hasRun = true;
105  }
106
107  virtual double score(node u, node v) {
108  throw std::runtime_error("Not implemented: Use scores() instead.");
109  }
110
111  virtual double score(edgeid eid) {
112  throw std::runtime_error("Not implemented: Use scores() instead.");
113  }
114
115 private:
116  const std::vector<InType>& attribute;
117  bool logarithmic;
118
119 };
120
121 } // namespace NetworKit
122
123 #endif // LOCALLOGSCORE_H
std::vector< double > scoreData
Definition: EdgeScore.h:44
index edgeid
Definition: Globals.h:25
void log(const Location &loc, LogLevel p, const std::string msg)
Definition: Log.cpp:202
const Graph & G
Definition: EdgeScore.h:43
uint64_t index
Typedefs.
Definition: Globals.h:20
void atomic_max(std::atomic< ValueType > &target, const ValueType &input)
Definition: Parallel.h:39
index upperEdgeIdBound() const
Get an upper bound for the edge ids in the graph.
Definition: Graph.h:421
count degree(node v) const
NODE PROPERTIES.
Definition: Graph.h:565
bool hasRun
A boolean variable indicating whether an algorithm has finished its computation or not...
Definition: Algorithm.h:14
Local filtering edge scoring.
Definition: LocalFilterScore.h:23
LocalFilterScore(const Graph &G, const std::vector< InType > &attribute, bool logarithmic=true)
Initialize the local edge filtering score.
Definition: LocalFilterScore.h:33
virtual double score(edgeid eid)
Get the edge score of the edge with the given edge id.
Definition: LocalFilterScore.h:111
uint64_t count
Definition: Globals.h:21
index node
Definition: Globals.h:23
void balancedParallelForNodes(L handle) const
Iterate in parallel over all nodes of the graph and call handler (lambda closure).
Definition: Graph.h:1137
bool hasEdgeIds() const
Checks if edges have been indexed.
Definition: Graph.h:410
void forNeighborsOf(node u, L handle) const
Iterate over all neighbors of a node and call handle (lamdba closure).
Definition: Graph.h:1378
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79
virtual double score(node u, node v)
Get the edge score of the given edge.
Definition: LocalFilterScore.h:107
Abstract base class for an edge score.
Definition: EdgeScore.h:20
virtual void run()
Execute the algorithm.
Definition: LocalFilterScore.h:39