root / custompackages / graphparser / src / bi_connected_components.cpp @ 437fd680
History  View  Annotate  Download (9.87 KB)
1 
//


2 
// Created by quynh on 1/9/16.

3 
//

4  
5 
#include "bi_connected_components.h" 
6 
using namespace std; 
7  
8 
/******************************

9 
* Public functions

10 
******************************/

11 
BiConnectedComponents::BiConnectedComponents(GraphManager &gm) : gm_(gm) { 
12 
cout << "BCC constructor \n";

13 
init(); 
14 
FindBiConnectedComponents(); 
15 
} 
16  
17 
void BiConnectedComponents::init() {

18 
// Set some variables

19 
num_of_vertices_ = boost::num_vertices(gm_.g_); 
20  
21 
component_vec_ = ComponentVec(boost::num_edges(gm_.g_), 0);

22 
component_map_ = ComponentMap(component_vec_.begin(), gm_.e_index_pmap()); 
23 
} 
24  
25 
/* GETTER */

26 
int const BiConnectedComponents::num_of_bcc() { 
27 
if (num_of_bcc_ == 1) { // calculate it 
28 
// +1 to counteract for the zeroindexing

29 
num_of_bcc_ = *std::max_element(component_vec_.begin(), component_vec_.end()) + 1;

30 
} 
31  
32 
return num_of_bcc_;

33 
} 
34  
35 
int const BiConnectedComponents::num_of_vertices() const { 
36 
return num_of_vertices_;

37 
} 
38  
39 
StringSet const& BiConnectedComponents::all_art_points_id() const { 
40 
return all_art_points_id_;

41 
} 
42  
43 
NameToDoubleMap const& BiConnectedComponents::bc_score() const { 
44 
return bc_score_;

45 
} 
46  
47 
/* SUBCOMPONENT */

48 
void BiConnectedComponents::FindBiConnectedComponents() {

49 
cout << "Running FindBiConnectedComponents" << endl;

50  
51 
boost::biconnected_components(gm_.g_, component_map_, 
52 
back_inserter(art_points_), 
53 
boost::vertex_index_map(gm_.v_index_pmap())); 
54  
55 
// Set some variables

56 
graphext::id_of_some_vertices(gm_.g_, art_points_, all_art_points_id_); 
57  
58 
// Process the result from boost::biconnected_components

59 
BCCs = Component_t(num_of_bcc()); 
60 
CreateSubComponents(); 
61  
62 
// Calculate Link Weight

63 
cout << "Calculate Link Weight\n";

64 
CalculateLinkWeight(); 
65  
66 
// Calculate Traffic Matrix

67 
cout << "Calculate Traffic Matrix\n";

68 
CalculateTrafficMatrix(); 
69  
70 
// Calculate Betweenness Centrality

71 
cout << "Calculate Betweenness Centrality\n";

72 
CalculateBetweennessCentrality(); 
73  
74 
// Print all the sub components

75 
print(); 
76 
} 
77  
78 
void BiConnectedComponents::CreateSubComponents() {

79 
// Generating subgraph for each subcomponent

80 
BGL_FORALL_EDGES(edge, gm_.g_, Graph) { 
81 
int comp_index = boost::get(component_map_, edge);

82 
Router r1 = gm_.g_[boost::source(edge, gm_.g_)]; 
83 
Router r2 = gm_.g_[boost::target(edge, gm_.g_)]; 
84 
Link l = gm_.g_[edge]; 
85 
BCCs[comp_index].AddEdge(r1, r2, l); 
86 
} 
87  
88 
// Finalizing each sub components

89 
for (int i = 0; i < num_of_bcc(); ++i) { 
90 
BCCs[i].FinalizeSubComponent(all_art_points_id_); 
91 
} 
92 
} 
93  
94 
/* LINK WEIGHT */

95 
void BiConnectedComponents::CalculateLinkWeight() {

96 
initialize_weight(); 
97 
initialize_queue(); 
98  
99 
while (!Q.empty()) {

100 
QueueElem elem = Q.front(); 
101 
Q.pop(); 
102 
int comp_index = elem.component_index;

103 
string vertex_id = elem.vertex_id;

104  
105 
if (elem.type == "component_vertex_pair") { 
106 
// cout << "component_vertex_pair: " << comp_index << "  " << vertex_id << endl;

107 
process_component_vertex_pair(comp_index, vertex_id); 
108 
} 
109 
else if (elem.type == "vertex_component_pair") { 
110 
// cout << "vertex_component_pair: " << comp_index << "  " << vertex_id << endl;

111 
process_vertex_component_pair(comp_index, vertex_id); 
112 
} 
113 
} 
114 
} 
115  
116 
/* TRAFFIC MATRIX */

