Merge branch 'master' into cygwin
[re6stnet.git] / simulation / graph.cpp
1 #include "main.h"
2 #include <cmath>
3 #include <map>
4 #include <queue>
5 #include <stack>
6
7 void erase(vector<int>& v, int value)
8 {
9 for(int i=0;;i++)
10 if(v[i] == value)
11 {
12 v[i] = v.back();
13 v.pop_back();
14 break;
15 }
16 }
17
18 Graph::Graph(int size, int k, int maxPeers, mt19937& rng) :
19 distrib(uniform_int_distribution<int>(0, size-1)),
20 size(size), generator(rng), k(k), maxPeers(maxPeers)
21 {
22 adjacency = new vector<int>[size];
23 generated = new vector<int>[size];
24
25 for(int i=0; i<size; i++)
26 {
27 int otherNode;
28 unordered_set<int> alreadyConnected;
29 alreadyConnected.insert(i);
30
31 for(int j=0; j<k; j++)
32 {
33 while(alreadyConnected.count(otherNode = distrib(generator)) >= 1
34 || otherNode > i && adjacency[otherNode].size() > maxPeers-k
35 || adjacency[otherNode].size() > maxPeers)
36 { }
37 adjacency[i].push_back(otherNode);
38 generated[i].push_back(otherNode);
39 adjacency[otherNode].push_back(i);
40 }
41 }
42 }
43
44 int Graph::AddEdge(int from, unordered_set<int>& alreadyConnected)
45 {
46 int otherNode;
47 while(alreadyConnected.count(otherNode = distrib(generator)) >= 1
48 || (adjacency[otherNode].size() > maxPeers ))
49 { }
50 adjacency[from].push_back(otherNode);
51 generated[from].push_back(otherNode);
52 adjacency[otherNode].push_back(from);
53 return otherNode;
54 }
55
56 int Graph::RemoveEdge(int from, int to)
57 {
58 erase(generated[from], to);
59 erase(adjacency[from], to);
60 erase(adjacency[to], from);
61 }
62
63 void Graph::GetDistancesFrom(int node, int* distance)
64 {
65 for(int j=0; j<size; j++)
66 distance[j] = -1;
67 distance[node] = 0;
68
69 queue<int> remainingNodes;
70 remainingNodes.push(node);
71
72 while(!remainingNodes.empty())
73 {
74 int node = remainingNodes.front();
75 remainingNodes.pop();
76
77 for(int neighbor : adjacency[node])
78 if(distance[neighbor] == -1)
79 {
80 distance[neighbor] = distance[node]+1;
81 remainingNodes.push(neighbor);
82 }
83 }
84 }
85
86 void Graph::GetRoutesFrom(int node, int* distance, float* routesCount)
87 {
88
89 unordered_set<int> prevs[size];
90
91 for(int i=0; i<size; i++)
92 {
93 distance[i] = -1;
94 routesCount[i] = 1;
95 }
96 distance[node] = 0;
97
98 queue<int> remainingNodes;
99 remainingNodes.push(node);
100
101 stack<int> order;
102
103 // Get the order
104 while(!remainingNodes.empty())
105 {
106 int node = remainingNodes.front();
107 int d = distance[node];
108 remainingNodes.pop();
109 order.push(node);
110
111 for(int neighbor : adjacency[node])
112 if(distance[neighbor] == -1)
113 {
114 distance[neighbor] = d+1;
115 prevs[neighbor].insert(node);
116 remainingNodes.push(neighbor);
117 }
118 else if(distance[neighbor] == d+1)
119 prevs[neighbor].insert(node);
120 }
121
122 // get the BC
123 while(!order.empty())
124 {
125 int node = order.top();
126 order.pop();
127 float w = routesCount[node];
128 for(int i : prevs[node])
129 routesCount[i] += w;
130 }
131
132 }
133
134 int Graph::CountUnreachableFrom(int node)
135 {
136 bool accessibility[size];
137 for(int i=0; i<size; i++)
138 accessibility[i] = false;
139 accessibility[node] = true;
140 int unAccessible = size;
141
142 queue<int> toVisit;
143 toVisit.push(node);
144 while(!toVisit.empty())
145 {
146 int n = toVisit.front();
147 for(int i : adjacency[n])
148 {
149 if(!accessibility[i])
150 {
151 toVisit.push(i);
152 accessibility[i] = true;
153 }
154 }
155
156 unAccessible--;
157 toVisit.pop();
158 }
159
160 return unAccessible;
161 }
162
163 // kill the last proportion*size machines of the graph
164 void Graph::KillMachines(float proportion)
165 {
166 size = proportion*size;
167 for(int i=0; i<size; i++)
168 {
169 auto it=adjacency[i].begin();
170 while(it!=adjacency[i].end())
171 {
172 if(*it >= size)
173 it = adjacency[i].erase(it);
174 else
175 it++;
176 }
177 }
178 }
179
180 int Graph::GetMinCut()
181 {
182 int nIter = log(size);
183 int minCut = -1;
184 for(int i=0; i<nIter; i++)
185 {
186 MinCutGraph graph = MinCutGraph(adjacency, size);
187 int minCutCandidate = GetMinCut(graph);
188 if(minCut == -1 || minCut > minCutCandidate)
189 minCut = minCutCandidate;
190 }
191
192 return minCut;
193 }
194
195 int Graph::GetMinCut(MinCutGraph& copy1)
196 {
197 int n=copy1.nodes.size();
198
199 if(n==2)
200 return copy1.edges.size();
201
202 MinCutGraph copy2(copy1);
203
204 int nMerge = min(n-2.0, n/1.414);
205 copy1.Merge(nMerge, generator);
206 copy2.Merge(nMerge, generator);
207
208 return min(GetMinCut(copy1), GetMinCut(copy2));
209 }
210
211 MinCutGraph::MinCutGraph(vector<int>* adjacency, int n)
212 {
213 nodes.resize(n);
214 int nextEdgeId = 0;
215
216 for(int i=0; i<n; i++)
217 for(int j : adjacency[i])
218 if(j > i)
219 {
220 nodes[i].v.insert(nextEdgeId);
221 nodes[j].v.insert(nextEdgeId);
222 edges.push_back(nullable<pair<int, int>>(pair<int, int>(i, j)));
223 nextEdgeId++;
224 }
225 }
226
227 void MinCutGraph::Merge(int nMerge, mt19937& rng)
228 {
229 uniform_int_distribution<int> distrib(0, edges.size()-1);
230
231 while(nMerge > 0)
232 {
233 // Choose an edge
234 int eId = distrib(rng);
235 if(edges[eId].null)
236 continue;
237
238 int n1 = edges[eId].v.first;
239 int n2 = edges[eId].v.second;
240
241 // anilate n2
242 nodes[n2].null = true;
243
244 // redirect all edges from n2
245 for(int i : nodes[n2].v)
246 {
247 if(edges[i].v.first == n1 || edges[i].v.second == n1)
248 {
249 nodes[n1].v.erase(i);
250 edges[i].null = true;
251 }
252
253 else
254 {
255 nodes[n1].v.insert(i);
256
257 if(edges[i].v.first == n2)
258 edges[i].v.first = n1;
259 else
260 edges[i].v.second = n1;
261 }
262 }
263
264 nMerge--;
265 }
266
267 RenumNodes();
268 RenumEdges();
269 }
270
271 void MinCutGraph::Check()
272 {
273 cout << "CHECKING ... "; cout.flush();
274 for(int i=0; i<edges.size(); i++)
275 {
276 if(!edges[i].null)
277 {
278 auto e = edges[i].v;
279
280 if(e.first >= nodes.size())
281 cout << "Bad first" << endl; cout.flush();
282 if(e.second >= nodes.size())
283 cout << "Bad second" << endl; cout.flush();
284 if(nodes[e.first].v.count(i) == 0)
285 cout << "Bad first node" << endl; cout.flush();
286 if(nodes[e.second].v.count(i) == 0)
287 cout << "Bad second node" << endl; cout.flush();
288 }
289 }
290
291 for(int i=0; i<nodes.size(); i++)
292 if(!nodes[i].null)
293 for(int e : nodes[i].v)
294 if(edges[e].v.first != i && edges[e].v.second != i)
295 cout << "Bad edge" << endl; cout.flush();
296
297 cout << "DONE" << endl; cout.flush();
298 }
299
300 void MinCutGraph::RenumEdges()
301 {
302 int nextId = 0;
303 for(int i=0; i<edges.size(); i++)
304 if(!edges[i].null)
305 {
306 edges[nextId] = edges[i];
307 nodes[edges[nextId].v.first].v.erase(i);
308 nodes[edges[nextId].v.first].v.insert(nextId);
309 nodes[edges[nextId].v.second].v.erase(i);
310 nodes[edges[nextId].v.second].v.insert(nextId);
311 nextId++;
312 }
313 edges.resize(nextId);
314 }
315
316 void MinCutGraph::RenumNodes()
317 {
318 int nextId = 0;
319 for(int i=0; i<nodes.size(); i++)
320 if(!nodes[i].null)
321 {
322 nodes[nextId] = nodes[i];
323 for(int j : nodes[nextId].v)
324 {
325 if(edges[j].v.first == i)
326 edges[j].v.first = nextId;
327 else
328 edges[j].v.second = nextId;
329 }
330 nextId++;
331 }
332 nodes.resize(nextId);
333 }
334