Statistics
| Branch: | Revision:

root / custompackages / graph-parser / src / bi_connected_components.cpp @ 6575aa2e

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