root / custompackages / graphparser / src / bi_connected_components.cpp @ 4ca27bae
History  View  Annotate  Download (17 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 
// cout << "BC for component " << i << endl;

126 
BCCs[i].CalculateBetweennessCentralityHeuristic(); 
127 
} 
128  
129 
double score;

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

132 
for (string id: BCCs[i].all_vertices_id()) { 
133 
score = BCCs[i].get_betweenness_centrality(id); 
134 
// cout << "XXX score from component << " << i << ", id " << id << " = " << score << endl;

135 
bc_score_[id] += score; 
136 
} 
137 
} 
138  
139 
// // Sum the BC for each subcomponent

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

141 
// // For non articulation points

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

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

144 
// bc_score_[id] = score;

145 
// }

146  
147 
// // For articulation points

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

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

150 
// bc_sum_art_points_[id] += score;

151 
// }

152 
// }

153  
154 
// Update the BC score for articulation points

155 
// for (string id : all_art_points_id_) {

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

157  
158 
// // TODO: Jan 29, 2015: for now, I do not minus the bc_inter_

159 
// cout << bc_score_[id] << " > ";

160 
// bc_score_[id] = bc_inter_[id];

161 
// cout << bc_score_[id] << endl;

162 
// }

163  
164 
finalize_betweenness_centrality_heuristic(); 
165  
166 
cout << "DONE WITH BETWEENNESS CENTRALITY\n";

167 
} 
168  
169 
// BETWEENNESS CENTRALITY  NORMAL CALCULATION

170 
void BiConnectedComponents::CalculateBetweennessCentrality(bool targets_inclusion) { 
171 
initialize_betweenness_centrality(); 
172  
173 
if (gm_.weighted_graph()) { // calculate BC for weighted graph 
174 
cout << "======= BCC  BC for weighted graph ======\n";

175  
176 
typedef map<Edge, double> EdgeWeightStdMap; 
177 
typedef boost::associative_property_map<EdgeIndexStdMap> EdgeWeightPMap;

178 
EdgeIndexStdMap edge_weight_std_map; 
179 
EdgeWeightPMap edge_weight_pmap = EdgeWeightPMap(edge_weight_std_map); 
180  
181 
BGL_FORALL_EDGES(edge, gm_.g_, Graph) { 
182 
edge_weight_std_map[edge] = gm_.g_[edge].cost; 
183 
} 
184 
boost::brandes_betweenness_centrality_targets_inclusion(gm_.g_, 
185 
targets_inclusion, 
186 
boost::centrality_map( 
187 
v_centrality_pmap_).vertex_index_map( 
188 
gm_.v_index_pmap()).weight_map( 
189 
edge_weight_pmap) 
190 
); 
191 
} 
192 
else { // for unweighted graph 
193 
boost::brandes_betweenness_centrality_targets_inclusion(gm_.g_, 
194 
targets_inclusion, 
195 
boost::centrality_map( 
196 
v_centrality_pmap_).vertex_index_map( 
197 
gm_.v_index_pmap()) 
198 
); 
199 
} 
200  
201 
boost::relative_betweenness_centrality(gm_.g_, v_centrality_pmap_); 
202 
} 
203  
204 
// HELPERS FOR OUTPUTTING RESULT

