Added a tool to simulate on real data
[re6stnet.git] / simulation / realistic_dataset / graph.cpp
1 #include "main.h"
2
3 Graph::Graph(int size, int k, int maxPeers, mt19937& generator, const Latency& latency) :
4 generator(generator), size(size), k(k), maxPeers(maxPeers), latency(latency),
5 distrib(uniform_int_distribution<int>(0, size-1))
6 {
7 adjacency = new unordered_set<int>[size];
8 generated = new unordered_set<int>[size];
9
10 for(int i=0; i<size; i++)
11 SaturateNode(i);
12 }
13
14 void Graph::SaturateNode(int node)
15 {
16 while(generated[node].size() < k && AddEdge(node)) { }
17 }
18
19 bool Graph::AddEdge(int from)
20 {
21 int to;
22 for(int i=0; i<50; i++)
23 {
24 to = distrib(generator);
25 if(latency.values[from][to] > 0
26 && to != from
27 && adjacency[from].count(to) == 0
28 && adjacency[to].size() + generated[to].size() <= maxPeers + k)
29 {
30 generated[from].insert(to);
31 adjacency[from].insert(to);
32 adjacency[to].insert(from);
33 return true;
34 }
35 }
36
37 //cout << "Warning : a link could not be established from " << from << endl;
38 return false;
39 }
40
41 void Graph::RemoveEdge(int from, int to)
42 {
43 generated[from].erase(to);
44 adjacency[from].erase(to);
45 adjacency[to].erase(from);
46 }
47
48 void Graph::GetRoutesFrom(int from, int* nRoutes, int* prevs, int* distances)
49 {
50 // init vars
51 stack<int> order;
52
53 for(int i=0; i<size; i++)
54 {
55 distances[i] = -1;
56 nRoutes[i] = 1;
57 }
58 distances[from] = 0;
59
60 priority_queue<pair<int, int>> remainingNodes;
61 remainingNodes.push(pair<int, int>(-0, from));
62
63 // Get the order
64 while(!remainingNodes.empty())
65 {
66 pair<int, int> p = remainingNodes.top();
67 int node = p.second;
68 int d = -p.first;
69 remainingNodes.pop();
70
71 if(d == distances[node])
72 {
73 order.push(node);
74 for(int neighbor : adjacency[node])
75 {
76 int neighborDist = d + latency.values[neighbor][node];
77
78 if(distances[neighbor] == -1 || distances[neighbor] > neighborDist)
79 {
80 distances[neighbor] = neighborDist;
81 prevs[neighbor] = node;
82 remainingNodes.push(pair<int, int>(-neighborDist, neighbor));
83 }
84 }
85 }
86 }
87
88 // get the BC
89 while(!order.empty())
90 {
91 int node = order.top();
92 order.pop();
93 if(distances[node] != -1)
94 nRoutes[prevs[node]] += nRoutes[node];
95 }
96 }
97
98
99 void Graph::UpdateLowRoutes(double& avgDistance, double unreachable, double* arityDistrib)
100 {
101 routesResult results[size];
102
103 for(int i=0; i<size; i++)
104 {
105 // Compute the routes
106 int nRoutes[size], prevs[size], distances[size];
107 GetRoutesFrom(i, nRoutes, prevs, distances);
108
109 // Get the values
110 routesResult r;
111 r.toDelete = -1;
112 for(int j : generated[i])
113 if(r.toDelete == -1 || nRoutes[r.toDelete] > nRoutes[j])
114 r.toDelete = j;
115
116 r.arity = adjacency[i].size();
117
118 r.avgDistance = 0;
119 r.unreachable = 0;
120 for(int j=0; j<size; j++)
121 {
122 if(distances[i] >= 0)
123 r.avgDistance += distances[j];
124 else
125 r.unreachable++;
126 }
127
128 r.avgDistance /= (double)(size - r.unreachable);
129
130 results[i] = r;
131 }
132
133 avgDistance = 0;
134 double avgDistanceWeight = 0;
135 unreachable = 0;
136 for(int i=0; i<=maxPeers; i++)
137 arityDistrib[i] = 0;
138
139 for(int i = 0; i<size; i++)
140 {
141 routesResult r = results[i];
142 if(r.toDelete >= 0)
143 RemoveEdge(i, r.toDelete);
144
145 SaturateNode(i);
146
147 avgDistance += r.avgDistance*(size-r.unreachable);
148 avgDistanceWeight += size-r.unreachable;
149 unreachable += r.unreachable;
150 arityDistrib[adjacency[i].size()]++;
151 }
152
153 avgDistance /= avgDistanceWeight;
154
155 for(int i=0; i<=maxPeers; i++)
156 arityDistrib[i] /= size;
157
158 }