randomGeographicalThresholdGraph.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
 
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);
}
 
 
}