root / custompackages / graphparser / src / bi_connected_components.cpp @ 33e5ad95
History  View  Annotate  Download (16.2 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 
init(); 
13 
} 
14  
15 
void BiConnectedComponents::init() {

16 
// Set some variables

17 
num_of_vertices_ = boost::num_vertices(gm_.g_); 
18  
19 
component_vec_ = ComponentVec(boost::num_edges(gm_.g_), 1);

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

24 
int const BiConnectedComponents::num_of_bcc() { 
25 
return num_of_bcc_;

26 
} 
27  
28 
int const BiConnectedComponents::num_of_vertices() const { 
29 
return num_of_vertices_;

30 
} 
31  
32 
StringSet const& BiConnectedComponents::all_art_points_id() const { 
33 
return all_art_points_id_;

34 
} 
35  
36 
NameToDoubleMap const& BiConnectedComponents::bc_score() const { 
37 
return bc_score_;

38 
} 
39  
40 
NameToDoubleMap const& BiConnectedComponents::bc_relative_score() const { 
41 
return bc_relative_score_;

42 
} 
43  
44 
// AUTO RUN

45 
void BiConnectedComponents::run() {

46 
/* Auto run all the necessary functions

47 
*/

48 
cout << "Running FindBiConnectedComponents" << endl;

49 
FindBiConnectedComponents(); 
50  
51 
// Calculate Link Weight + Link Weight Reversed

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

53 
CalculateLinkWeight(); 
54 
CalculateLinkWeightReversed(); 
55 
verify_link_weight(); 
56  
57 
// Calculate Traffic Matrix

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

59 
CalculateTrafficMatrix(); 
60  
61 
// Calculate Betweenness Centrality Heuristic

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

63 
CalculateBetweennessCentralityHeuristic(); 
64 
} 
65  
66 
// SUBCOMPONENT

67 
void BiConnectedComponents::FindBiConnectedComponents() {

68 
boost::biconnected_components(gm_.g_, component_map_, 
69 
back_inserter(art_points_), 
70 
boost::vertex_index_map(gm_.v_index_pmap())); 
71  
72 
// Set some necessary variables

73 
graphext::id_of_some_vertices(gm_.g_, art_points_, all_art_points_id_); 
74 
reset_num_of_bcc(); 
75 
cout << "Total # of components: " << num_of_bcc_ << endl;

76  
77 
// Process the result from boost::biconnected_components

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

79 
CreateSubComponents(); 
80 
} 
81  
82 
// LINK WEIGHT

83 
void BiConnectedComponents::CalculateLinkWeight() {

84 
initialize_weight(); 
85 
initialize_queue(); 
86  
87 
while (!Q.empty()) {

88 
QueueElem elem = Q.front(); 
89 
Q.pop(); 
90 
int comp_index = elem.component_index;

91 
string vertex_id = elem.vertex_id;

92  
93 
if (elem.type == "component_vertex_pair") { 
94 
// cout << "component_vertex_pair: " << comp_index << "  " << vertex_id << endl;

95 
process_component_vertex_pair(comp_index, vertex_id); 
96 
} 
97 
else if (elem.type == "vertex_component_pair") { 
98 
// cout << "vertex_component_pair: " << comp_index << "  " << vertex_id << endl;

99 
process_vertex_component_pair(comp_index, vertex_id); 
100 
} 
101 
} 
102 
} 
103  
104 
void BiConnectedComponents::CalculateLinkWeightReversed() {

105 
for (int i = 0; i < num_of_bcc_; ++i) { 
106 
BCCs[i].calculate_weight_reversed(num_of_vertices_); 
107 
} 
108 
} 
109  
110 
// TRAFFIC MATRIX

111 
void BiConnectedComponents::CalculateTrafficMatrix() {

112 
for (int i = 0; i < num_of_bcc_; ++i) { 
113 
BCCs[i].CalculateTrafficMatrix(); 
114 
} 
115 
} 
116  
117 
// BETWEENNESS CENTRALITY HEURISTIC

118 
void BiConnectedComponents::CalculateBetweennessCentralityHeuristic() {

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

120  
121 
initialize_betweenness_centrality_heuristic(); 
122 
calculate_bc_inter(); 
123  
124 
for (int i = 0; i < num_of_bcc_; ++i) { 
125 
BCCs[i].CalculateBetweennessCentralityHeuristic(); 
126 
} 
127  
128 
double score;

129 
for (int i = 0; i < num_of_bcc_; ++i) { 
130 
// For all points

131 
for (string id: BCCs[i].all_vertices_id()) { 
132 
score = BCCs[i].get_betweenness_centrality(id); 
133 
bc_score_[id] += score; 
134 
} 
135 
} 
136  
137 
// Update the BC score for articulation points

138 
for (string id : all_art_points_id_) { 
139 
bc_score_[id] = bc_inter_[id]; 
140 
} 
141  
142 
finalize_betweenness_centrality_heuristic(); 
143  
144 
cout << "DONE WITH BETWEENNESS CENTRALITY\n";

145 
} 
146  
147 
// BETWEENNESS CENTRALITY  NORMAL CALCULATION

148 
void BiConnectedComponents::CalculateBetweennessCentrality(bool endpoints_inclusion) { 
149 
initialize_betweenness_centrality(); 
150  
151 
if (gm_.weighted_graph()) { // calculate BC for weighted graph 
152 
cout << "======= BCC  BC for weighted graph ======\n";

153  
154 
typedef map<Edge, double> EdgeWeightStdMap; 
155 
typedef boost::associative_property_map<EdgeIndexStdMap> EdgeWeightPMap;

156 
EdgeIndexStdMap edge_weight_std_map; 
157 
EdgeWeightPMap edge_weight_pmap = EdgeWeightPMap(edge_weight_std_map); 
158  
159 
BGL_FORALL_EDGES(edge, gm_.g_, Graph) { 
160 
edge_weight_std_map[edge] = gm_.g_[edge].cost; 
161 
} 
162 
boost::brandes_betweenness_centrality_endpoints_inclusion(gm_.g_, 
163 
endpoints_inclusion, 
164 
boost::centrality_map( 
165 
v_centrality_pmap_).vertex_index_map( 
166 
gm_.v_index_pmap()).weight_map( 
167 
edge_weight_pmap) 
168 
); 
169 
} 
170 
else { // for unweighted graph 
171 
boost::brandes_betweenness_centrality_endpoints_inclusion(gm_.g_, 
172 
endpoints_inclusion, 
173 
boost::centrality_map( 
174 
v_centrality_pmap_).vertex_index_map( 
175 
gm_.v_index_pmap()) 
176 
); 
177 
} 
178  
179 
boost::relative_betweenness_centrality(gm_.g_, v_centrality_pmap_); 
180 
} 
181  
182 
// HELPERS FOR OUTPUTTING RESULT

183 
void BiConnectedComponents::print_all_sub_components() {

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

186 
BCCs[i].print(); 
187 
} 
188 
} 
189  
190 
void BiConnectedComponents::print_biconnected_components() {

191 
cout << "\nArticulation points:\n";

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

193  
194 
cout << "All Sub Components:\n\n";

195 
for (int i = 0; i < num_of_bcc_; ++i) { 
196 
cout << " " << i << endl;

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

198 
} 
199 
} 
200  
201 
void BiConnectedComponents::print_betweenness_centrality() {

202 
BGL_FORALL_VERTICES(v, gm_.g_, Graph) { 
203 
double bc_score = boost::get(v_centrality_pmap_, v);

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

205 
} 
206 
} 
207  
208 
void BiConnectedComponents::print_betweenness_centrality_heuristic() {

209 
outops::operator<< <double>(cout, bc_relative_score_); 
210 
} 
211  
212 
void BiConnectedComponents::write_all_betweenness_centrality(string filepath) { 
213 
/* Write the heuristic and the normal version of betweenness centrality

214 
1st column: brandes_betweenness_centrality

215 
2nd column: heuristic_betweenness_centrality

216 
*/

217  
218 
vector<pair<string, double> > mapcopy(bc_relative_score_.begin(), bc_relative_score_.end()); 
219 
std::sort(mapcopy.begin(), mapcopy.end(), less_second<string, double>()); 
220  
221 
ofstream outFile(filepath.c_str()); 
222  
223 
Viter vi, ve; 
224 
size_t i = 0;

225 
if (outFile.is_open()) {

226 
for(auto id_bc_score_pair : mapcopy) { 
227 
string id = id_bc_score_pair.first;

228 
double heuristic_bc_score = id_bc_score_pair.second;

229  
230 
int index = gm_.get_index_from_id(id);

231 
double bc_score = v_centrality_vec_.at(index);

232  
233 
outFile << id << "\t" << setprecision(4) << fixed << bc_score << "\t" << heuristic_bc_score << endl; 
234 
} 
235 
// for (boost::tie(vi, ve) = boost::vertices(gm_.g_); vi != ve; ++vi) {

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

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

238 
// ++i;

239 
// }

240 
} 
241 
outFile.close(); 
242 
cout << "Finish writing brandes and heurisic BC score to file " << filepath << endl;

243 
} 
244  
245 
void BiConnectedComponents::print() {

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

247 
cout << gm_; 
248  
249 
print_biconnected_components(); 
250  
251 
cout << "\nHeuristic Betweenness Centrality Score:\n";

252 
outops::operator<< <double>(cout, bc_score_); 
253  
254 
cout << "\nHeuristic Betweenness Centrality Relative Score:\n";

255 
outops::operator<< <double>(cout, bc_relative_score_); 
256  
257 
cout << "\nNormal Betweenness Centrality Score:\n";

258 
print_betweenness_centrality(); 
259 
} 
260  
261 
std::ostream& operator<<(std::ostream& os, const BiConnectedComponents& rhs) { 
262 
cout << "\n\nBiConnected Components\n\n";

263 
cout << rhs.gm_; 
264  
265 
cout << "\nArticulation points:\n";

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

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

269 
outops::operator<< <double>(cout, rhs.bc_score()); 
270  
271 
cout << "\nHeuristic Betweenness Centrality Relative Score:\n";

272 
outops::operator<< <double>(cout, rhs.bc_relative_score()); 
273  
274 
return os;

275 
} 
276  
277 
/******************************

278 
* Private functions

279 
******************************/

