Revision efed924d custompackages/graphparser/src/bi_connected_components.cpp
custompackages/graphparser/src/bi_connected_components.cpp  

10  10 
findBiConnectedComponents(); 
11  11 
} 
12  12  
13  
13  14 
void BiConnectedComponents::init() { 
14  15 
size_t i = 0; // for indexing in the loop 
15  16  
...  ...  
49  50 
outops::operator<<(cout, art_point_ids); 
50  51  
51  52 
// Process the result from boost::biconnected_components 
52 
// BCCs = Component_t(num_bcc());


53 
// verticesInBCC();


53 
BCCs = Component_t(num_bcc()); 

54 
verticesInBCC(); 

54  55 
// testVerticesInBCC(); 
55 
// processArtPoints();


56 
processArtPoints(); 

56  57 
// testProcessArtPoints(); 
57  58 
// _test_set_difference(); 
58 
// createSubComponents();


59 
createSubComponents(); 

59  60 
} 
60  61  
61  62 
void BiConnectedComponents::createSubComponents() { 
62 
vector<Graph> subGraphVec(num_bcc()); 

63 
vector< map<string, Vertex> > nameVertexMapVec(num_bcc()); 

63 
// Generating articulation points for each subcomponent 

64 
for (int i = 0; i < num_bcc(); ++i) { 

65 
StringSet art_point_ids; 

66 
VertexVec art_points_vec; 

67 
art_points_vec = get_art_points_for_component(i); 

68 
graphext::id_of_vertices(g, art_points_vec, art_point_ids); 

64  69  
65 
// Build subgraphs 

66 
int comp_index; 

67 
BGL_FORALL_EDGES(edge, g, Graph) { 

68 
comp_index = boost::get(component_map, edge); 

69 
string source = g[edge.m_source].name; 

70 
string target = g[edge.m_target].name; 

71 
double cost = g[edge].cost; 

72 
addLinkToGraph(source, target, cost, subGraphVec[comp_index], nameVertexMapVec[comp_index]); 

70 
outops::operator<<(cout, art_point_ids); 

71 
BCCs[i].set_art_points(art_point_ids); 

73  72 
} 
74  73  
75 
// Build articulation points for this each subGraph 

76 
vector<VertexVec> art_points_vec(num_bcc()); 

77 
for (int i = 0; i < num_bcc(); ++i) { 

78 
// TODO optimize here  remove the function 

79 
art_points_vec[i] = get_art_points_for_component(i); 

74 
// Generating subgraph for each subcomponent 

75 
BGL_FORALL_EDGES(edge, g, Graph) { 

76 
int comp_index = boost::get(component_map, edge); 

77 
Router r1 = g[boost::source(edge, g)]; 

78 
Router r2 = g[boost::target(edge, g)]; 

79 
Link l = g[edge]; 

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

80  81 
} 
81  82  
82 
// 

83  83 
for (int i = 0; i < num_bcc(); ++i) { 
84 
SubComponent subComp = SubComponent( 

85 
art_points_vec[i], 

86 
subGraphVec[i] 

87 
); 

88 
BCCs[i] = subComp; 

84 
cout << BCCs[i] << endl; 

89  85 
} 
90  
91  
92  86 
} 
93  87  
94  88 
void BiConnectedComponents::print() { 
...  ...  
216  210  
217  211 
std::vector<int> components = boost::get(art_point_component_map, articulation_point); 
218  212  
219 
cout << "Components belonging to articulation point " << g[articulation_point].name << endl;


213 
cout << "Components belonging to articulation point " << g[articulation_point].label << endl;


220  214  
221  215 
for (ii = components.begin(); ii < components.end(); ++ii) { 
222  216 
cout << *ii << endl; 
...  ...  
260  254 
return normal_points; 
261  255 
} 
262  256  
263 
void BiConnectedComponents::compute_weight() { 

264 
_initialize_weight(); 

265 
_initialize_queue(); 

266  
267 
while (!Q.empty()) { 

268 
QueueElem elem = Q.front(); 

269 
Q.pop(); 

270 
int comp_index = elem.component_index; 

271 
Vertex current_art_point = elem.art_point; 

272  
273 
if (elem.type == "component_vertex_pair") { 

274 
int size = BCCs[comp_index].num_vertices()  1; 

275 
VertexVec art_points = BCCs[comp_index].get_art_points(); 

276  
277 
// TODO: I assume here that vvi != art_points.end(), aka. the element is always found. 

278 
VertexVecIter vvi; 

279 
vvi = std::find(art_points.begin(), art_points.end(), current_art_point); 

280 
try { 

281 
art_points.erase(vvi); 

282 
} 

283 
catch (exception& e) { 

284 
cout << "Standard exception: " << e.what() << endl; 

285 
} 

286  
287 
for (vvi = art_points.begin(); vvi != art_points.end(); ++vvi) { 

288 
cout << " " << g[*vvi].name << endl; 

289 
int weight = BCCs[comp_index].getWeight(*vvi); 

290 
if (weight != 1) { 

291 
size += boost::num_vertices(g)  weight  1; 

292 
} 

293 
} 

294  
295 
int link_weight = size; 

296 
// _verify_weight(comp_index, current_art_point, link_weight); 

297 
BCCs[comp_index].setWeight(current_art_point, link_weight); 

298  
299 
_find_unknown_weight_wrt_art_point(current_art_point); 

300 
} 

301  
302 
if (elem.type == "vertex_component_pair") { 

303 
vector<int> comp_indices = get_components_for_art_point(current_art_point);; 

304  
305 
vector<int>::iterator vi; 

306 
vi = std::find(comp_indices.begin(), comp_indices.end(), comp_index); 

307 
try { 

308 
comp_indices.erase(vi); 

309 
} 

310 
catch (exception& e) { 

311 
cout << "Standard exception: " << e.what() << endl; 

312 
} 

313  
314 
int size = 0; 

315 
for (vi = comp_indices.begin(); vi != comp_indices.end(); ++vi) { 

316 
int weight = BCCs[*vi].getWeight(current_art_point); 

317 
if (weight != 1) { 

318 
size += weight; 

319 
} 

320 
} 

321  
322 
int link_weight = boost::num_vertices(g)  1  size; 

323 
// _verify_weight(comp_index, current_art_point, link_weight); 

324 
BCCs[comp_index].setWeight(current_art_point, link_weight); 

325 
_find_unknown_weight_wrt_component(comp_index); 

326  
327 
} 

328 
} 

329 
} 

330  
331 
void BiConnectedComponents::_initialize_weight() { 

332 
ComponentIter_t ci; 

333 
for (ComponentIter_t ci = BCCs.begin(); ci != BCCs.end(); ++ci) { 

334 
(*ci)._initialize_weight(); 

335 
} 

336 
} 

337  
338 
void BiConnectedComponents::_initialize_queue() { 

339 
VertexVecIter vvi; 

340  
341 
int i = 0; 

342 
VertexVec current_art_points; 

343 
for (i; i < num_bcc(); ++i) { 

344 
current_art_points = BCCs[i].get_art_points(); 

345 
if (current_art_points.size() == 1) { 

346 
// creating element for queue Q 

347 
Vertex art_point = current_art_points[0]; 

348 
string type = "component_vertex_pair"; 

349 
QueueElem qe = { 

350 
.component_index = i, 

351 
.art_point = art_point, 

352 
.type = type, 

353 
}; 

354  
355 
Q.push(qe); 

356 
} 

357 
} 

358 
} 

359  
360 
void BiConnectedComponents::_find_unknown_weight_wrt_art_point(Vertex art_point) { 

361 
int num_of_uncomputed_weight = 0; 

362 
vector<int> uncomputed_weight_component_indices; 

363  
364 
size_t i; 

365 
for (i = 0; i < num_bcc(); ++i) { 

366 
if (hasVertex(art_point, i)) { 

367 
// Check if value 1 appear exactly 1 time 

368 
if (BCCs[i].getWeight(art_point) == 1) { 

369 
num_of_uncomputed_weight += 1; 

370 
uncomputed_weight_component_indices.insert(uncomputed_weight_component_indices.end(), i); 

371 
} 

372 
} 

373  
374 
if (num_of_uncomputed_weight > 1) { 

375 
break; 

376 
} 

377 
} 

378  
379 
if (num_of_uncomputed_weight == 1) { 

380 
QueueElem elem = { 

381 
component_index: uncomputed_weight_component_indices[0], 

382 
art_point: art_point, 

383 
type: "vertex_component_pair", 

384 
}; 

385 
Q.push(elem); 

386 
} 

387 
} 

388  
389 
void BiConnectedComponents::_find_unknown_weight_wrt_component(int comp_index) { 

390 
VertexVec unknown_weight_vertices; 

391 
BCCs[comp_index]._find_vertices_with_unknown_weight(unknown_weight_vertices); 

392  
393 
if (unknown_weight_vertices.size() == 1) { 

394 
QueueElem elem = { 

395 
.component_index = comp_index, 

396 
.art_point = unknown_weight_vertices[0], 

397 
.type = "component_vertex_pair", 

398 
}; 

399  
400 
Q.push(elem); 

401 
} 

402 
} 

403  
404 
void BiConnectedComponents::print_weight() { 

405 
for (int i = 0; i < num_bcc(); ++i) { 

406 
BCCs[i].printWeight(); 

407 
} 

408 
} 

409  
410 
void BiConnectedComponents::findBetweennessCentrality() { 

411 
for (int i = 0; i < num_bcc(); ++i) { 

412 
// BCCs[i]._computeTrafficMatrix(); 

413 
cout << "###########" << endl; 

414 
_print_art_points(); 

415 
cout << "###########" << endl; 

416 
BCCs[i].findBetweennessCentrality(); 

417 
} 

418 
} 

419  
420 
void BiConnectedComponents::printBetweennessCentrality() { 

421 
for (int i = 0; i < num_bcc(); ++i) { 

422 
BCCs[i].printBetweennessCentrality(); 

423 
} 

424 
} 

425  
426 
void BiConnectedComponents::_print_art_points() { 

427 
for (int i = 0; i < art_points.size(); ++i) { 

428 
cout << &art_points[i] << endl; 

429 
} 

430 
} 

431  
432 
void BiConnectedComponents::_test_set_difference() { 

433 
VertexVec component = bcc_vertices[0]; 

434 
VertexVec intersection_result; 

435  
436 
cout << "******** Test set_difference ********" << endl; 

437 
cout << " Component" << endl; 

438 
for (VertexVecIter vvi = component.begin(); vvi != component.end(); ++vvi) { 

439 
cout << "\t" << *vvi << endl; 

440 
} 

441 
cout << " Articulation points" << endl; 

442 
cout << " " << &art_points[0] << endl; 

443 
cout << " " << &art_points[1] << endl; 

444  
445 
for (VertexVecIter vvi = art_points.begin(); vvi != art_points.end(); ++vvi) { 

446 
cout << "\t" << *vvi << endl; 

447 
} 

448  
449 
VertexVec copy_art_points = VertexVec(art_points); 

450 
cout << " Copy Articulation points" << endl; 

451 
cout << " " << ©_art_points << endl; 

452 
// cout << " " << &(*copy_art_points) << endl; 

453 
cout << " " << &(copy_art_points[0]) << " " << copy_art_points[0] << endl; 

454 
cout << " " << &(*(©_art_points[0])) << " " << *(©_art_points[0]) << endl; 

455 
cout << " " << ©_art_points[1] << " " << copy_art_points[1] << endl; 

456 
for (VertexVecIter vvi = copy_art_points.begin(); vvi != copy_art_points.end(); ++vvi) { 

457 
cout << "\t" << *vvi << endl; 

458 
} 

459  
460 
std::set_intersection(component.begin(), component.end(), art_points.begin(), art_points.end(), back_inserter(intersection_result)); 

461  
462 
cout << " Intersection result" << endl; 

463 
for (VertexVecIter vvi = intersection_result.begin(); vvi != intersection_result.end(); ++vvi) { 

464 
cout << "\t" << *vvi << endl; 

465 
} 

466  
467 
VertexVec difference_result; 

468 
std::set_intersection(component.begin(), component.end(), art_points.begin(), art_points.end(), back_inserter(difference_result)); 

469  
470 
cout << " Difference result" << endl; 

471 
for (VertexVecIter vvi = difference_result.begin(); vvi != difference_result.end(); ++vvi) { 

472 
cout << "\t" << *vvi << endl; 

473 
} 

474 
} 

257 
// void BiConnectedComponents::compute_weight() { 

258 
// _initialize_weight(); 

259 
// _initialize_queue(); 

260  
261 
// while (!Q.empty()) { 

262 
// QueueElem elem = Q.front(); 

263 
// Q.pop(); 

264 
// int comp_index = elem.component_index; 

265 
// Vertex current_art_point = elem.art_point; 

266  
267 
// if (elem.type == "component_vertex_pair") { 

268 
// int size = BCCs[comp_index].num_vertices()  1; 

269 
// VertexVec art_points = BCCs[comp_index].art_points(); 

270  
271 
// // TODO: I assume here that vvi != art_points.end(), aka. the element is always found. 

272 
// VertexVecIter vvi; 

273 
// vvi = std::find(art_points.begin(), art_points.end(), current_art_point); 

274 
// try { 

275 
// art_points.erase(vvi); 

276 
// } 

277 
// catch (exception& e) { 

278 
// cout << "Standard exception: " << e.what() << endl; 

279 
// } 

280  
281 
// for (vvi = art_points.begin(); vvi != art_points.end(); ++vvi) { 

282 
// cout << " " << g[*vvi].label << endl; 

283 
// int weight = BCCs[comp_index].getWeight(*vvi); 

284 
// if (weight != 1) { 

285 
// size += boost::num_vertices(g)  weight  1; 

286 
// } 

287 
// } 

288  
289 
// int link_weight = size; 

290 
// // _verify_weight(comp_index, current_art_point, link_weight); 

291 
// BCCs[comp_index].setWeight(current_art_point, link_weight); 

292  
293 
// _find_unknown_weight_wrt_art_point(current_art_point); 

294 
// } 

295  
296 
// if (elem.type == "vertex_component_pair") { 

297 
// vector<int> comp_indices = get_components_for_art_point(current_art_point);; 

298  
299 
// vector<int>::iterator vi; 

300 
// vi = std::find(comp_indices.begin(), comp_indices.end(), comp_index); 

301 
// try { 

302 
// comp_indices.erase(vi); 

303 
// } 

304 
// catch (exception& e) { 

305 
// cout << "Standard exception: " << e.what() << endl; 

306 
// } 

307  
308 
// int size = 0; 

309 
// for (vi = comp_indices.begin(); vi != comp_indices.end(); ++vi) { 

310 
// int weight = BCCs[*vi].getWeight(current_art_point); 

311 
// if (weight != 1) { 

312 
// size += weight; 

313 
// } 

314 
// } 

315  
316 
// int link_weight = boost::num_vertices(g)  1  size; 

317 
// // _verify_weight(comp_index, current_art_point, link_weight); 

318 
// BCCs[comp_index].setWeight(current_art_point, link_weight); 

319 
// _find_unknown_weight_wrt_component(comp_index); 

320  
321 
// } 

322 
// } 

323 
// } 

324  
325 
// void BiConnectedComponents::_initialize_weight() { 

326 
// ComponentIter_t ci; 

327 
// for (ComponentIter_t ci = BCCs.begin(); ci != BCCs.end(); ++ci) { 

328 
// (*ci)._initialize_weight(); 

329 
// } 

330 
// } 

331  
332 
// void BiConnectedComponents::_initialize_queue() { 

333 
// VertexVecIter vvi; 

334  
335 
// int i = 0; 

336 
// VertexVec current_art_points; 

337 
// for (i; i < num_bcc(); ++i) { 

338 
// current_art_points = BCCs[i].art_points(); 

339 
// if (curr ent_art_points.size() == 1) { 

340 
// // creating element for queue Q 

341 
// Vertex art_point = current_art_points[0]; 

342 
// string type = "component_vertex_pair"; 

343 
// QueueElem qe = { 

344 
// .component_index = i, 

345 
// .art_point = art_point, 

346 
// .type = type, 

347 
// }; 

348  
349 
// Q.push(qe); 

350 
// } 

351 
// } 

352 
// } 

353  
354 
// void BiConnectedComponents::_find_unknown_weight_wrt_art_point(Vertex art_point) { 

355 
// int num_of_uncomputed_weight = 0; 

356 
// vector<int> uncomputed_weight_component_indices; 

357  
358 
// size_t i; 

359 
// for (i = 0; i < num_bcc(); ++i) { 

360 
// if (hasVertex(art_point, i)) { 

361 
// // Check if value 1 appear exactly 1 time 

362 
// if (BCCs[i].getWeight(art_point) == 1) { 

363 
// num_of_uncomputed_weight += 1; 

364 
// uncomputed_weight_component_indices.insert(uncomputed_weight_component_indices.end(), i); 

365 
// } 

366 
// } 

367  
368 
// if (num_of_uncomputed_weight > 1) { 

369 
// break; 

370 
// } 

371 
// } 

372  
373 
// if (num_of_uncomputed_weight == 1) { 

374 
// QueueElem elem = { 

375 
// component_index: uncomputed_weight_component_indices[0], 

376 
// art_point: art_point, 

377 
// type: "vertex_component_pair", 

378 
// }; 

379 
// Q.push(elem); 

380 
// } 

381 
// } 

382  
383 
// void BiConnectedComponents::_find_unknown_weight_wrt_component(int comp_index) { 

384 
// VertexVec unknown_weight_vertices; 

385 
// BCCs[comp_index]._find_vertices_with_unknown_weight(unknown_weight_vertices); 

386  
387 
// if (unknown_weight_vertices.size() == 1) { 

388 
// QueueElem elem = { 

389 
// .component_index = comp_index, 

390 
// .art_point = unknown_weight_vertices[0], 

391 
// .type = "component_vertex_pair", 

392 
// }; 

393  
394 
// Q.push(elem); 

395 
// } 

396 
// } 

397  
398 
// void BiConnectedComponents::print_weight() { 

399 
// for (int i = 0; i < num_bcc(); ++i) { 

400 
// BCCs[i].printWeight(); 

401 
// } 

402 
// } 

403  
404 
// void BiConnectedComponents::findBetweennessCentrality() { 

405 
// for (int i = 0; i < num_bcc(); ++i) { 

406 
// // BCCs[i]._computeTrafficMatrix(); 

407 
// cout << "###########" << endl; 

408 
// _print_art_points(); 

409 
// cout << "###########" << endl; 

410 
// BCCs[i].findBetweennessCentrality(); 

411 
// } 

412 
// } 

413  
414 
// void BiConnectedComponents::printBetweennessCentrality() { 

415 
// for (int i = 0; i < num_bcc(); ++i) { 

416 
// BCCs[i].printBetweennessCentrality(); 

417 
// } 

418 
// } 

419  
420 
// void BiConnectedComponents::_print_art_points() { 

421 
// for (int i = 0; i < art_points.size(); ++i) { 

422 
// cout << &art_points[i] << endl; 

423 
// } 

424 
// } 

425  
426 
// void BiConnectedComponents::_test_set_difference() { 

427 
// VertexVec component = bcc_vertices[0]; 

428 
// VertexVec intersection_result; 

429  
430 
// cout << "******** Test set_difference ********" << endl; 

431 
// cout << " Component" << endl; 

432 
// for (VertexVecIter vvi = component.begin(); vvi != component.end(); ++vvi) { 

433 
// cout << "\t" << *vvi << endl; 

434 
// } 

435 
// cout << " Articulation points" << endl; 

436 
// cout << " " << &art_points[0] << endl; 

437 
// cout << " " << &art_points[1] << endl; 

438  
439 
// for (VertexVecIter vvi = art_points.begin(); vvi != art_points.end(); ++vvi) { 

440 
// cout << "\t" << *vvi << endl; 

441 
// } 

442  
443 
// VertexVec copy_art_points = VertexVec(art_points); 

444 
// cout << " Copy Articulation points" << endl; 

445 
// cout << " " << ©_art_points << endl; 

446 
// // cout << " " << &(*copy_art_points) << endl; 

447 
// cout << " " << &(copy_art_points[0]) << " " << copy_art_points[0] << endl; 

448 
// cout << " " << &(*(©_art_points[0])) << " " << *(©_art_points[0]) << endl; 

449 
// cout << " " << ©_art_points[1] << " " << copy_art_points[1] << endl; 

450 
// for (VertexVecIter vvi = copy_art_points.begin(); vvi != copy_art_points.end(); ++vvi) { 

451 
// cout << "\t" << *vvi << endl; 

452 
// } 

453  
454 
// std::set_intersection(component.begin(), component.end(), art_points.begin(), art_points.end(), back_inserter(intersection_result)); 

455  
456 
// cout << " Intersection result" << endl; 

457 
// for (VertexVecIter vvi = intersection_result.begin(); vvi != intersection_result.end(); ++vvi) { 

458 
// cout << "\t" << *vvi << endl; 

459 
// } 

460  
461 
// VertexVec difference_result; 

462 
// std::set_intersection(component.begin(), component.end(), art_points.begin(), art_points.end(), back_inserter(difference_result)); 

463  
464 
// cout << " Difference result" << endl; 

465 
// for (VertexVecIter vvi = difference_result.begin(); vvi != difference_result.end(); ++vvi) { 

466 
// cout << "\t" << *vvi << endl; 

467 
// } 

468 
// } 
Also available in: Unified diff