randomGeographicalThresholdGraph.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Array.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/basic.h>
 
#include <cmath>
#include <functional>
#include <random>
 
namespace ogdf {
 
 
 
template<typename D>
void randomGeographicalThresholdGraph(Graph& G, Array<int>& weights, D& dist, double threshold,
        std::function<double(double)> h, int dimension = 2) {
    OGDF_ASSERT(dimension >= 1);
    OGDF_ASSERT(threshold >= 0.0);
 
    G.clear();
    Array<node> nodes(weights.size());
 
    // Randomly distribute nodes in a d-dimensional area
    NodeArray<int> nodeWeights = NodeArray<int>(G);
    NodeArray<Array<double>> cord(G, Array<double>(dimension));
    std::minstd_rand rng(randomSeed());
    for (int i = 0; i < weights.size(); i++) {
        nodes[i] = G.newNode();
        nodeWeights[nodes[i]] = weights[i];
        for (int j = 0; j < dimension; j++) {
            cord[nodes[i]][j] = dist(rng);
        }
    }
 
    for (node v : nodes) {
        for (node w = v->succ(); w; w = w->succ()) {
            double distance = 0.0;
            for (int i = 0; i < dimension; i++) {
                distance += (cord[v][i] - cord[w][i]) * (cord[v][i] - cord[w][i]);
            }
            distance = sqrt(distance);
 
            if ((nodeWeights[v] + nodeWeights[w]) * h(distance) > threshold) {
                G.newEdge(v, w);
            }
        }
    }
}
 
template<typename D>
void randomGeographicalThresholdGraph(Graph& G, Array<int>& weights, D& dist, double threshold,
        int alpha = 2, int dimension = 2) {
    randomGeographicalThresholdGraph<D>(
            G, weights, dist, threshold, [alpha](double d) { return 1 / pow(d, alpha); }, dimension);
}
 
 
}