Revision 162e1bda custompackages/graphparser/src/bi_connected_components.cpp
custompackages/graphparser/src/bi_connected_components.cpp  

18  18 
// Set some variables 
19  19 
num_of_vertices_ = boost::num_vertices(gm_.g_); 
20  20  
21 
component_vec_ = ComponentVec(boost::num_edges(gm_.g_), 0);


21 
component_vec_ = ComponentVec(boost::num_edges(gm_.g_), 1);


22  22 
component_map_ = ComponentMap(component_vec_.begin(), gm_.e_index_pmap()); 
23  23 
} 
24  24  
...  ...  
44  44 
return bc_score_; 
45  45 
} 
46  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())); 

47 
NameToDoubleMap const& BiConnectedComponents::bc_relative_score() const { 

48 
return bc_relative_score_; 

49 
} 

54  50  
55 
// Set some variables 

56 
graphext::id_of_some_vertices(gm_.g_, art_points_, all_art_points_id_); 

51 
// AUTO RUN 

52 
void BiConnectedComponents::run() { 

53 
/* Auto run all the necessary functions 

54 
*/ 

55 
FindBiConnectedComponents(); 

57  56  
58 
// Process the result from boost::biconnected_components 

59 
BCCs = Component_t(num_of_bcc()); 

60 
CreateSubComponents(); 

57 
cout << "All Sub Components:\n\n"; 

58 
for (int i = 0; i < num_of_bcc_; ++i) { 

59 
cout << " " << i << endl; 

60 
outops::operator<<(cout, BCCs[i].all_vertices_id()); 

61 
} 

61  62  
62 
// Calculate Link Weight 

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

63 
// Calculate Link Weight + Link Weight Reversed


64 
cout << "Calculate Link Weight + Link Weight Reversed\n";


64  65 
CalculateLinkWeight(); 
66 
CalculateLinkWeightReversed(); 

67 
verify_link_weight(); 

65  68  
66  69 
// Calculate Traffic Matrix 
67  70 
cout << "Calculate Traffic Matrix\n"; 
68  71 
CalculateTrafficMatrix(); 
69  72  
73 
// Calculate Betweenness Centrality Heuristic 

74 
cout << "Calculate Betweenness Centrality Heuristic\n"; 

75 
CalculateBetweennessCentralityHeuristic(); 

76  
70  77 
// Calculate Betweenness Centrality 
71  78 
cout << "Calculate Betweenness Centrality\n"; 
72  79 
CalculateBetweennessCentrality(); 
73  
74 
// Print all the sub components 

75 
print(); 

76  80 
} 
77  81  
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 
} 

82 
// SUBCOMPONENT 

83 
void BiConnectedComponents::FindBiConnectedComponents() { 

84 
cout << "Running FindBiConnectedComponents" << endl; 

87  85  
88 
// Finalizing each sub components 

89 
for (int i = 0; i < num_of_bcc(); ++i) { 

90 
BCCs[i].FinalizeSubComponent(all_art_points_id_); 

91 
} 

86 
boost::biconnected_components(gm_.g_, component_map_, 

87 
back_inserter(art_points_), 

88 
boost::vertex_index_map(gm_.v_index_pmap())); 

89  
90 
// Set some variables 

91 
graphext::id_of_some_vertices(gm_.g_, art_points_, all_art_points_id_); 

92  
93 
cout << "\nArticulation points:\n"; 

94 
outops::operator<<(cout, all_art_points_id_); 

95  
96 
// Process the result from boost::biconnected_components 

97 
cout << "Create Sub Components\n"; 

98 
BCCs = Component_t(num_of_bcc()); 

99 
CreateSubComponents(); 

92  100 
} 
93  101  
94 
/* LINK WEIGHT */


102 
// LINK WEIGHT


95  103 
void BiConnectedComponents::CalculateLinkWeight() { 
96  104 
initialize_weight(); 
97  105 
initialize_queue(); 
...  ...  
113  121 
} 
114  122 
} 
115  123  
116 
/* TRAFFIC MATRIX */ 