280 
// SUBCOMPONENT

281 
void BiConnectedComponents::reset_num_of_bcc() {

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

283 
} 
284  
285 
void BiConnectedComponents::CreateSubComponents() {

286 
for (int i = 0; i < num_of_bcc_; ++i) { 
287 
BCCs.push_back(SubComponent(gm_.weighted_graph())); 
288 
} 
289  
290 
// Generating subgraph for each subcomponent

291 
BGL_FORALL_EDGES(edge, gm_.g_, Graph) { 
292 
Vertex source = boost::source(edge, gm_.g_); 
293 
Vertex target = boost::target(edge, gm_.g_); 
294  
295 
int comp_index = boost::get(component_map_, edge);

296 
cout << comp_index << " ";

297  
298 
if (comp_index == 1) { 
299 
cout << "ERROR: edge ";

300 
graphext::print_edge(gm_.g_, edge); 
301 
cout << "not belonging to subcomponent\n";

302 
} 
303 
else {

304 
Router r1 = gm_.g_[source]; 
305 
Router r2 = gm_.g_[target]; 
306 
Link l = gm_.g_[edge]; 
307 
if (r1 != r2) { // Do not add selfloop edge 
308 
BCCs[comp_index].AddEdge(r1, r2, l); 
309 
} 
310 
} 
311 
} 
312  
313 
// Finalizing each sub components

314 
for (int i = 0; i < num_of_bcc_; ++i) { 
315 
BCCs[i].FinalizeSubComponent(all_art_points_id_); 
316 
} 
317 
} 
318  
319 
// LINK WEIGHT

