Go to the documentation of this file.
1 /*
3  *
4  * Created on: 21.05.2014
5  * Author: Moritz v. Looz (moritz.looz-corswarem@kit.edu)
6  */
7
10
11 #include <vector>
12 #include <memory>
13 #include <cmath>
14 #include <omp.h>
15 #include <functional>
17 #include "../../geometric/HyperbolicSpace.h"
18 #include "../../auxiliary/Parallel.h"
19
20 namespace NetworKit {
21
22 template <class T, bool poincare=true>
25 public:
29  }
30
38  Quadtree(double maxR,bool theoreticalSplit=false, double alpha=1, count capacity=1000, double balance = 0.5) {
39  root = QuadNode<T,poincare>(0, 0, 2*M_PI, maxR, capacity, theoreticalSplit,alpha,balance);
41  }
42
43  Quadtree(const vector<double> &angles, const vector<double> &radii, const vector<T> &content, double stretch, bool theoreticalSplit=false, double alpha=1, count capacity=1000, double balance = 0.5) {
44  const count n = angles.size();
49  root = QuadNode<T>(0, 0, 2*M_PI, r, capacity, theoreticalSplit,alpha,balance);
51  for (index i = 0; i < n; i++) {
52  assert(content[i] < n);
54  }
55  }
56
62  void addContent(T newcomer, double angle, double r) {
64  }
65
71  bool removeContent(T toRemove, double angle, double r) {
72  return root.removeContent(toRemove, angle, r);
73  }
74
80  vector<T> getElements() const {
81  return root.getElements();
82  }
83
84  void extractCoordinates(vector<double> &anglesContainer, vector<double> &radiiContainer) const {
86  }
87
95  vector<T> getElementsInHyperbolicCircle(Point2D<double> circleCenter, double hyperbolicRadius) const {
96  vector<T> circleDenizens;
98  return circleDenizens;
99  }
100
101  void getElementsInHyperbolicCircle(const Point2D<double> circleCenter, const double hyperbolicRadius, const bool suppressLeft, vector<T> &circleDenizens) const {
102  assert(circleDenizens.empty());
103  double cc_phi, cc_r;
104  HyperbolicSpace::cartesianToPolar(circleCenter, cc_phi, cc_r);
105  //Transform hyperbolic circle into Euclidean circle
106  double minPhi, maxPhi, radius, r_e;
109  double minR = r_e - radius;
110  double maxR = r_e + radius;
111  //assert(maxR < 1);//this looks fishy
112  if (maxR > 1) maxR = 1;
113  if (minR < 0) {
114  maxR = std::max(abs(minR), maxR);
115  minR = 0;
116  minPhi = 0;
117  maxPhi = 2*M_PI;
118  } else {
120  //double phi_c, r_c;
121  //HyperbolicSpace::cartesianToPolar(center, phi_c, r_c);
122  minPhi = cc_phi - spread;
123  maxPhi = cc_phi + spread;
127  }
128
129  if (suppressLeft) minPhi = cc_phi;
134  bool wraparound = false;
135  root.getElementsInEuclideanCircle(center, radius, circleDenizens, minPhi, maxPhi, minR, maxR);
136  if (minPhi < 0) {
137  root.getElementsInEuclideanCircle(center, radius, circleDenizens, 2*M_PI+minPhi, 2*M_PI, minR, maxR);
138  wraparound = true;
139  }
140  if (maxPhi > 2*M_PI) {
141  root.getElementsInEuclideanCircle(center, radius, circleDenizens, 0, maxPhi - 2*M_PI, minR, maxR);
142  wraparound = true;
143  }
144
145  for (T denizen : circleDenizens) {
146  if (denizen >= size()) {
147  DEBUG("Content ", denizen, " found in quadtree of size ", size(), ", as one of ", circleDenizens.size(), " neighbours.");
148  }
149  assert(denizen < size());//TODO: remove this after debugging, in general the quadtree should handle arbitrary contents
150  }
151
152  //we have sort(deg(v)) here! This is not good, but does not make the asymptotical complexity of O(deg(v) log n) worse.
153  if (wraparound) {
154  Aux::Parallel::sort(circleDenizens.begin(), circleDenizens.end());
155  auto newend = unique(circleDenizens.begin(), circleDenizens.end());
156  count toRemove = circleDenizens.end() - newend;
157  count remaining = newend - circleDenizens.begin();
158  if (toRemove > 0) {
159  DEBUG("Removing, ", toRemove, " duplicate entries, keeping ", remaining);
160  circleDenizens.resize(remaining);
161  }
162  }
163
164  for (T denizen : circleDenizens) {
165  if (denizen >= size()) DEBUG("Content ", denizen, " found in quadtree of size ", size(), ", as one of ", circleDenizens.size(), " neighbours, after sorting");
166  assert(denizen < size());//TODO: remove this after debugging, in general the quadtree should handle arbitrary contents
167  }
168  }
169
170  void getElementsInHyperbolicCircle(const Point2D<double> circleCenter, const double hyperbolicRadius, vector<T> &circleDenizens) const {
172  }
173
174  count getElementsProbabilistically(Point2D<double> euQuery, std::function<double(double)> prob, vector<T> &circleDenizens) {
175  return root.getElementsProbabilistically(euQuery, prob, false, circleDenizens);
176  }
177
178  count getElementsProbabilistically(Point2D<double> euQuery, std::function<double(double)> prob, bool suppressLeft, vector<T> &circleDenizens) {
179  return root.getElementsProbabilistically(euQuery, prob, suppressLeft, circleDenizens);
180  }
181
182  void recount() {
183  root.recount();
184  }
185
186  count size() const {
187  return root.size();
188  }
189
190  count height() const {
191  return root.height();
192  }
193
194  count countLeaves() const {
195  return root.countLeaves();
196  }
197
199  return root.indexSubtree(nextID);
200  }
201
202  index getCellID(double phi, double r) const {
203  return root.getCellID(phi, r);
204  }
205
208  }
209
210  void reindex() {
211  #pragma omp parallel
212  {
213  #pragma omp single nowait
214  {
215  root.reindex(0);
216  }
217  }
218  }
219
223  void trim() {
224  root.trim();
225  }
226
227 private:
230 };
231 }
232
void recount()
Definition: HyperbolicSpace.h:128
Quadtree(const vector< double > &angles, const vector< double > &radii, const vector< T > &content, double stretch, bool theoreticalSplit=false, double alpha=1, count capacity=1000, double balance=0.5)
Project radial coordinates of the hyperbolic plane into the Poincare disk model.
Definition: HyperbolicSpace.cpp:139
vector< T > getElements() const
Get all elements, regardless of position.
uint64_t index
Typedefs.
Definition: Globals.h:20
#define DEBUG(...)
Definition: Log.h:82
static Point2D< double > polarToCartesian(double phi, double r)
Definition: HyperbolicSpace.cpp:98
vector< T > getElementsInHyperbolicCircle(Point2D< double > circleCenter, double hyperbolicRadius) const
Get elements whose hyperbolic distance to the query point is less than the hyperbolic distance...
void addContent(T newcomer, double angle, double r)
static void getEuclideanCircle(Point2D< double > hyperbolicCenter, double hyperbolicRadius, Point2D< double > &euclideanCenter, double &euclideanRadius)
Converts a hyperbolic circle to a Euclidean circle.
Definition: HyperbolicSpace.cpp:124
void extractCoordinates(vector< double > &anglesContainer, vector< double > &radiiContainer) const
uint64_t count
Definition: Globals.h:21
void getElementsInHyperbolicCircle(const Point2D< double > circleCenter, const double hyperbolicRadius, const bool suppressLeft, vector< T > &circleDenizens) const
count height() const
void trim()
trims the vectors used to hold the content in the leaf cells.
index getCellID(double phi, double r) const
bool removeContent(T toRemove, double angle, double r)
count getElementsProbabilistically(Point2D< double > euQuery, std::function< double(double)> prob, bool suppressLeft, vector< T > &circleDenizens)
static void cartesianToPolar(Point2D< double > a, double &phi, double &r)
Definition: HyperbolicSpace.cpp:113
count getElementsProbabilistically(Point2D< double > euQuery, std::function< double(double)> prob, vector< T > &circleDenizens)