Revision 162e1bda custompackages/graph-parser/src/bi_connected_components.cpp

View differences:

custompackages/graph-parser/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
/* SUB-COMPONENT */
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 sub-component
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
// SUB-COMPONENT
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 sub-component
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 sub-component
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\nBi-Connected 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\nBi-Connected 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
// SUB-COMPONENT
295
void BiConnectedComponents::CreateSubComponents() {
296
    // Generating subgraph for each sub-component
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