A few fixes in the simulator, preapring the simulation of major failure in the network
[re6stnet.git] / simulation / main.cpp
1 // To compile with -std=c++0x
2 // The GET_BC option might not be working
3 //#define GET_BC // Uncomment this line to get the betweeness centrality
4 #include "main.h"
5
6 int n = 1000; // the number of peer
7 int k = 10; // each peer try to make k connections with the others
8 int maxPeer = 25; // no more that 25 connections per peer
9 int runs = 100; // use this to run the simulation multiple times to get more accurate values
10 int betweenessDiv = 20; // to kown how to sample the BC. Max BC should be betweenessDiv*100
11
12 Graph::Graph(int size, int k, int maxPeers, mt19937 rng) :
13 distrib(uniform_int_distribution<int>(0, n-1)),
14 size(size)
15 {
16 adjacency = new vector<int>[size];
17 for(int i=0; i<size; i++)
18 {
19 set<int> alreadyConnected;
20 alreadyConnected.insert(i);
21
22 for(int j=0; j<k; j++)
23 {
24 int otherNode;
25
26 while(alreadyConnected.count(otherNode = distrib(rng)) == 1
27 || otherNode > i && adjacency[otherNode].size() > maxPeers-10
28 || adjacency[otherNode].size() > maxPeers)
29 { }
30 adjacency[i].push_back(otherNode);
31 adjacency[otherNode].push_back(i);
32 }
33 }
34 }
35
36 void Graph::GetDistancesFrom(int node, int* distance)
37 {
38 for(int j=0; j<size; j++)
39 distance[j] = -1;
40 distance[node] = 0;
41
42 queue<int> remainingNodes;
43 remainingNodes.push(node);
44
45 while(!remainingNodes.empty())
46 {
47 int node = remainingNodes.front();
48 remainingNodes.pop();
49
50 for(int neighbor : adjacency[node])
51 if(distance[neighbor] == -1)
52 {
53 distance[neighbor] = distance[node]+1;
54 remainingNodes.push(neighbor);
55 }
56 }
57 }
58
59 // kill the last proportion*size machines of the graph
60 void Graph::KillMachines(float proportion)
61 {
62 // TODO
63 }
64
65 int main()
66 {
67 mt19937 rng(time(NULL));
68
69 // Init the parameters
70 double array(arityDistrib, maxPeer+1);
71 double array(distanceDistrib, n);
72 double array(betweenessDistrib, 100);
73 int disconnected = 0;
74
75 for(int r=0; r<runs; r++)
76 {
77 cout << "\r \rRun " << r;
78 cout.flush();
79
80 Graph graph(n, k, maxPeer, rng);
81 double array(betweeness, n);
82
83 // Get the arity distribution
84 for(int i=0; i<n; i++)
85 arityDistrib[graph.adjacency[i].size()]++;
86
87 // Compute the shortest path
88 // TODO : optimise this
89 // switch to int64 ?
90 for(int i=0; i<graph.size; i++)
91 {
92 int distance[graph.size];
93 // if(i%10==0) cout << "Computing distances from node " << i << endl;
94 graph.GetDistancesFrom(i, distance);
95
96 // retrieve the distance
97 int maxDistance = -1;
98 for(int j=0; j<graph.size; j++)
99 if(distance[j] != -1)
100 {
101 maxDistance = max(distance[j], maxDistance);
102 distanceDistrib[distance[j]]++;
103 }
104 else
105 disconnected++;
106
107 #ifdef GET_BC
108 // Get the betweeness
109 double toBePushed[graph.size];
110 for(int j=0; j<n; j++)
111 toBePushed[j] = 1;
112
113 // TODO : change this into a true sort ?
114 // run accross the nodes in the right order
115 // we don't need to sort them since we will only run across them a few times
116 for(int d=maxDistance; d>=0; d--)
117 for(int j=0; j<graph.size; j++)
118 if(distance[j] == d)
119 {
120 int nMin, min = -1;
121 for(int neighbor : graph.adjacency[j])
122 {
123 if(distance[neighbor] < min || min == -1)
124 {
125 min = distance[neighbor];
126 nMin = 1;
127 }
128 else if(distance[neighbor] == min)
129 nMin++;
130 }
131
132 double singleScore = toBePushed[j]/nMin;
133 for(int neighbor : graph.adjacency[j])
134 if(distance[neighbor] == min)
135 toBePushed[neighbor] += singleScore;
136
137 betweeness[j] += toBePushed[j] - 1;
138 }
139 #endif
140 }
141 #ifdef GET_BC
142 // Get the betweeness distribution
143 for(int i=0; i<n; i++)
144 betweenessDistrib[min((int)betweeness[i]/betweenessDiv, 99)]++;
145 #endif
146 }
147 cout << "\r \r";
148
149 // Display the parameters we have mesured
150 cout << "Arity :" << endl;
151 for(int i=0; i<=maxPeer; i++)
152 if(arityDistrib[i] != 0)
153 {
154 arityDistrib[i] /= (double)(n*runs);
155 cout << i << " : " << arityDistrib[i] << endl;
156 }
157
158 cout << "Distance :" << endl;
159 double nLinks = n*(n-1)*runs;
160 for(int i=0; i<n; i++)
161 if(distanceDistrib[i] != 0)
162 {
163 distanceDistrib[i] /= nLinks - disconnected;
164 cout << i << " : " << distanceDistrib[i] << endl;
165 }
166
167 cout << "Probability that a node is not reachable : "
168 << disconnected/nLinks
169 << " (" << disconnected << " total)" << endl;
170
171 #ifdef GET_BC
172 cout << "Betweeness :" << endl;
173 double nNodes = n*runs;
174 for(int i=0; i<100; i++)
175 if(betweenessDistrib[i] != 0)
176 cout << betweenessDiv*i << " -> " << betweenessDiv*(i+1) << " : "
177 << betweenessDistrib[i]/nNodes << endl;
178 #endif
179
180 cout << endl;
181 return 0;
182 }
183
184