All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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 
105  static void getEuclideanCircle(Point2D<double> hyperbolicCenter, double hyperbolicRadius, Point2D<double> &euclideanCenter, double &euclideanRadius);
106  static void getEuclideanCircle(double r_h, double hyperbolicRadius, double &radialCoordOfEuclideanCenter, double &euclideanRadius);
107 
114  static double hyperbolicRadiusToEuclidean(double hyperbolicRadius);
115 
122  static double EuclideanRadiusToHyperbolic(double EuclideanRadius);
123 
128  static inline double hyperbolicAreaToRadius(double area) {
129  return acosh(area/(2*M_PI)+1);
130  }
131 
132  static inline double radiusToHyperbolicArea(double radius) {
133  return 2*M_PI*(cosh(radius)-1);
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
static double hyperbolicAreaToRadius(double area)
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
static double hyperbolicRadiusToEuclidean(double hyperbolicRadius)
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
static double EuclideanRadiusToHyperbolic(double EuclideanRadius)
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
static double radiusToHyperbolicArea(double radius)
Definition: HyperbolicSpace.h:132
Definition: HyperbolicSpace.h:23
#define TRACE(...)
Definition: Log.h:92
static double getTargetRadius(double n, double m, double alpha=1, double T=0, double epsilon=0.01)
Definition: HyperbolicSpace.h:166
static void fillPoints(vector< double > &angles, vector< double > &radii, double R, double alpha)
Definition: HyperbolicSpace.cpp:67