320 
void BiConnectedComponents::initialize_weight() {

321 
for (int i = 0; i < num_of_bcc_; ++i) { 
322 
BCCs[i].initialize_weight(); 
323 
} 
324 
} 
325  
326 
void BiConnectedComponents::initialize_queue() {

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

330 
string type = "component_vertex_pair"; 
331 
QueueElem elem = { 
332 
.component_index = i, 
333 
.vertex_id = vertex_id, 
334 
.type = type, 
335 
}; 
336 
// cout << "adding component_vertex_pair (" << i << " " << vertex_id << ")\n";

337 
Q.push(elem); 
338 
} 
339 
} 
340 
} 
341  
342 
void BiConnectedComponents::process_component_vertex_pair(int comp_index, string vertex_id) { 
343 
int size = BCCs[comp_index].num_of_vertices()  1; 
344 
for (string s : BCCs[comp_index].art_points_id()) { 
345 
if (s.compare(vertex_id) != 0) { 
346 
int weight = BCCs[comp_index].get_weight_map(s);

347 
if (weight != 1) { 
348 
size += num_of_vertices_  weight  1;

349 
} 
350 
} 
351 
} 
352 
int link_weight = size;

353  
354 
int old_link_weight = BCCs[comp_index].get_weight_map(vertex_id);

355 
if (old_link_weight != 1) { 
356 
if (link_weight != old_link_weight) {

357 
cout << "ERROR in Link Weight for comp " << comp_index << "  vertex " << vertex_id << old_link_weight << "  " << link_weight << endl; 
358 
} 
359 
} 
360  
361 
BCCs[comp_index].update_weight_map(vertex_id, link_weight); 
362 
// cout << " update weight for comp " << comp_index << "  vertex " << vertex_id << " = " << link_weight << endl;

363 
find_unknown_weight_wrt_art_point(vertex_id); 
364 
} 
365  
366 
void BiConnectedComponents::find_unknown_weight_wrt_art_point(string vertex_id) { 
367 
int count = 0; 
368 
int comp_index = 1; 
369 
// cout << "find_unknown_weight_wrt_art_point " << vertex_id << "\n";

370  
371 
for (int i = 0; i < num_of_bcc_; ++i) { 
372 
if (BCCs[i].vertex_exists(vertex_id)) {

373 
if (BCCs[i].get_weight_map(vertex_id) == 1) { 
374 
// cout << " comp_index = " << i << endl;

375 
++count; 
376 
comp_index = i; 
377 
} 
378  
379 
if (count > 1) break; 
380 
} 
381 
} 
382  
383 
if (count == 1) { 
384 
// Add new element to QueueElem

385 
QueueElem elem = { 
386 
.component_index = comp_index, 
387 
.vertex_id = vertex_id, 
388 
.type = "vertex_component_pair"

389 
}; 
390  
391 
// cout << " Add vertex_component_pair: " << comp_index << "  " << vertex_id << endl;

392 
Q.push(elem); 
393 
} 
394 
} 
395  
396 
void BiConnectedComponents::process_vertex_component_pair(int comp_index, string vertex_id) { 
397 
int size = 0; 
398  
399 
for (int i = 0; i < num_of_bcc_; ++i) { 
400 
if (i != comp_index) {

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

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

403 
if (weight != 1) { 
404 
size += weight; 
405 
} 
406 
} 
407 
} 
408 
} 
409  
410 
int link_weight = num_of_vertices_  1  size; 
411  
412 
int old_link_weight = BCCs[comp_index].get_weight_map(vertex_id);

