Accept multiple --ip arguments
[re6stnet.git] / simulation / realistic_dataset / graph.cpp
1 #include "main.h"
2
3 Graph::Graph(int size, int k, int maxPeers, mt19937& rng, Latency* latency, double minKillProba, double maxKillProba) :
4 generator(mt19937(rng())), 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 killProba = new double[size];
10 uniform_real_distribution<double> kill_distrib(minKillProba, maxKillProba);
11
12 for(int i=0; i<size; i++)
13 {
14 SaturateNode(i);
15 killProba[i] = kill_distrib(generator);
16 }
17 }
18
19 Graph::Graph(Graph& g) :
20 generator(mt19937(g.generator())), size(g.size), k(g.k), maxPeers(g.maxPeers), latency(g.latency),
21 distrib(g.distrib)
22 {
23 adjacency = new unordered_set<int>[size];
24 generated = new unordered_set<int>[size];
25
26 for(int i=0; i<size; i++)
27 {
28 adjacency[i] = unordered_set<int>(g.adjacency[i]);
29 generated[i] = unordered_set<int>(g.generated[i]);
30 }
31 }
32
33 void Graph::SaturateNode(int node)
34 {
35 while(generated[node].size() < k && AddEdge(node)) { }
36 }
37
38 bool Graph::AddEdge(int from)
39 {
40 int to;
41 for(int i=0; i<50; i++)
42 {
43 to = distrib(generator);
44
45 if( to != from
46 && latency->values[from][to] > 0
47 && adjacency[from].count(to) == 0
48 && adjacency[to].size() + k < maxPeers + generated[to].size())
49 {
50 generated[from].insert(to);
51 adjacency[from].insert(to);
52 adjacency[to].insert(from);
53 return true;
54 }
55 }
56
57 //cout << "Warning : a link could not be established from " << from << endl;
58 return false;
59 }
60
61 void Graph::RemoveEdge(int from, int to)
62 {
63 generated[from].erase(to);
64 adjacency[from].erase(to);
65 adjacency[to].erase(from);
66 }
67
68 void Graph::GetRoutesFrom(int from, int* nRoutes, int* prevs, int* distances)
69 {
70 // init vars
71 stack<int> order;
72
73 for(int i=0; i<size; i++)
74 {
75 distances[i] = -1;
76 nRoutes[i] = 1;
77 }
78 distances[from] = 0;
79
80 priority_queue<pair<int, int>> remainingNodes;
81 remainingNodes.push(pair<int, int>(-0, from));
82
83 // Get the order
84 while(!remainingNodes.empty())
85 {
86 pair<int, int> p = remainingNodes.top();
87 int node = p.second;
88 int d = -p.first;
89 remainingNodes.pop();
90
91 if(d == distances[node])
92 {
93 order.push(node);
94 for(int neighbor : adjacency[node])
95 {
96 int neighborDist = d + latency->values[neighbor][node];
97
98 if(distances[neighbor] == -1 || distances[neighbor] > neighborDist)
99 {
100 distances[neighbor] = neighborDist;
101 prevs[neighbor] = node;
102 remainingNodes.push(pair<int, int>(-neighborDist, neighbor));
103 }
104 }
105 }
106 }
107
108 // get the BC
109 while(!order.empty())
110 {
111 int node = order.top();
112 order.pop();
113 if(distances[node] != -1 && node != from)
114 nRoutes[prevs[node]] += nRoutes[node];
115 }
116 }
117
118 routesResult Graph::GetRouteResult(int node, int nRefresh, double* bc)
119 {
120 int nRoutes[size], prevs[size], distances[size];
121 GetRoutesFrom(node, nRoutes, prevs, distances);
122
123 if(bc != NULL)
124 for(int j=0; j<size; j++)
125 bc[j] += nRoutes[j];
126
127 routesResult r;
128 r.routesToDelete = 0;
129
130 for(int k=0; k<nRefresh; k++)
131 {
132 int mini = -1;
133 for(int j : generated[node])
134 if(mini == -1 || nRoutes[mini] > nRoutes[j])
135 mini = j;
136
137 if(mini != -1)
138 {
139 r.toDelete.push(mini);
140 r.routesToDelete += nRoutes[mini];
141 }
142 }
143
144 r.arity = adjacency[node].size();
145
146 r.avgDistance = 0;
147 r.unreachable = 0;
148
149 for(int j=0; j<size; j++)
150 {
151 if(distances[j] >= 0)
152 r.avgDistance += distances[j];
153 else
154 r.unreachable++;
155 }
156
157 r.avgDistance /= (double)(size - r.unreachable);
158
159 return r;
160 }
161
162 int Graph::UpdateLowRoutes(double& avgDistance, double& unreachable, double& nRoutesKilled,
163 double* arityDistrib, double* bcArity, int nRefresh, int round)
164 {
165 int nUpdated = 0;
166 routesResult results[size];
167 double bc[size];
168 for(int i=0; i<size; i++)
169 bc[i] = 0;
170
171 avgDistance = 0;
172 double avgDistanceWeight = 0;
173 unreachable = 0;
174 for(int i=0; i<=maxPeers; i++)
175 {
176 bcArity[i] = 0;
177 arityDistrib[i] = 0;
178 }
179
180 for(int i=0; i<size; i++)
181 results[i] = GetRouteResult(i, nRefresh, bc);
182
183 for(int i = 0; i<size; i++)
184 {
185 routesResult r = results[i];
186
187 while(!r.toDelete.empty())
188 {
189 RemoveEdge(i, r.toDelete.top());
190 r.toDelete.pop();
191 }
192 SaturateNode(i);
193 nUpdated++;
194
195 avgDistance += r.avgDistance*(size-r.unreachable);
196 avgDistanceWeight += size-r.unreachable;
197 unreachable += r.unreachable;
198 nRoutesKilled += r.routesToDelete;
199 arityDistrib[adjacency[i].size()]++;
200 bcArity[adjacency[i].size()] += bc[i] - 2*size + 1;
201 }
202
203 avgDistance /= avgDistanceWeight;
204
205 for(int i=0; i<=maxPeers; i++)
206 {
207 bcArity[i] = arityDistrib[i]>0 ? bcArity[i] / arityDistrib[i]:0;
208 arityDistrib[i] /= size;
209 }
210
211 return nUpdated;
212 }
213
214 pair<double, double> Graph::UpdateLowRoutesArity(int arityToUpdate)
215 {
216 // Update
217 routesResult results[size];
218 double nRoutesDeleted = 0;
219 double avgDist = 0;
220
221 for(int i=0; i<size; i++)
222 if(adjacency[i].size() == arityToUpdate || adjacency[i].size() < k)
223 results[i] = GetRouteResult(i, 1, NULL);
224
225 for(int i=0; i<size; i++)
226 if(results[i].toDelete.size() > 0)
227 {
228 routesResult r = results[i];
229 while(!r.toDelete.empty())
230 {
231 RemoveEdge(i, r.toDelete.top());
232 r.toDelete.pop();
233 }
234
235 nRoutesDeleted += r.routesToDelete;
236 SaturateNode(i);
237 }
238
239 // Get the distance
240 int distances[size];
241
242 for(int from=0; from<size; from++)
243 {
244 for(int i=0; i<size; i++)
245 distances[i] = -1;
246 distances[from] = 0;
247
248 priority_queue<pair<int, int>> remainingNodes;
249 remainingNodes.push(pair<int, int>(-0, from));
250
251 // Get the order
252 while(!remainingNodes.empty())
253 {
254 pair<int, int> p = remainingNodes.top();
255 int node = p.second;
256 int d = -p.first;
257 remainingNodes.pop();
258
259 if(d == distances[node])
260 for(int neighbor : adjacency[node])
261 {
262 int neighborDist = d + latency->values[neighbor][node];
263
264 if(distances[neighbor] == -1 || distances[neighbor] > neighborDist)
265 {
266 distances[neighbor] = neighborDist;
267 remainingNodes.push(pair<int, int>(-neighborDist, neighbor));
268 }
269 }
270 }
271
272 for(int i=0; i<size; i++)
273 avgDist += distances[i];
274 }
275
276 return pair<double, double>(avgDist/(size*size), nRoutesDeleted);
277 }
278
279 int Graph::CountUnreachableFrom(int node)
280 {
281 bool accessibility[size];
282 for(int i=0; i<size; i++)
283 accessibility[i] = false;
284 accessibility[node] = true;
285 int unreachable = size;
286
287 queue<int> toVisit;
288 toVisit.push(node);
289 while(!toVisit.empty())
290 {
291 int n = toVisit.front();
292 for(int i : adjacency[n])
293 {
294 if(!accessibility[i])
295 {
296 toVisit.push(i);
297 accessibility[i] = true;
298 }
299 }
300
301 unreachable--;
302 toVisit.pop();
303 }
304
305 return unreachable;
306 }
307
308 double Graph::GetUnAvalaibility()
309 {
310 double moy = 0;
311 for(int i=0; i<size; i++)
312 moy += CountUnreachableFrom(i);
313 return moy / (size*size);
314 }
315
316 void Graph::KillMachines(float proportion)
317 {
318 size = proportion*size;
319 distrib = uniform_int_distribution<int>(0, size - 1);
320
321 for(int i=0; i<size; i++)
322 {
323 vector<int> toBeRemoved;
324 for(int j : adjacency[i])
325 if(j >= size)
326 toBeRemoved.push_back(j);
327
328 for(int j : toBeRemoved)
329 {
330 generated[i].erase(j);
331 adjacency[i].erase(j);
332 }
333 }
334 }
335
336 void Graph::Reboot()
337 {
338 uniform_real_distribution<double> d(0.0, 1.0);
339 for(int i=0; i<size; i++)
340 if(d(generator) <= killProba[i])
341 {
342 stack<int> toSaturate;
343
344 unordered_set<int> generated_cpy(generated[i]);
345 for(int j : generated_cpy)
346 RemoveEdge(i, j);
347
348 unordered_set<int> adjacency_cpy(adjacency[i]);
349 for(int j : adjacency_cpy)
350 {
351 toSaturate.push(j);
352 RemoveEdge(j, i);
353 }
354
355 SaturateNode(i);
356
357 while(!toSaturate.empty())
358 {
359 SaturateNode(toSaturate.top());
360 toSaturate.pop();
361 }
362 }
363 }
364
365 void Graph::GetArity(int* arity)
366 {
367 for(int a=0; a<=maxPeers; a++)
368 arity[a] = 0;
369
370 for(int i=0; i<size; i++)
371 arity[adjacency[i].size()]++;
372 }
373
374 void Graph::GetArityLat(int arity[][10])
375 {
376 for(int i=0; i<10; i++)
377 for(int a=0; a<=maxPeers; a++)
378 arity[a][i] = 0;
379
380 for(int i=0; i<size; i++)
381 arity[adjacency[i].size()][max(min((int)(latency->avgLatencyToOthers[i] - 45000)/5000, 9), 0)]++;
382 }
383
384 void Graph::GetArityKill(int arity[][10])
385 {
386 for(int i=0; i<10; i++)
387 for(int a=0; a<=maxPeers; a++)
388 arity[a][i] = 0;
389
390 for(int i=0; i<size; i++)
391 {
392 arity[adjacency[i].size()][max(min((int)(killProba[i]*200.0), 9), 0)]++;
393 }
394 }
395
396 double Graph::GetAvgDistanceHop()
397 {
398 double avgDist = 0;
399 int distances[size];
400
401 for(int from=0; from<size; from++)
402 {
403 for(int i=0; i<size; i++)
404 distances[i] = -1;
405 distances[from] = 0;
406
407 queue<int> remainingNodes;
408 remainingNodes.push(from);
409
410 // Get the order
411 while(!remainingNodes.empty())
412 {
413 int node = remainingNodes.front();
414 remainingNodes.pop();
415 avgDist += distances[node];
416
417 for(int neighbor : adjacency[node])
418 if(distances[neighbor] == -1)
419 {
420 distances[neighbor] = distances[node] + latency->values[neighbor][node];
421 remainingNodes.push(neighbor);
422 }
423 }
424 }
425
426 return avgDist/(size*size);
427 }