124 
void BiConnectedComponents::CalculateLinkWeightReversed() { 

125 
for (int i = 0; i < num_of_bcc_; ++i) { 

126 
BCCs[i].calculate_weight_reversed(num_of_vertices_); 

127 
} 

128 
} 

129  
130 
// TRAFFIC MATRIX 

117  131 
void BiConnectedComponents::CalculateTrafficMatrix() { 
118  132 
for (int i = 0; i < num_of_bcc_; ++i) { 
119  133 
BCCs[i].CalculateTrafficMatrix(); 
120  134 
} 
121  135 
} 
122  136  
123 
/* BETWEENNESS CENTRALITY */


124 
void BiConnectedComponents::CalculateBetweennessCentrality() { 

125 
cout << "BETWEENNESS CENTRALITY\n"; 

137 
// BETWEENNESS CENTRALITY HEURISTIC


138 
void BiConnectedComponents::CalculateBetweennessCentralityHeuristic() {


139 
cout << "BETWEENNESS CENTRALITY HEURISTIC\n";


126  140  
127 
initialize_betweenness_centrality(); 

141 
initialize_betweenness_centrality_heuristic(); 

142 
calculate_bc_inter(); 

128  143  
129  144 
for (int i = 0; i < num_of_bcc_; ++i) { 
130  145 
cout << "BC for component " << i << endl; 
131 
BCCs[i].CalculateBetweennessCentrality(); 

146 
BCCs[i].CalculateBetweennessCentralityHeuristic();


132  147 
} 
133  148  
134  149 
double score; 
135 
// Sum the BC for each subcomponent 

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


138 
for (string id: BCCs[i].non_art_points_id()) {


151 
// For all points


152 
for (string id: BCCs[i].all_vertices_id()) {


139  153 
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; 

154 
cout << "XXX score from component << " << i << ", id " << id << " = " << score << endl; 

155 
bc_score_[id] += score; 

148  156 
} 
149  157 
} 
150  158  
151 
// Update the BC score for articulation points 

159 
// // Sum the BC for each subcomponent 

160 
// for (int i = 0; i < num_of_bcc_; ++i) { 

161 
// // For non articulation points 

162 
// for (string id: BCCs[i].non_art_points_id()) { 

163 
// score = BCCs[i].get_betweenness_centrality(id); 

164 
// bc_score_[id] = score; 

165 
// } 

166  
167 
// // For articulation points 

168 
// for (string id: BCCs[i].art_points_id()) { 

169 
// score = BCCs[i].get_betweenness_centrality(id); 

170 
// bc_sum_art_points_[id] += score; 

171 
// } 

172 
// } 

173  
174 
// // Update the BC score for articulation points 

152  175 
for (string id : all_art_points_id_) { 
153 
bc_score_[id] = bc_sum_art_points_[id]; 

176 
// bc_score_[id] = bc_sum_art_points_[id];


154  177  
155  178 
// 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]; 

179 
cout << bc_score_[id] << " > "; 

180 
bc_score_[id] = bc_inter_[id]; 

181 
cout << bc_score_[id] << endl; 

157  182 
} 
158  183  
184 
finalize_betweenness_centrality_heuristic(); 

185  
159  186 
cout << "DONE WITH BETWEENNESS CENTRALITY\n"; 
160  187 
} 
161  188  
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 
} 

189 
// BETWEENNESS CENTRALITY  NORMAL CALCULATION 

190 
void BiConnectedComponents::CalculateBetweennessCentrality() { 

191 
initialize_betweenness_centrality(); 

167  192  
168 
StringSet all_vertices_id; 

169 
graphext::id_of_all_vertices(gm_.g_, all_vertices_id); 

193 
boost::brandes_betweenness_centrality(gm_.g_, 

194 
boost::centrality_map( 

195 
v_centrality_pmap_).vertex_index_map( 

196 
gm_.v_index_pmap()) 

197 
); 

170  198  
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; 

199 
boost::relative_betweenness_centrality(gm_.g_, v_centrality_pmap_); 

200 
} 

