HyperbolicSpace.h
Go to the documentation of this file.
1 /*
2  * HyperbolicSpace.h
3  *
4  * Created on: 20.05.2014
5  * Author: Moritz v. Looz (moritz.looz-corswarem@kit.edu)
6  */
7
8 #ifndef HYPERBOLICSPACE_H_
9 #define HYPERBOLICSPACE_H_
10
11 #include <vector>
12 #include <map>
13 #include <cmath>
14 #include "Point2D.h"
15 #include "../viz/Point.h"
16 #include "../auxiliary/Random.h"
17
18 using std::vector;
19 using std::abs;
20
21 namespace NetworKit {
22
24 public:
25  HyperbolicSpace() = default;
26  virtual ~HyperbolicSpace() = default;
35  static void fillPoints(vector<double> &angles, vector<double> &radii, double R, double alpha);
36
45  static void fillPoints(vector<double> &angles, vector<double> &radii, double minPhi, double maxPhi, double minR, double maxR, double alpha);
46
55  static double poincareMetric(double firstangle, double firstR, double secondangle, double secondR);
56
65  static double nativeDistance(double firstangle, double firstR, double secondangle, double secondR);
66
74
75
76
83  static Point2D<double> polarToCartesian(double phi, double r);
84
88  static std::map<index, Point<float> > polarToCartesian(const vector<double> &angles, const vector<double> &radii);
89
95  static void cartesianToPolar(Point2D<double> a, double &phi, double &r);
96
107
115
123
128  static inline double hyperbolicAreaToRadius(double area) {
129  return acosh(area/(2*M_PI)+1);
130  }
131
134  }
135
136  static double getExpectedDegree(double n, double alpha, double R) {
137  double gamma = 2*alpha+1;
138  double xi = (gamma-1)/(gamma-2);
139  double firstSumTerm = exp(-R/2);
140  double secondSumTerm = exp(-alpha*R)*(alpha*(R/2)*((M_PI/4)*pow((1/alpha),2)-(M_PI-1)*(1/alpha)+(M_PI-2))-1);
141  double expectedDegree = (2/M_PI)*xi*xi*n*(firstSumTerm + secondSumTerm);
142  return expectedDegree;
143  }
144
145  static double searchTargetRadiusForColdGraphs(double n, double k, double alpha, double epsilon) {
146  double gamma = 2*alpha+1;
147  double xiInv = ((gamma-2)/(gamma-1));
148  double v = k * (M_PI/2)*xiInv*xiInv;
149  double currentR = 2*log(n / v);
150  double lowerBound = currentR/2;
151  double upperBound = currentR*2;
152  assert(getExpectedDegree(n, alpha, lowerBound) > k);
153  assert(getExpectedDegree(n, alpha, upperBound) < k);
154  do {
155  currentR = (lowerBound + upperBound)/2;
156  double currentK = getExpectedDegree(n, alpha, currentR);
157  if (currentK < k) {
158  upperBound = currentR;
159  } else {
160  lowerBound = currentR;
161  }
162  } while (abs(getExpectedDegree(n, alpha, currentR) - k) > epsilon );
163  return currentR;
164  }
165
166  static double getTargetRadius(double n, double m, double alpha=1, double T=0, double epsilon = 0.01) {
167  double result;
168  double plexp = 2*alpha+1;
169  double targetAvgDegree = (m/n)*2;
170  double xiInv = ((plexp-2)/(plexp-1));
171  if (T == 0) {
172  double v = targetAvgDegree * (M_PI/2)*xiInv*xiInv;
173  result = 2*log(n / v);
174  TRACE("expected:", getExpectedDegree(n, alpha, result));
175  result = searchTargetRadiusForColdGraphs(n, targetAvgDegree, alpha, epsilon);
176  } else {
177  double beta = 1/T;
178  if (T < 1){//cold regime
179  double Iinv = ((beta/M_PI)*sin(M_PI/beta));
180  double v = (targetAvgDegree*Iinv)*(M_PI/2)*xiInv*xiInv;
181  result = 2*log(n / v);
182  } else {//hot regime
183  double v = targetAvgDegree*(1-beta)*pow((M_PI/2), beta)*xiInv*xiInv;
184  result = 2*log(n/v)/beta;
185  }
186  }
187  return result;
188  }
189
190  static inline double effectiveAreaInCell(double minPhi, double maxPhi, double minR, double maxR, double alpha) {
191  double deltaPhi = maxPhi - minPhi;
192  assert(deltaPhi >= 0);
193  assert(deltaPhi <= 2*M_PI);
195  return ringArea*(deltaPhi/(2*M_PI));
196  }
197
203  static double hyperbolicSpaceInEuclideanCircle(double r_c, double d_c, double R);
204
208  static double maxRinSlice(double minPhi, double maxPhi, double phi_c, double r_c, double euRadius);
209 };
210 }
211
212 #endif /* HYPERBOLICSPACE_H_ */
virtual ~HyperbolicSpace()=default
static double poincareMetric(double firstangle, double firstR, double secondangle, double secondR)
This distance measure is taken from the PoincarĂ© disc model.
Definition: HyperbolicSpace.cpp:44
static double maxRinSlice(double minPhi, double maxPhi, double phi_c, double r_c, double euRadius)
Definition: HyperbolicSpace.cpp:150
static double effectiveAreaInCell(double minPhi, double maxPhi, double minR, double maxR, double alpha)
Definition: HyperbolicSpace.h:190
Definition: HyperbolicSpace.h:128
static double searchTargetRadiusForColdGraphs(double n, double k, double alpha, double epsilon)
Definition: HyperbolicSpace.h:145
static double getExpectedDegree(double n, double alpha, double R)
Definition: HyperbolicSpace.h:136
Project radial coordinates of the hyperbolic plane into the Poincare disk model.
Definition: HyperbolicSpace.cpp:139
void log(const Location &loc, LogLevel p, const std::string msg)
Definition: Log.cpp:202
static Point2D< double > polarToCartesian(double phi, double r)
Definition: HyperbolicSpace.cpp:98
Project radial coordinates of the Poincare model into the hyperbolic plane.
Definition: HyperbolicSpace.cpp:144
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
static double nativeDistance(double firstangle, double firstR, double secondangle, double secondR)
Definition: HyperbolicSpace.cpp:20
static double hyperbolicSpaceInEuclideanCircle(double r_c, double d_c, double R)
Definition: HyperbolicSpace.cpp:163
static void cartesianToPolar(Point2D< double > a, double &phi, double &r)
Definition: HyperbolicSpace.cpp:113