413 
if (old_link_weight != 1) { 
414 
if (link_weight != old_link_weight) {

415 
cout << "ERROR in Link Weight for comp " << comp_index << "  vertex " << vertex_id << old_link_weight << "  " << link_weight << endl; 
416 
} 
417 
} 
418  
419 
BCCs[comp_index].update_weight_map(vertex_id, link_weight); 
420 
// cout << " update weight for vertex_component pair: " << comp_index << "  " << vertex_id << " = " << link_weight << endl;

421 
find_unknown_weight_wrt_component(comp_index); 
422 
} 
423  
424 
void BiConnectedComponents::find_unknown_weight_wrt_component(int comp_index) { 
425 
// The 'counting' solution is found here: http://stackoverflow.com/questions/5517615/countingnumberofsamevaluesinmap

426 
typedef NameToIntMap::value_type MapEntry;

427 
int count = std::count_if(

428 
BCCs[comp_index].weight_map().begin(), 
429 
BCCs[comp_index].weight_map().end(), 
430 
second_equal_to<MapEntry>(1));

431  
432 
if (count == 1) { 
433 
// Find the vertex id for the vertex with unknown link weight

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

435  
436 
QueueElem elem = { 
437 
.component_index = comp_index, 
438 
.vertex_id = vertex_id, 
439 
.type = "component_vertex_pair",

440 
}; 
441 
// cout << "Add component_vertex_pair: " << comp_index << "  " << vertex_id << endl;

442 
Q.push(elem); 
443 
} 
444 
} 
445  
446 
bool BiConnectedComponents::verify_link_weight() {

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

448 
bool result = true; 
449  
450 
for (int i = 0; i < num_of_bcc_; ++i) { 
451 
for (string id : BCCs[i].art_points_id()) { 
452 
if (BCCs[i].get_weight_map(id) == 1) { 
453 
cout << "ERROR Link Weight for vertex " << id << " in component " << i << " = " << 1 << endl; 
454 
result = false;

455 
} 
456 
} 
457 
} 
458 
} 
459  
460 
// BETWEENNESS CENTRALITY  HEURISTIC