205 
void BiConnectedComponents::print_all_sub_components() {

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

208 
BCCs[i].print(); 
209 
} 
210 
} 
211  
212 
void BiConnectedComponents::print_biconnected_components() {

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

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

215  
216 
cout << "All Sub Components:\n\n";

217 
for (int i = 0; i < num_of_bcc_; ++i) { 
218 
cout << " " << i << endl;

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

220 
} 
221 
} 
222  
223 
void BiConnectedComponents::print_betweenness_centrality() {

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

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

227 
} 
228 
} 
229  
230 
void BiConnectedComponents::print_betweenness_centrality_heuristic() {

231 
outops::operator<< <double>(cout, bc_relative_score_); 
232 
} 
233  
234 
void BiConnectedComponents::write_all_betweenness_centrality(string filepath) { 
235 
/* Write the heuristic and the normal version of betweenness centrality

236 
1st column: brandes_betweenness_centrality

237 
2nd column: heuristic_betweenness_centrality

238 
*/

239  
240 
vector<pair<string, double> > mapcopy(bc_relative_score_.begin(), bc_relative_score_.end()); 
241 
std::sort(mapcopy.begin(), mapcopy.end(), less_second<string, double>()); 
242  
243 
ofstream outFile(filepath.c_str()); 
244  
245 
Viter vi, ve; 
246 
size_t i = 0;

247 
if (outFile.is_open()) {

248 
for(auto id_bc_score_pair : mapcopy) { 
249 
string id = id_bc_score_pair.first;

250 
double heuristic_bc_score = id_bc_score_pair.second;

251  
252 
int index = gm_.get_index_from_id(id);

253 
double bc_score = v_centrality_vec_.at(index);

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

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

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

260 
// ++i;

261 
// }

262 
} 
263 
outFile.close(); 
264 
cout << "Finish writing brandes and heurisic BC score to file " << filepath << endl;

265 
} 
266  
267 
void BiConnectedComponents::print() {

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

269 
cout << gm_; 
270  
271 
print_biconnected_components(); 
272  
273 
cout << "\nHeuristic Betweenness Centrality Score:\n";

274 
outops::operator<< <double>(cout, bc_score_); 
275  
276 
cout << "\nHeuristic Betweenness Centrality Relative Score:\n";

277 
outops::operator<< <double>(cout, bc_relative_score_); 
278  
279 
cout << "\nNormal Betweenness Centrality Score:\n";

280 
print_betweenness_centrality(); 
281 
} 
282  
283 
std::ostream& operator<<(std::ostream& os, const BiConnectedComponents& rhs) { 
284 
cout << "\n\nBiConnected Components\n\n";

285 
cout << rhs.gm_; 
286  
287 
cout << "\nArticulation points:\n";

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

289  
290 
cout << "\nHeuristic Betweenness Centrality Score:\n";

291 
outops::operator<< <double>(cout, rhs.bc_score()); 
292  
293 
cout << "\nHeuristic Betweenness Centrality Relative Score:\n";

294 
outops::operator<< <double>(cout, rhs.bc_relative_score()); 
295  
296 
return os;

297 
} 
298  
299 
/******************************

300 
* Private functions

301 
******************************/

302 
// SUBCOMPONENT

303 
void BiConnectedComponents::reset_num_of_bcc() {

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

305 
} 
306  
307 
void BiConnectedComponents::CreateSubComponents() {

308 
for (int i = 0; i < num_of_bcc_; ++i) { 
309 
BCCs.push_back(SubComponent(gm_.weighted_graph())); 
310 
} 
311  
312 
// Generating subgraph for each subcomponent

313 
BGL_FORALL_EDGES(edge, gm_.g_, Graph) { 
314 
Vertex source = boost::source(edge, gm_.g_); 
315 
Vertex target = boost::target(edge, gm_.g_); 
316  
317 
int comp_index = boost::get(component_map_, edge);

318 
cout << comp_index << " ";

319  
320 
if (comp_index == 1) { 
321 
cout << "ERROR: edge ";

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

324 
} 
325 
else {

326 
Router r1 = gm_.g_[source]; 
327 
Router r2 = gm_.g_[target]; 
328 
Link l = gm_.g_[edge]; 
329 
if (r1 != r2) { // Do not add selfloop edge 
330 
BCCs[comp_index].AddEdge(r1, r2, l); 
331 
} 
332 
} 
333 
} 
334  
335 
// Finalizing each sub components

336 
for (int i = 0; i < num_of_bcc_; ++i) { 
337 
BCCs[i].FinalizeSubComponent(all_art_points_id_); 
338 
} 
339 
} 
340  
341 
// LINK WEIGHT

342 
void BiConnectedComponents::initialize_weight() {

343 
for (int i = 0; i < num_of_bcc_; ++i) { 
344 
BCCs[i].initialize_weight(); 
345 
} 
346 
} 
347  
348 
void BiConnectedComponents::initialize_queue() {

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

352 
string type = "component_vertex_pair"; 
353 
QueueElem elem = { 
354 
.component_index = i, 
355 
.vertex_id = vertex_id, 
356 
.type = type, 
357 
}; 
358 
// cout << "adding component_vertex_pair (" << i << " " << vertex_id << ")\n";

359 
Q.push(elem); 
360 
} 
361 
} 
362 
} 
363  
364 
void BiConnectedComponents::process_component_vertex_pair(int comp_index, string vertex_id) { 
365 
int size = BCCs[comp_index].num_of_vertices()  1; 
366 
for (string s : BCCs[comp_index].art_points_id()) { 
367 
if (s.compare(vertex_id) != 0) { 
368 
int weight = BCCs[comp_index].get_weight_map(s);

369 
if (weight != 1) { 
370 
size += num_of_vertices_  weight  1;

371 
} 
372 
} 
373 
} 
374 
int link_weight = size;

375  
376 
int old_link_weight = BCCs[comp_index].get_weight_map(vertex_id);

377 
if (old_link_weight != 1) { 
378 
if (link_weight != old_link_weight) {

379 
cout << "ERROR in Link Weight for comp " << comp_index << "  vertex " << vertex_id << old_link_weight << "  " << link_weight << endl; 
380 
} 
381 
} 
382  
383 
BCCs[comp_index].update_weight_map(vertex_id, link_weight); 
384 
// cout << " update weight for comp " << comp_index << "  vertex " << vertex_id << " = " << link_weight << endl;

385 
find_unknown_weight_wrt_art_point(vertex_id); 
386 
} 
387  
388 
void BiConnectedComponents::find_unknown_weight_wrt_art_point(string vertex_id) { 
389 
int count = 0; 
390 
int comp_index = 1; 
391 
// cout << "find_unknown_weight_wrt_art_point " << vertex_id << "\n";

392  
393 
for (int i = 0; i < num_of_bcc_; ++i) { 
394 
if (BCCs[i].vertex_exists(vertex_id)) {

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

397 
++count; 
398 
comp_index = i; 
399 
} 
400  
401 
if (count > 1) break; 
402 
} 
403 
} 
404  
405 
if (count == 1) { 
406 
// Add new element to QueueElem

407 
QueueElem elem = { 
408 
.component_index = comp_index, 
409 
.vertex_id = vertex_id, 
410 
.type = "vertex_component_pair"

411 
}; 
412  
413 
// cout << " Add vertex_component_pair: " << comp_index << "  " << vertex_id << endl;

414 
Q.push(elem); 
415 
} 
416 
} 
417  
418 
void BiConnectedComponents::process_vertex_component_pair(int comp_index, string vertex_id) { 
419 
int size = 0; 
420  
421 
for (int i = 0; i < num_of_bcc_; ++i) { 
422 
if (i != comp_index) {

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

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

425 
if (weight != 1) { 
426 
size += weight; 
427 
} 
428 
} 
429 
} 
430 
} 
431  
432 
int link_weight = num_of_vertices_  1  size; 
433  
434 
int old_link_weight = BCCs[comp_index].get_weight_map(vertex_id);

