Remove trailing whitespaces
[re6stnet.git] / simulation / graph.cpp
1 #include "main.h"
2 #include <cmath>
3 #include <map>
4 #include <queue>
5
6 Graph::Graph(int size, int k, int maxPeers, mt19937& rng) :
7 distrib(uniform_int_distribution<int>(0, size-1)),
8 size(size), generator(rng)
9 {
10 adjacency = new vector<int>[size];
11 for(int i=0; i<size; i++)
12 {
13 unordered_set<int> alreadyConnected;
14 alreadyConnected.insert(i);
15
16 for(int j=0; j<k; j++)
17 {
18 int otherNode;
19
20 while(alreadyConnected.count(otherNode = distrib(rng)) == 1
21 || otherNode > i && adjacency[otherNode].size() > maxPeers-10
22 || adjacency[otherNode].size() > maxPeers)
23 { }
24 adjacency[i].push_back(otherNode);
25 adjacency[otherNode].push_back(i);
26 }
27 }
28 }
29
30 void Graph::GetDistancesFrom(int node, int* distance)
31 {
32 for(int j=0; j<size; j++)
33 distance[j] = -1;
34 distance[node] = 0;
35
36 queue<int> remainingNodes;
37 remainingNodes.push(node);
38
39 while(!remainingNodes.empty())
40 {
41 int node = remainingNodes.front();
42 remainingNodes.pop();
43
44 for(int neighbor : adjacency[node])
45 if(distance[neighbor] == -1)
46 {
47 distance[neighbor] = distance[node]+1;
48 remainingNodes.push(neighbor);
49 }
50 }
51 }
52
53 int Graph::CountUnreachableFrom(int node)
54 {
55 bool accessibility[size];
56 for(int i=0; i<size; i++)
57 accessibility[i] = false;
58 accessibility[node] = true;
59 int unAccessible = size;
60
61 queue<int> toVisit;
62 toVisit.push(node);
63 while(!toVisit.empty())
64 {
65 int n = toVisit.front();
66 for(int i : adjacency[n])
67 {
68 if(!accessibility[i])
69 {
70 toVisit.push(i);
71 accessibility[i] = true;
72 }
73 }
74
75 unAccessible--;
76 toVisit.pop();
77 }
78
79 return unAccessible;
80 }
81
82 // kill the last proportion*size machines of the graph
83 void Graph::KillMachines(float proportion)
84 {
85 size = proportion*size;
86 for(int i=0; i<size; i++)
87 {
88 auto it=adjacency[i].begin();
89 while(it!=adjacency[i].end())
90 {
91 if(*it >= size)
92 it = adjacency[i].erase(it);
93 else
94 it++;
95 }
96 }
97 }
98
99 int Graph::GetMinCut()
100 {
101 int nIter = log(size);
102 int minCut = -1;
103 for(int i=0; i<nIter; i++)
104 {
105 MinCutGraph graph = MinCutGraph(adjacency, size);
106 int minCutCandidate = GetMinCut(graph);
107 if(minCut == -1 || minCut > minCutCandidate)
108 minCut = minCutCandidate;
109 }
110
111 return minCut;
112 }
113
114 int Graph::GetMinCut(MinCutGraph& copy1)
115 {
116 int n=copy1.nodes.size();
117
118 if(n==2)
119 return copy1.edges.size();
120
121 MinCutGraph copy2(copy1);
122
123 int nMerge = min(n-2.0, n/1.414);
124 copy1.Merge(nMerge, generator);
125 copy2.Merge(nMerge, generator);
126
127 return min(GetMinCut(copy1), GetMinCut(copy2));
128 }
129
130 MinCutGraph::MinCutGraph(vector<int>* adjacency, int n)
131 {
132 nodes.resize(n);
133 int nextEdgeId = 0;
134
135 for(int i=0; i<n; i++)
136 for(int j : adjacency[i])
137 if(j > i)
138 {
139 nodes[i].v.insert(nextEdgeId);
140 nodes[j].v.insert(nextEdgeId);
141 edges.push_back(nullable<pair<int, int>>(pair<int, int>(i, j)));
142 nextEdgeId++;
143 }
144 }
145
146 void MinCutGraph::Merge(int nMerge, mt19937& rng)
147 {
148 uniform_int_distribution<int> distrib(0, edges.size()-1);
149
150 while(nMerge > 0)
151 {
152 // Choose an edge
153 int eId = distrib(rng);
154 if(edges[eId].null)
155 continue;
156
157 int n1 = edges[eId].v.first;
158 int n2 = edges[eId].v.second;
159
160 // anilate n2
161 nodes[n2].null = true;
162
163 // redirect all edges from n2
164 for(int i : nodes[n2].v)
165 {
166 if(edges[i].v.first == n1 || edges[i].v.second == n1)
167 {
168 nodes[n1].v.erase(i);
169 edges[i].null = true;
170 }
171
172 else
173 {
174 nodes[n1].v.insert(i);
175
176 if(edges[i].v.first == n2)
177 edges[i].v.first = n1;
178 else
179 edges[i].v.second = n1;
180 }
181 }
182
183 nMerge--;
184 }
185
186 RenumNodes();
187 RenumEdges();
188 }
189
190 void MinCutGraph::Check()
191 {
192 cout << "CHECKING ... "; cout.flush();
193 for(int i=0; i<edges.size(); i++)
194 {
195 if(!edges[i].null)
196 {
197 auto e = edges[i].v;
198
199 if(e.first >= nodes.size())
200 cout << "Bad first" << endl; cout.flush();
201 if(e.second >= nodes.size())
202 cout << "Bad second" << endl; cout.flush();
203 if(nodes[e.first].v.count(i) == 0)
204 cout << "Bad first node" << endl; cout.flush();
205 if(nodes[e.second].v.count(i) == 0)
206 cout << "Bad second node" << endl; cout.flush();
207 }
208 }
209
210 for(int i=0; i<nodes.size(); i++)
211 if(!nodes[i].null)
212 for(int e : nodes[i].v)
213 if(edges[e].v.first != i && edges[e].v.second != i)
214 cout << "Bad edge" << endl; cout.flush();
215
216 cout << "DONE" << endl; cout.flush();
217 }
218
219 void MinCutGraph::RenumEdges()
220 {
221 int nextId = 0;
222 for(int i=0; i<edges.size(); i++)
223 if(!edges[i].null)
224 {
225 edges[nextId] = edges[i];
226 nodes[edges[nextId].v.first].v.erase(i);
227 nodes[edges[nextId].v.first].v.insert(nextId);
228 nodes[edges[nextId].v.second].v.erase(i);
229 nodes[edges[nextId].v.second].v.insert(nextId);
230 nextId++;
231 }
232 edges.resize(nextId);
233 }
234
235 void MinCutGraph::RenumNodes()
236 {
237 int nextId = 0;
238 for(int i=0; i<nodes.size(); i++)
239 if(!nodes[i].null)
240 {
241 nodes[nextId] = nodes[i];
242 for(int j : nodes[nextId].v)
243 {
244 if(edges[j].v.first == i)
245 edges[j].v.first = nextId;
246 else
247 edges[j].v.second = nextId;
248 }
249 nextId++;
250 }
251 nodes.resize(nextId);
252 }
253