117 
void BiConnectedComponents::CalculateTrafficMatrix() {

118 
for (int i = 0; i < num_of_bcc_; ++i) { 
119 
BCCs[i].CalculateTrafficMatrix(); 
120 
} 
121 
} 
122  
123 
/* BETWEENNESS CENTRALITY */

124 
void BiConnectedComponents::CalculateBetweennessCentrality() {

125 
cout << "BETWEENNESS CENTRALITY\n";

126  
127 
initialize_betweenness_centrality(); 
128  
129 
for (int i = 0; i < num_of_bcc_; ++i) { 
130 
cout << "BC for component " << i << endl;

131 
BCCs[i].CalculateBetweennessCentrality(); 
132 
} 
133  
134 
double score;

135 
// Sum the BC for each subcomponent

136 
for (int i = 0; i < num_of_bcc_; ++i) { 
137 
// For non articulation points

138 
for (string id: BCCs[i].non_art_points_id()) { 
139 
score = BCCs[i].get_betweenness_centrality(id); 
140 
cout << "id = " << id << ", score = " << score << endl; 
141 
bc_score_[id] = score; 
142 
} 
143  
144 
// For articulation points

145 
for (string id: BCCs[i].art_points_id()) { 
146 
score = BCCs[i].get_betweenness_centrality(id); 
147 
bc_sum_art_points_[id] += score; 
148 
} 
149 
} 
150  
151 
// Update the BC score for articulation points

152 
for (string id : all_art_points_id_) { 
153 
bc_score_[id] = bc_sum_art_points_[id]; 
154  
155 
// TODO: Jan 29, 2015: for now, I do not minus the bc_inter_

156 
// bc_score_[id] = bc_sum_art_points_[id]  bc_inter_[id];

157 
} 
158  
159 
cout << "DONE WITH BETWEENNESS CENTRALITY\n";

160 
} 
161  
162 
void BiConnectedComponents::initialize_betweenness_centrality() {

163 
// Initialize bc_inter_ to be 0

164 
for (string id: all_art_points_id_) { 
165 
bc_inter_[id] = 0;

166 
} 
167  
168 
StringSet all_vertices_id; 
169 
graphext::id_of_all_vertices(gm_.g_, all_vertices_id); 
170  
171 
// Initialize bc_sum_, bc_score_ to be 0

172 
for (string id: all_vertices_id) { 
173 
bc_sum_art_points_[id] = 0;

174 
bc_score_[id] = 0;

175 
} 
176 
} 
177  
178 
void BiConnectedComponents::calculate_bc_inter() {

179 
for (int i = 0; i < num_of_bcc_; ++i) { 
180 
for (string id : BCCs[i].art_points_id()) { 
181 
bc_inter_[id] += BCCs[i].get_weight_map(id) * BCCs[i].get_weight_reversed_map(id); 
182 
} 
183 
} 
184 
} 
185  
186 
/* HELPERS FOR OUTPUTTING RESULT */

187  
188 
void BiConnectedComponents::print() {

189 
for (int i = 0; i < num_of_bcc(); ++i) { 
190 
// cout << BCCs[i]; // Since I call another print() function inside, I cannot use cout

191 
BCCs[i].print(); 
192 
} 
193 
} 
194  
195 
std::ostream& operator<<(std::ostream& os, const BiConnectedComponents& rhs) { 
196 
cout << "MARK\n";

197 
cout << "\n\nBiConnected Components\n\n";

198 
cout << rhs.gm_; 
199  
200 
cout << "\nArticulation points:\n";

201 
outops::operator<<(cout, rhs.all_art_points_id());

202  
203 
cout << "\nBetweenness Centrality Score:\n";

204 
outops::operator<< <double>(cout, rhs.bc_score()); 
205 
return os;

206  
207 
// TODO: output the result of BCC

208 
// Test the biconnected components

209 
// Eiter ei, ei_end;

210 
// size_t i = 0;

211 
// for (boost::tie(ei, ei_end) = boost::edges(gm_.g_); ei != ei_end; ++ei) {

212 
// string source = gm_.g_[(*ei).m_source].id;

213 
// string target = gm_.g_[(*ei).m_target].id;

214 
// edges_size_type comp = component_vec_.at(i);

215 
// cout << source << " " << target << " " << comp << endl;

216 
// ++i;

217 
// }

218 
} 
219  
220 
/******************************

221 
* Private functions

222 
******************************/