201  
202  
203 
// HELPERS FOR OUTPUTTING RESULT 

204 
void BiConnectedComponents::print_all_sub_components() { 

205 
for (int i = 0; i < num_of_bcc(); ++i) { 

206 
// cout << BCCs[i]; // Since I call another print() function inside, I cannot use cout 

207 
BCCs[i].print(); 

175  208 
} 
176  209 
} 
177  210  
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 
} 

211 
void BiConnectedComponents::print_betweenness_centrality() { 

212 
BGL_FORALL_VERTICES(v, gm_.g_, Graph) { 

213 
double bc_score = boost::get(v_centrality_pmap_, v); 

214 
cout << gm_.g_[v].id << ": " << bc_score << endl; 

183  215 
} 
184  216 
} 
185  217  
186 
/* HELPERS FOR OUTPUTTING RESULT */ 

218 
void BiConnectedComponents::print_betweenness_centrality_heuristic() { 

219 
outops::operator<< <double>(cout, bc_relative_score_); 

220 
} 

221  
222 
void BiConnectedComponents::write_all_betweenness_centrality(string filepath) { 

223 
/* Write the heuristic and the normal version of betweenness centrality 

224 
1st column: brandes_betweenness_centrality 

225 
2nd column: heuristic_betweenness_centrality 

226 
*/ 

187  227  
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(); 

228 
vector<pair<string, double> > mapcopy(bc_relative_score_.begin(), bc_relative_score_.end()); 

229 
std::sort(mapcopy.begin(), mapcopy.end(), less_second<string, double>()); 

230  
231 
ofstream outFile(filepath.c_str()); 

232  
233 
Viter vi, ve; 

234 
size_t i = 0; 

235 
if (outFile.is_open()) { 

236 
for(auto id_bc_score_pair : mapcopy) { 

237 
string id = id_bc_score_pair.first; 

238 
double heuristic_bc_score = id_bc_score_pair.second; 

239  
240 
int index = gm_.get_index_from_id(id); 

241 
double bc_score = v_centrality_vec_.at(index); 

242  
243 
outFile << id << "\t" << bc_score << "\t" << heuristic_bc_score << endl; 

244 
} 

245 
// for (boost::tie(vi, ve) = boost::vertices(gm_.g_); vi != ve; ++vi) { 

246 
// string id = gm_.g_[*vi].id; 

247 
// outFile << id << "\t" << bc_relative_score_[id] << "\t" << v_centrality_vec_.at(i) << endl; 

248 
// ++i; 

249 
// } 

192  250 
} 
251 
outFile.close(); 

252 
cout << "Finish writing brandes and heurisic BC score to file " << filepath << endl; 

253 
} 

254  
255 
void BiConnectedComponents::print() { 

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

257 
cout << gm_; 

258  
259 
cout << "\nArticulation points:\n"; 

260 
outops::operator<<(cout, all_art_points_id_); 

261  
262 
cout << "\nHeuristic Betweenness Centrality Score:\n"; 

263 
outops::operator<< <double>(cout, bc_score_); 

264  
265 
cout << "\nHeuristic Betweenness Centrality Relative Score:\n"; 

266 
outops::operator<< <double>(cout, bc_relative_score_); 

267  
268 
cout << "\nNormal Betweenness Centrality Score:\n"; 

269 
print_betweenness_centrality(); 

270  
271 
cout << "Special debugging case\n"; 

272 
BCCs[71].print(); 

193  273 
} 
194  274  
195  275 
std::ostream& operator<<(std::ostream& os, const BiConnectedComponents& rhs) { 
196 
cout << "MARK\n"; 

197  276 
cout << "\n\nBiConnected Components\n\n"; 
198  277 
cout << rhs.gm_; 
199  278  
200  279 
cout << "\nArticulation points:\n"; 
201  280 
outops::operator<<(cout, rhs.all_art_points_id()); 
202  281  
203 
cout << "\nBetweenness Centrality Score:\n"; 

282 
cout << "\nHeuristic Betweenness Centrality Score:\n";


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

206  284  
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 
// } 

285 
cout << "\nHeuristic Betweenness Centrality Relative Score:\n"; 

286 
outops::operator<< <double>(cout, rhs.bc_relative_score()); 

287  
288 
return os; 

218  289 
} 
219  290  
220  291 
/****************************** 
221  292 
* Private functions 
222  293 
******************************/ 
294 
// SUBCOMPONENT 

