Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

randomGeographicalThresholdGraph.h
Go to the documentation of this file.
1 
32 #pragma once
33 
34 #include <ogdf/basic/Graph.h>
35 
36 namespace ogdf {
37 
43 
47 
66 template<typename D>
67 void randomGeographicalThresholdGraph(Graph &G, Array<int> &weights, D &dist, double threshold, std::function<double(double)> h, int dimension = 2)
68 {
69  OGDF_ASSERT(dimension >= 1);
70  OGDF_ASSERT(threshold >= 0.0);
71 
72  G.clear();
73  Array<node> nodes(weights.size());
74 
75  // Randomly distribute nodes in a d-dimensional area
76  NodeArray<int> nodeWeights = NodeArray<int>(G);
77  NodeArray<Array<double>> cord(G, Array<double>(dimension));
78  std::minstd_rand rng(randomSeed());
79  for (int i = 0; i < weights.size(); i++) {
80  nodes[i] = G.newNode();
81  nodeWeights[nodes[i]] = weights[i];
82  for (int j = 0; j < dimension; j++){
83  cord[nodes[i]][j] = dist(rng);
84  }
85  }
86 
87  for (node v : nodes) {
88  for (node w = v->succ(); w; w = w->succ()) {
89  double distance = 0.0;
90  for (int i = 0; i < dimension; i++) {
91  distance += (cord[v][i] - cord[w][i]) * (cord[v][i] - cord[w][i]);
92  }
93  distance = sqrt(distance);
94 
95  if ((nodeWeights[v] + nodeWeights[w]) * h(distance) > threshold) {
96  G.newEdge(v, w);
97  }
98  }
99  }
100 }
101 
119 template<typename D>
120 void randomGeographicalThresholdGraph(Graph &G, Array<int> &weights, D &dist, double threshold, int alpha = 2, int dimension = 2)
121 {
122  randomGeographicalThresholdGraph<D>(G, weights, dist, threshold, [alpha](double d){ return 1/pow(d, alpha); }, dimension);
123 }
124 
126 
129 }
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
Graph.h
Includes declaration of graph class.
OGDF_ASSERT
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition: basic.h:41
ogdf::NodeArray< int >
ogdf::Array< int >
ogdf::Graph
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:495
ogdf::randomSeed
long unsigned int randomSeed()
Returns a random value suitable as initial seed for a random number engine.
ogdf::NodeElement::succ
node succ() const
Returns the successor in the list of all nodes.
Definition: Graph_d.h:218
ogdf::randomGeographicalThresholdGraph
void randomGeographicalThresholdGraph(Graph &G, Array< int > &weights, D &dist, double threshold, std::function< double(double)> h, int dimension=2)
Creates a random geometric graph where edges are created based on their distance and the weight of no...
Definition: randomGeographicalThresholdGraph.h:67
ogdf::Array::size
INDEX size() const
Returns the size (number of elements) of the array.
Definition: Array.h:286
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169