461 
void BiConnectedComponents::initialize_betweenness_centrality_heuristic() {

462 
// Initialize bc_inter_ to be 0

463 
for (string id: all_art_points_id_) { 
464 
bc_inter_[id] = 0;

465 
} 
466  
467 
StringSet all_vertices_id; 
468 
graphext::id_of_all_vertices(gm_.g_, all_vertices_id); 
469  
470 
// Initialize bc_sum_, bc_score_ to be 0

471 
for (string id: all_vertices_id) { 
472 
bc_sum_art_points_[id] = 0;

473 
bc_score_[id] = 0;

474 
} 
475 
} 
476  
477 
void BiConnectedComponents::calculate_bc_inter() {

478 
for (int i = 0; i < num_of_bcc_; ++i) { 
479 
for (string id : BCCs[i].art_points_id()) { 
480 
bc_inter_[id] += BCCs[i].get_weight_map(id) * BCCs[i].get_weight_reversed_map(id); 
481 
} 
482 
} 
483  
484 
if (!gm_.weighted_graph()) {

485 
for (string id : all_art_points_id_) { 
486 
bc_inter_[id] /= 2;

487 
} 
488 
} 
489 
} 
490  
491 
void BiConnectedComponents::finalize_betweenness_centrality_heuristic() {

492 
// Divide the bc_score_ by some factor

493 
int n = num_of_vertices();

494 
double factor = 2.0 / (n*n  3*n + 2); 
495 
NameToDoubleMap::iterator iter; 
496 
for (iter = bc_score_.begin(); iter != bc_score_.end(); ++iter) {

497 
double old_value = iter>second;

498 
bc_relative_score_[iter>first] = old_value * factor; 
499 
} 
500 
} 
501  
502 
// BETWEENNESS CENTRALITY

503 
void BiConnectedComponents::initialize_betweenness_centrality() {

504 
v_centrality_vec_ = CentralityVec(num_of_vertices()); 
505 
v_centrality_pmap_ = CentralityPMap(v_centrality_vec_.begin(), gm_.v_index_pmap()); 
506 
} 