root / custompackages / graph-parser / 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 |
// SUB-COMPONENT
|
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\nBi-Connected 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\nBi-Connected 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 |
// SUB-COMPONENT
|
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 sub-component
|
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 self-loop 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/counting-number-of-same-values-in-map
|
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 |
} |