Program Listing for File HyperbolicSpace.hpp¶

/*
 * HyperbolicSpace.hpp
 *
 *  Created on: 20.05.2014
 *      Author: Moritz v. Looz
 */

#ifndef NETWORKIT_GEOMETRIC_HYPERBOLIC_SPACE_HPP_
#define NETWORKIT_GEOMETRIC_HYPERBOLIC_SPACE_HPP_

#include <cmath>
#include <map>
#include <vector>

#include <networkit/auxiliary/Random.hpp>
#include <networkit/geometric/Point2DWithIndex.hpp>
#include <networkit/viz/Point.hpp>

using std::abs;
using std::vector;

namespace NetworKit {

class HyperbolicSpace final {
public:
    HyperbolicSpace() = default;
    ~HyperbolicSpace() = default;
    static void fillPoints(vector<double> &angles, vector<double> &radii, double R, double alpha);

    static void fillPoints(vector<double> &angles, vector<double> &radii, double minPhi,
                           double maxPhi, double minR, double maxR, double alpha);

    static void fillPointsSorted(vector<double> &angles, vector<double> &radii, double R,
                                 double alpha);

    static void fillPointsSorted(vector<double> &angles, vector<double> &radii, double minPhi,
                                 double maxPhi, double minR, double maxR, double alpha);

    static double poincareMetric(double firstangle, double firstR, double secondangle,
                                 double secondR);

    static double nativeDistance(double firstangle, double firstR, double secondangle,
                                 double secondR);

    static double poincareMetric(Point2DWithIndex<double> a, Point2DWithIndex<double> b);

    static Point2DWithIndex<double> polarToCartesian(double phi, double r);

    static std::map<index, Point<float>> polarToCartesian(const vector<double> &angles,
                                                          const vector<double> &radii);

    static void cartesianToPolar(Point2DWithIndex<double> a, double &phi, double &r);

    static void getEuclideanCircle(Point2DWithIndex<double> hyperbolicCenter,
                                   double hyperbolicRadius,
                                   Point2DWithIndex<double> &euclideanCenter,
                                   double &euclideanRadius);
    static void getEuclideanCircle(double r_h, double hyperbolicRadius,
                                   double &radialCoordOfEuclideanCenter, double &euclideanRadius);

    static double hyperbolicRadiusToEuclidean(double hyperbolicRadius);

    static double EuclideanRadiusToHyperbolic(double EuclideanRadius);

    static inline double hyperbolicAreaToRadius(double area) {
        return std::acosh(area / (2 * PI) + 1);
    }

    static inline double radiusToHyperbolicArea(double radius) {
        return 2 * PI * (std::cosh(radius) - 1);
    }

    static double getExpectedDegree(double n, double alpha, double R) {
        double gamma = 2 * alpha + 1;
        double xi = (gamma - 1) / (gamma - 2);
        double firstSumTerm = std::exp(-R / 2);
        double secondSumTerm =
            std::exp(-alpha * R)
            * (alpha * (R / 2)
                   * ((PI / 4) * std::pow((1 / alpha), 2) - (PI - 1) * (1 / alpha) + (PI - 2))
               - 1);
        double expectedDegree = (2 / PI) * xi * xi * n * (firstSumTerm + secondSumTerm);
        return expectedDegree;
    }

    static double searchTargetRadiusForColdGraphs(double n, double k, double alpha,
                                                  double epsilon) {
        double gamma = 2 * alpha + 1;
        double xiInv = ((gamma - 2) / (gamma - 1));
        double v = k * (PI / 2) * xiInv * xiInv;
        double currentR = 2 * std::log(n / v);
        double lowerBound = currentR / 2;
        double upperBound = currentR * 2;
        assert(getExpectedDegree(n, alpha, lowerBound) > k);
        assert(getExpectedDegree(n, alpha, upperBound) < k);
        do {
            currentR = (lowerBound + upperBound) / 2;
            double currentK = getExpectedDegree(n, alpha, currentR);
            if (currentK < k) {
                upperBound = currentR;
            } else {
                lowerBound = currentR;
            }
        } while (abs(getExpectedDegree(n, alpha, currentR) - k) > epsilon);
        return currentR;
    }

    static double getTargetRadius(double n, double m, double alpha = 1, double T = 0,
                                  double epsilon = 0.01) {
        double result;
        double plexp = 2 * alpha + 1;
        double targetAvgDegree = (m / n) * 2;
        double xiInv = ((plexp - 2) / (plexp - 1));
        if (T == 0) {
            result = searchTargetRadiusForColdGraphs(n, targetAvgDegree, alpha, epsilon);
        } else {
            double beta = 1 / T;
            if (T < 1) { // cold regime
                double Iinv = ((beta / PI) * std::sin(PI / beta));
                double v = (targetAvgDegree * Iinv) * (PI / 2) * xiInv * xiInv;
                result = 2 * std::log(n / v);
            } else { // hot regime
                double v = targetAvgDegree * (1 - beta) * std::pow((PI / 2), beta) * xiInv * xiInv;
                result = 2 * std::log(n / v) / beta;
            }
        }
        return result;
    }

    static inline double effectiveAreaInCell(double minPhi, double maxPhi, double minR, double maxR,
                                             double alpha) {
        double deltaPhi = maxPhi - minPhi;
        assert(deltaPhi >= 0);
        assert(deltaPhi <= 2 * PI);
        double ringArea = radiusToHyperbolicArea(alpha * EuclideanRadiusToHyperbolic(maxR))
                          - radiusToHyperbolicArea(alpha * EuclideanRadiusToHyperbolic(minR));
        return ringArea * (deltaPhi / (2 * PI));
    }

    static double hyperbolicSpaceInEuclideanCircle(double r_c, double d_c, double R);

    static double maxRinSlice(double minPhi, double maxPhi, double phi_c, double r_c,
                              double euRadius);
};
} // namespace NetworKit

#endif // NETWORKIT_GEOMETRIC_HYPERBOLIC_SPACE_HPP_