295 
void BiConnectedComponents::CreateSubComponents() { 

296 
// Generating subgraph for each subcomponent 

297 
BGL_FORALL_EDGES(edge, gm_.g_, Graph) { 

298 
Vertex source = boost::source(edge, gm_.g_); 

299 
Vertex target = boost::target(edge, gm_.g_); 

300  
301 
int comp_index = boost::get(component_map_, edge); 

302 
cout << comp_index << endl; 

303 
if (comp_index == 1) { 

304 
cout << "ERROR: edge "; 

305 
graphext::print_edge(gm_.g_, edge); 

306 
cout << "not belonging to subcomponent\n"; 

307 
} 

308 
else { 

309 
Router r1 = gm_.g_[source]; 

310 
Router r2 = gm_.g_[target]; 

311 
Link l = gm_.g_[edge]; 

312 
BCCs[comp_index].AddEdge(r1, r2, l); 

313 
} 

314 
} 

315  
316 
// Finalizing each sub components 

317 
for (int i = 0; i < num_of_bcc(); ++i) { 

318 
BCCs[i].FinalizeSubComponent(all_art_points_id_); 

319 
} 

320 
} 

223  321  
224 
/* LINK WEIGHT */


322 
// LINK WEIGHT


225  323 
void BiConnectedComponents::initialize_weight() { 
226  324 
for (int i = 0; i < num_of_bcc_; ++i) { 
227  325 
BCCs[i].initialize_weight(); 
...  ...  
230  328  
231  329 
void BiConnectedComponents::initialize_queue() { 
232  330 
for (int i = 0; i < num_of_bcc_; ++i) { 
331 
if (BCCs[i].vertex_exists("43")) { 

332 
cout << "### 43 ###\n"; 

333 
outops::operator<<(cout, BCCs[i].all_vertices_id()); 

334 
} 

233  335 
if (BCCs[i].art_points_id().size() == 1) { 
234  336 
string vertex_id = *(BCCs[i].art_points_id().begin()); 
235  337 
string type = "component_vertex_pair"; 
...  ...  
238  340 
.vertex_id = vertex_id, 
239  341 
.type = type, 
240  342 
}; 
241  
343 
cout << "adding component_vertex_pair (" << i << " " << vertex_id << ")\n"; 

242  344 
Q.push(elem); 
243  345 
} 
244  346 
} 
...  ...  
255  357 
} 
256  358 
} 
257  359 
int link_weight = size; 
360  
361 
int old_link_weight = BCCs[comp_index].get_weight_map(vertex_id); 

362 
if (old_link_weight != 1) { 

363 
if (link_weight != old_link_weight) { 

364 
cout << "ERROR in Link Weight for vertex " << vertex_id << old_link_weight << "  " << link_weight << endl; 

365 
} 

366 
} 

367  
258  368 
BCCs[comp_index].update_weight_map(vertex_id, link_weight); 
259  369 
find_unknown_weight_wrt_art_point(vertex_id); 
260  370 
} 
...  ...  
262  372 
void BiConnectedComponents::find_unknown_weight_wrt_art_point(string vertex_id) { 
263  373 
int count = 0; 
264  374 
int comp_index = 1; 
375 
cout << "find_unknown_weight_wrt_art_point " << vertex_id << "\n"; 

376  
265  377 
for (int i = 0; i < num_of_bcc_; ++i) { 
266  378 
if (BCCs[i].vertex_exists(vertex_id)) { 
267  379 
if (BCCs[i].get_weight_map(vertex_id) == 1) { 
380 
cout << " comp_index = " << i << endl; 

268  381 
++count; 
269  382 
comp_index = i; 
270  383 
} 
...  ...  
281  394 
.type = "vertex_component_pair" 
282  395 
}; 
283  396  
284 
// cout << "Add vertex_component_pair: " << comp_index << "  " << vertex_id << endl;


397 
cout << " Add vertex_component_pair: " << comp_index << "  " << vertex_id << endl;


285  398 
Q.push(elem); 
286  399 
} 
287  400 
} 
...  ...  
301  414 
} 
302  415  
303  416 
int link_weight = num_of_vertices_  1  size; 
417  
418 
int old_link_weight = BCCs[comp_index].get_weight_map(vertex_id); 