223  
224 
/* LINK WEIGHT */

225 
void BiConnectedComponents::initialize_weight() {

226 
for (int i = 0; i < num_of_bcc_; ++i) { 
227 
BCCs[i].initialize_weight(); 
228 
} 
229 
} 
230  
231 
void BiConnectedComponents::initialize_queue() {

232 
for (int i = 0; i < num_of_bcc_; ++i) { 
233 
if (BCCs[i].art_points_id().size() == 1) { 
234 
string vertex_id = *(BCCs[i].art_points_id().begin());

235 
string type = "component_vertex_pair"; 
236 
QueueElem elem = { 
237 
.component_index = i, 
238 
.vertex_id = vertex_id, 
239 
.type = type, 
240 
}; 
241  
242 
Q.push(elem); 
243 
} 
244 
} 
245 
} 
246  
247 
void BiConnectedComponents::process_component_vertex_pair(int comp_index, string vertex_id) { 
248 
int size = BCCs[comp_index].num_of_vertices()  1; 
249 
for (string s : BCCs[comp_index].art_points_id()) { 
250 
if (s.compare(vertex_id) != 0) { 
251 
int weight = BCCs[comp_index].get_weight_map(s);

252 
if (weight != 1) { 
253 
size += num_of_vertices_  weight  1;

254 
} 
255 
} 
256 
} 
257 
int link_weight = size;

258 
BCCs[comp_index].update_weight_map(vertex_id, link_weight); 
259 
find_unknown_weight_wrt_art_point(vertex_id); 
260 
} 
261  
262 
void BiConnectedComponents::find_unknown_weight_wrt_art_point(string vertex_id) { 
263 
int count = 0; 
264 
int comp_index = 1; 
265 
for (int i = 0; i < num_of_bcc_; ++i) { 
266 
if (BCCs[i].vertex_exists(vertex_id)) {

267 
if (BCCs[i].get_weight_map(vertex_id) == 1) { 
268 
++count; 
269 
comp_index = i; 
270 
} 
271  
272 
if (count > 1) break; 
273 
} 
274 
} 
275  
276 
if (count == 1) { 
277 
// Add new element to QueueElem

278 
QueueElem elem = { 
279 
.component_index = comp_index, 
280 
.vertex_id = vertex_id, 
281 
.type = "vertex_component_pair"

282 
}; 
283  
284 
// cout << "Add vertex_component_pair: " << comp_index << "  " << vertex_id << endl;

285 
Q.push(elem); 
286 
} 
287 
} 
288  
289 
void BiConnectedComponents::process_vertex_component_pair(int comp_index, string vertex_id) { 
290 
int size = 0; 
291  
292 
for (int i = 0; i < num_of_bcc_; ++i) { 
293 
if (i != comp_index) {

294 
if (BCCs[i].vertex_exists(vertex_id)) {

295 
int weight = BCCs[i].get_weight_map(vertex_id);

296 
if (weight != 1) { 
297 
size += weight; 
298 
} 
299 
} 
300 
} 
301 
} 
302  
303 
int link_weight = num_of_vertices_  1  size; 
304 
BCCs[comp_index].update_weight_map(vertex_id, link_weight); 
305 
find_unknown_weight_wrt_component(comp_index); 
306 
} 
307  
308 
void BiConnectedComponents::find_unknown_weight_wrt_component(int comp_index) { 
309 
// The 'counting' solution is found here: http://stackoverflow.com/questions/5517615/countingnumberofsamevaluesinmap

310 
typedef NameToIntMap::value_type MapEntry;

311 
int count = std::count_if(

312 
BCCs[comp_index].weight_map().begin(), 
313 
BCCs[comp_index].weight_map().end(), 
314 
second_equal_to<MapEntry>(1));

315  
316 
if (count == 1) { 
317 
// Find the vertex id for the vertex with unknown link weight

318 
string vertex_id = BCCs[comp_index].first_vertex_id_with_unknown_weight();

319  
320 
QueueElem elem = { 
321 
.component_index = comp_index, 
322 
.vertex_id = vertex_id, 
323 
.type = "component_vertex_pair",

324 
}; 
325 
// cout << "Add component_vertex_pair: " << comp_index << "  " << vertex_id << endl;

326 
Q.push(elem); 
327 
} 
328 
} 