All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
HyperbolicGenerator.h
Go to the documentation of this file.
1 /*
2  * HyperbolicGenerator.h
3  *
4  * Created on: 20.05.2014
5  * Author: Moritz v. Looz (moritz.looz-corswarem@kit.edu)
6  */
7 
8 #ifndef HYPERBOLICGENERATOR_H_
9 #define HYPERBOLICGENERATOR_H_
10 
11 #include <vector>
12 #include "../geometric/HyperbolicSpace.h"
13 #include "StaticGraphGenerator.h"
14 #include "../auxiliary/Timer.h"
15 #include "quadtree/Quadtree.h"
16 
17 namespace NetworKit {
18 
21 public:
22 
29  HyperbolicGenerator(count n=10000, double avgDegree=6, double exp=3, double T=0);
30 
38  Graph generate(const vector<double> &angles, const vector<double> &radii, double R, double T=0);
39  Graph generateCold(const vector<double> &angles, const vector<double> &radii, double R);
40 
44  Graph generate();
45 
51  void setLeafCapacity(count capacity) {
52  this->capacity = capacity;
53  }
54 
60  this->theoreticalSplit = split;
61  }
62 
63  void setBalance(double balance) {
64  this->balance = balance;
65  }
66 
67  vector<double> getElapsedMilliseconds() const {
68  vector<double> result(threadtimers.size());
69  for (index i = 0; i < result.size(); i++) {
70  result[i] = threadtimers[i].elapsedMilliseconds();
71  }
72  return result;
73  }
74 
75 private:
76 
80  void initialize();
81 
82  Graph generate(count n, double R, double alpha, double T = 0);
83 
84  static vector<vector<double> > getBandAngles(const vector<vector<Point2D<double>>> &bands) {
85  vector<vector<double>> bandAngles(bands.size());
86  #pragma omp parallel for
87  for(index i=0; i < bands.size(); i++){
88  const count currentBandSize = bands[i].size();
89  bandAngles[i].resize(currentBandSize);
90  for(index j=0; j < currentBandSize; j++) {
91  bandAngles[i][j] = bands[i][j].getX();
92  }
93  }
94  return bandAngles;
95  }
96 
97  static vector<double> getBandRadii(int n, double R, double seriesRatio = 0.9) {
98  /*
99  * We assume band differences form a geometric series.
100  * Thus, there is a constant ratio(r) between band length differences
101  * i.e (c2-c1)/(c1-c0) = (c3-c2)/(c2-c1) = r
102  */
103  vector<double> bandRadius;
104  bandRadius.push_back(0);
105  double a = R*(1-seriesRatio)/(1-pow(seriesRatio, log(n)));
106  const double logn = log(n);
107 
108  for (int i = 1; i < logn; i++){
109  double c_i = a*((1-pow(seriesRatio, i))/(1-seriesRatio));
110  bandRadius.push_back(c_i);
111  }
112  bandRadius.push_back(R);
113  return bandRadius;
114  }
115 
116  static std::tuple<double, double> getMinMaxTheta(double angle, double radius, double cLow, double thresholdDistance) {
117  /*
118  Calculates the angles that are enclosing the intersection of the
119  hyperbolic disk that is around point v and the bands.
120  Calculation is as follows:
121  1. For the most inner band, return [0, 2pi]
122  2. For other bands, consider the point P which lies on the tangent from origin to the disk of point v.
123  Its radial coordinates would be(cHigh, point[1]+deltaTheta). We're looking for the deltaTheta.
124  We know the distance from point v to P is R. Thus, we can solve the hyperbolic distance of (v, P)
125  for deltaTheta. Then, thetaMax is simply point[1] + deltaTheta and thetaMin is point[1] - deltaTheta
126  */
127 
128  //Most innerband is defined by cLow = 0
129  double minTheta, maxTheta;
130  if (cLow == 0)
131  return std::make_tuple(0, 2* M_PI);
132 
133  double a = (cosh(radius)*cosh(cLow) - cosh(thresholdDistance))/(sinh(radius)*sinh(cLow));
134  //handle floating point error
135  if(a < -1)
136  a = -1;
137  else if(a > 1)
138  a = 1;
139  a = acos(a);
140  maxTheta = angle + a;
141  minTheta = angle - a;
142  return std::make_tuple(minTheta, maxTheta);
143  }
144 
145  static vector<Point2D<double>> getPointsWithinAngles(double minTheta, double maxTheta, const vector<Point2D<double>> &band, vector<double> &bandAngles){
150  //TODO: There should be a better way to write the whole thing. Find it.
151  //TODO: This can be done faster. Instead of returning the copying to slab array, just return the indexes and iterate over the band array
152  assert(band.size() == bandAngles.size());
153 
154  vector<Point2D<double>> slab;
155 
156  std::vector<double>::iterator low;
157  std::vector<double>::iterator high;
158 
159  if(minTheta == -2*M_PI)
160  minTheta = 0;
161  //Case 1: We do not have overlap 2pi, simply put all the points between min and max to the list
162  if(maxTheta <= 2*M_PI && minTheta >= 0){
163  low = std::lower_bound(bandAngles.begin(), bandAngles.end(), minTheta);
164  high = std::upper_bound(bandAngles.begin(), bandAngles.end(), maxTheta);
165  std::vector<Point2D<double>>::const_iterator first = band.begin() + (low - bandAngles.begin());
166  std::vector<Point2D<double>>::const_iterator last = band.begin() + (high - bandAngles.begin());
167  //Q: Does this operation increases the complexity ? It is linear in times of high - low
168  //Does not increase the complexity, since we have to check these points anyway
169  slab.insert(slab.end(), first, last);
170  }
171  //Case 2: We have 'forward' overlap at 2pi, that is maxTheta > 2pi
172  else if (maxTheta > 2*M_PI){
173  //1. Get points from minTheta to 2pi
174  low = std::lower_bound(bandAngles.begin(), bandAngles.end(), minTheta);
175  high = std::upper_bound(bandAngles.begin(), bandAngles.end(), 2*M_PI);
176  std::vector<Point2D<double>>::const_iterator first = band.begin() + (low - bandAngles.begin());
177  std::vector<Point2D<double>>::const_iterator last = band.begin() + (high - bandAngles.begin());
178  slab.insert(slab.end(), first, last);
179 
180  //2. Get points from 0 to maxTheta%2pi
181  low = std::lower_bound(bandAngles.begin(), bandAngles.end(), 0);
182  maxTheta = fmod(maxTheta, (2*M_PI));
183  high = std::upper_bound(bandAngles.begin(), bandAngles.end(), maxTheta);
184  std::vector<Point2D<double>>::const_iterator first2 = band.begin() + (low - bandAngles.begin());
185  std::vector<Point2D<double>>::const_iterator last2 = band.begin() + (high - bandAngles.begin());
186  slab.insert(slab.end(), first2, last2);
187  }
188  //Case 3: We have 'backward' overlap at 2pi, that is minTheta < 0
189  else if (minTheta < 0){
190  //1. Get points from 2pi + minTheta to 2pi
191  minTheta = (2*M_PI) + minTheta;
192  low = std::lower_bound(bandAngles.begin(), bandAngles.end(), minTheta);
193  high = std::upper_bound(bandAngles.begin(), bandAngles.end(), 2*M_PI);
194  std::vector<Point2D<double>>::const_iterator first = band.begin() + (low - bandAngles.begin());
195  std::vector<Point2D<double>>::const_iterator last = band.begin() + (high - bandAngles.begin());
196  slab.insert(slab.end(), first, last);
197  //2. Get points from 0 to maxTheta
198  low = std::lower_bound(bandAngles.begin(), bandAngles.end(), 0);
199  high = std::upper_bound(bandAngles.begin(), bandAngles.end(), maxTheta);
200  std::vector<Point2D<double>>::const_iterator first2 = band.begin() + (low - bandAngles.begin());
201  std::vector<Point2D<double>>::const_iterator last2 = band.begin() + (high - bandAngles.begin());
202  slab.insert(slab.end(), first2, last2);
203  }
204  return slab;
205  }
206 
210  count nodeCount;
211  double R;
212  double alpha;
213  double temperature;
214 
218  count capacity;
219  bool theoreticalSplit;
220  double balance = 0.5;
221  static const bool directSwap = false;
222 
226  vector<Aux::Timer> threadtimers;
227 };
228 }
229 #endif /* HYPERBOLICGENERATOR_H_ */
void setTheoreticalSplit(bool split)
When using a theoretically optimal split, the quadtree will be flatter, but running time usually long...
Definition: HyperbolicGenerator.h:59
void setLeafCapacity(count capacity)
Set the capacity of a quadtree leaf.
Definition: HyperbolicGenerator.h:51
void setBalance(double balance)
Definition: HyperbolicGenerator.h:63
void log(const Location &loc, LogLevel p, const std::string msg)
Definition: Log.cpp:202
Definition: HyperbolicGenerator.h:19
uint64_t index
Typedefs.
Definition: Globals.h:20
Abstract base class for static graph generators.
Definition: StaticGraphGenerator.h:19
Graph generate()
Definition: HyperbolicGenerator.cpp:67
Graph generateCold(const vector< double > &angles, const vector< double > &radii, double R)
Definition: HyperbolicGenerator.cpp:99
HyperbolicGenerator(count n=10000, double avgDegree=6, double exp=3, double T=0)
Construct a generator for n nodes and m edges.
Definition: HyperbolicGenerator.cpp:40
uint64_t count
Definition: Globals.h:21
vector< double > getElapsedMilliseconds() const
Definition: HyperbolicGenerator.h:67
std::vector< std::string > split(Iterator begin, Iterator end, Character delim=Character{' '})
Splits a range of characters at a delimiter into a vector of strings.
Definition: StringTools.h:31
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79
Definition: DynamicHyperbolicGenerator.h:19