419 
if (old_link_weight != 1) { 

420 
if (link_weight != old_link_weight) { 

421 
cout << "ERROR in Link Weight for vertex " << vertex_id << old_link_weight << "  " << link_weight << endl; 

422 
} 

423 
} 

424  
304  425 
BCCs[comp_index].update_weight_map(vertex_id, link_weight); 
305  426 
find_unknown_weight_wrt_component(comp_index); 
306  427 
} 
...  ...  
322  443 
.vertex_id = vertex_id, 
323  444 
.type = "component_vertex_pair", 
324  445 
}; 
325 
// cout << "Add component_vertex_pair: " << comp_index << "  " << vertex_id << endl;


446 
cout << "Add component_vertex_pair: " << comp_index << "  " << vertex_id << endl; 

326  447 
Q.push(elem); 
327  448 
} 
449 
} 

450  
451 
bool BiConnectedComponents::verify_link_weight() { 

452 
// Returns True if there is no negative value in Link Weight 

453 
bool result = true; 

454  
455 
for (int i = 0; i < num_of_bcc_; ++i) { 

456 
for (string id : BCCs[i].art_points_id()) { 

457 
if (BCCs[i].get_weight_map(id) == 1) { 

458 
cout << "ERROR Link Weight for vertex " << id << " = " << 1 << endl; 

459 
result = false; 

460 
} 

461 
} 

462 
} 

463 
} 

464  
465 
// BETWEENNESS CENTRALITY  HEURISTIC 

466 
void BiConnectedComponents::initialize_betweenness_centrality_heuristic() { 

467 
// Initialize bc_inter_ to be 0 

468 
for (string id: all_art_points_id_) { 

469 
bc_inter_[id] = 0; 

470 
} 

471  
472 
StringSet all_vertices_id; 

473 
graphext::id_of_all_vertices(gm_.g_, all_vertices_id); 

474  
475 
// Initialize bc_sum_, bc_score_ to be 0 

476 
for (string id: all_vertices_id) { 

477 
bc_sum_art_points_[id] = 0; 

478 
bc_score_[id] = 0; 

479 
} 

480 
} 

481  
482 
void BiConnectedComponents::calculate_bc_inter() { 

483 
for (int i = 0; i < num_of_bcc_; ++i) { 

484 
for (string id : BCCs[i].art_points_id()) { 

485 
bc_inter_[id] += BCCs[i].get_weight_map(id) * BCCs[i].get_weight_reversed_map(id); 

486 
} 

487 
} 

488 
} 

489  
490 
void BiConnectedComponents::finalize_betweenness_centrality_heuristic() { 

491 
// Divide the bc_score_ by some factor 

492 
int n = num_of_vertices(); 

493 
double factor = 2.0 / (n*n  3*n + 2); 

494 
NameToDoubleMap::iterator iter; 

495 
for (iter = bc_score_.begin(); iter != bc_score_.end(); ++iter) { 

496 
double old_value = iter>second; 

497 
bc_relative_score_[iter>first] = old_value * factor; 

498 
} 

499 
} 

500  
501 
// BETWEENNESS CENTRALITY 

502 
void BiConnectedComponents::initialize_betweenness_centrality() { 

503 
v_centrality_vec_ = CentralityVec(num_of_vertices()); 

504 
v_centrality_pmap_ = CentralityPMap(v_centrality_vec_.begin(), gm_.v_index_pmap()); 

328  505 
} 
Also available in: Unified diff