435 
if (old_link_weight != 1) { 
436 
if (link_weight != old_link_weight) {

437 
cout << "ERROR in Link Weight for comp " << comp_index << "  vertex " << vertex_id << old_link_weight << "  " << link_weight << endl; 
438 
} 
439 
} 
440  
441 
BCCs[comp_index].update_weight_map(vertex_id, link_weight); 
442 
// cout << " update weight for vertex_component pair: " << comp_index << "  " << vertex_id << " = " << link_weight << endl;

443 
find_unknown_weight_wrt_component(comp_index); 
444 
} 
445  
446 
void BiConnectedComponents::find_unknown_weight_wrt_component(int comp_index) { 
447 
// The 'counting' solution is found here: http://stackoverflow.com/questions/5517615/countingnumberofsamevaluesinmap

448 
typedef NameToIntMap::value_type MapEntry;

449 
int count = std::count_if(

450 
BCCs[comp_index].weight_map().begin(), 
451 
BCCs[comp_index].weight_map().end(), 
452 
second_equal_to<MapEntry>(1));

453  
454 
if (count == 1) { 
455 
// Find the vertex id for the vertex with unknown link weight

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

457  
458 
QueueElem elem = { 
459 
.component_index = comp_index, 
460 
.vertex_id = vertex_id, 
461 
.type = "component_vertex_pair",

462 
}; 
463 
// cout << "Add component_vertex_pair: " << comp_index << "  " << vertex_id << endl;

464 
Q.push(elem); 
465 
} 
466 
} 
467  
468 
bool BiConnectedComponents::verify_link_weight() {

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

470 
bool result = true; 
471  
472 
for (int i = 0; i < num_of_bcc_; ++i) { 
473 
for (string id : BCCs[i].art_points_id()) { 
474 
if (BCCs[i].get_weight_map(id) == 1) { 
475 
cout << "ERROR Link Weight for vertex " << id << " in component " << i << " = " << 1 << endl; 
476 
result = false;

477 
} 
478 
} 
479 
} 
480 
} 
481  
482 
// BETWEENNESS CENTRALITY  HEURISTIC

483 
void BiConnectedComponents::initialize_betweenness_centrality_heuristic() {

484 
// Initialize bc_inter_ to be 0

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

487 
} 
488  
489 
StringSet all_vertices_id; 
490 
graphext::id_of_all_vertices(gm_.g_, all_vertices_id); 
491  
492 
// Initialize bc_sum_, bc_score_ to be 0

493 
for (string id: all_vertices_id) { 
494 
bc_sum_art_points_[id] = 0;

495 
bc_score_[id] = 0;

496 
} 
497 
} 
498  
499 
void BiConnectedComponents::calculate_bc_inter() {

500 
for (int i = 0; i < num_of_bcc_; ++i) { 
501 
for (string id : BCCs[i].art_points_id()) { 
502 
bc_inter_[id] += BCCs[i].get_weight_map(id) * BCCs[i].get_weight_reversed_map(id); 
503 
} 
504 
} 
505 
} 
506  
507 
void BiConnectedComponents::finalize_betweenness_centrality_heuristic() {

508 
// Divide the bc_score_ by some factor

509 
int n = num_of_vertices();

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

513 
double old_value = iter>second;

514 
bc_relative_score_[iter>first] = old_value * factor; 
515 
} 
516 
} 
517  
518 
// BETWEENNESS CENTRALITY

519 
void BiConnectedComponents::initialize_betweenness_centrality() {

520 
v_centrality_vec_ = CentralityVec(num_of_vertices()); 
521 
v_centrality_pmap_ = CentralityPMap(v_centrality_vec_.begin(), gm_.v_index_pmap()); 
522 
} 