Statistics
| Branch: | Revision:

root / custompackages / graph-parser / src / bi_connected_components.cpp @ 162e1bda

History | View | Annotate | Download (15.9 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
    cout << "BCC constructor \n";
13
    init();
14
    FindBiConnectedComponents();
15
}
16

    
17
void BiConnectedComponents::init() {
18
    // Set some variables
19
    num_of_vertices_ = boost::num_vertices(gm_.g_);
20

    
21
    component_vec_ = ComponentVec(boost::num_edges(gm_.g_), -1);
22
    component_map_ = ComponentMap(component_vec_.begin(), gm_.e_index_pmap());
23
}
24

    
25
/* GETTER */
26
int const BiConnectedComponents::num_of_bcc() {
27
    if (num_of_bcc_ == -1) { // calculate it
28
        // +1 to counteract for the zero-indexing
29
        num_of_bcc_ = *std::max_element(component_vec_.begin(), component_vec_.end()) + 1;
30
    }
31

    
32
    return num_of_bcc_;
33
}
34

    
35
int const BiConnectedComponents::num_of_vertices() const {
36
    return num_of_vertices_;
37
}
38

    
39
StringSet const& BiConnectedComponents::all_art_points_id() const {
40
    return all_art_points_id_;
41
}
42

    
43
NameToDoubleMap const& BiConnectedComponents::bc_score() const {
44
    return bc_score_;
45
}
46

    
47
NameToDoubleMap const& BiConnectedComponents::bc_relative_score() const {
48
    return bc_relative_score_;
49
}
50

    
51
// AUTO RUN
52
void BiConnectedComponents::run() {
53
    /* Auto run all the necessary functions
54
    */
55
    FindBiConnectedComponents();
56

    
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
    }
62

    
63
    // Calculate Link Weight + Link Weight Reversed
64
    cout << "Calculate Link Weight + Link Weight Reversed\n";
65
    CalculateLinkWeight();
66
    CalculateLinkWeightReversed();
67
    verify_link_weight();
68

    
69
    // Calculate Traffic Matrix
70
    cout << "Calculate Traffic Matrix\n";
71
    CalculateTrafficMatrix();
72

    
73
    // Calculate Betweenness Centrality Heuristic
74
    cout << "Calculate Betweenness Centrality Heuristic\n";
75
    CalculateBetweennessCentralityHeuristic();
76

    
77
    // Calculate Betweenness Centrality
78
    cout << "Calculate Betweenness Centrality\n";
79
    CalculateBetweennessCentrality();
80
}
81

    
82
// SUB-COMPONENT
83
void BiConnectedComponents::FindBiConnectedComponents() {
84
    cout << "Running FindBiConnectedComponents" << endl;
85

    
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();
100
}
101

    
102
// LINK WEIGHT
103
void BiConnectedComponents::CalculateLinkWeight() {
104
    initialize_weight();
105
    initialize_queue();
106

    
107
    while (!Q.empty()) {
108
        QueueElem elem = Q.front();
109
        Q.pop();
110
        int comp_index = elem.component_index;
111
        string vertex_id = elem.vertex_id;
112

    
113
        if (elem.type == "component_vertex_pair") {
114
            // cout << "component_vertex_pair: " << comp_index << " - " << vertex_id << endl;
115
            process_component_vertex_pair(comp_index, vertex_id);
116
        }
117
        else if (elem.type == "vertex_component_pair") {
118
            // cout << "vertex_component_pair: " << comp_index << " - " << vertex_id << endl;
119
            process_vertex_component_pair(comp_index, vertex_id);
120
        }
121
    }
122
}
123

    
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
131
void BiConnectedComponents::CalculateTrafficMatrix() {
132
    for (int i = 0; i < num_of_bcc_; ++i) {
133
        BCCs[i].CalculateTrafficMatrix();
134
    }
135
}
136

    
137
// BETWEENNESS CENTRALITY HEURISTIC
138
void BiConnectedComponents::CalculateBetweennessCentralityHeuristic() {
139
    cout << "BETWEENNESS CENTRALITY HEURISTIC\n";
140

    
141
    initialize_betweenness_centrality_heuristic();
142
    calculate_bc_inter();
143

    
144
    for (int i = 0; i < num_of_bcc_; ++i) {
145
        cout << "BC for component " << i << endl;
146
        BCCs[i].CalculateBetweennessCentralityHeuristic();
147
    }
148

    
149
    double score;
150
    for (int i = 0; i < num_of_bcc_; ++i) {
151
        // For all points
152
        for (string id: BCCs[i].all_vertices_id()) {
153
            score = BCCs[i].get_betweenness_centrality(id);
154
            cout << "XXX score from component << " << i << ", id " << id << " = " << score << endl;
155
            bc_score_[id] += score;
156
        }
157
    }
158

    
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
175
    for (string id : all_art_points_id_) {
176
    //     bc_score_[id] = bc_sum_art_points_[id];
177

    
178
        // TODO: Jan 29, 2015: for now, I do not minus the bc_inter_
179
        cout << bc_score_[id] << " --> ";
180
        bc_score_[id] -= bc_inter_[id];
181
        cout << bc_score_[id] << endl;
182
    }
183

    
184
    finalize_betweenness_centrality_heuristic();
185

    
186
    cout << "DONE WITH BETWEENNESS CENTRALITY\n";
187
}
188

    
189
// BETWEENNESS CENTRALITY - NORMAL CALCULATION
190
void BiConnectedComponents::CalculateBetweennessCentrality() {
191
    initialize_betweenness_centrality();
192

    
193
    boost::brandes_betweenness_centrality(gm_.g_,
194
        boost::centrality_map(
195
            v_centrality_pmap_).vertex_index_map(
196
            gm_.v_index_pmap())
197
    );
198

    
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();
208
    }
209
}
210

    
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;
215
    }
216
}
217

    
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
    */
227

    
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
        // }
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();
273
}
274

    
275
std::ostream& operator<<(std::ostream& os, const BiConnectedComponents& rhs) {
276
    cout << "\n\nBi-Connected Components\n\n";
277
    cout << rhs.gm_;
278

    
279
    cout << "\nArticulation points:\n";
280
    outops::operator<<(cout, rhs.all_art_points_id());
281

    
282
    cout << "\nHeuristic Betweenness Centrality Score:\n";
283
    outops::operator<< <double>(cout, rhs.bc_score());
284

    
285
    cout << "\nHeuristic Betweenness Centrality Relative Score:\n";
286
    outops::operator<< <double>(cout, rhs.bc_relative_score());
287

    
288
    return os;
289
}
290

    
291
/******************************
292
* Private functions
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
}
321

    
322
// LINK WEIGHT
323
void BiConnectedComponents::initialize_weight() {
324
    for (int i = 0; i < num_of_bcc_; ++i) {
325
        BCCs[i].initialize_weight();
326
    }
327
}
328

    
329
void BiConnectedComponents::initialize_queue() {
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
        }
335
        if (BCCs[i].art_points_id().size() == 1) {
336
            string vertex_id = *(BCCs[i].art_points_id().begin());
337
            string type = "component_vertex_pair";
338
            QueueElem elem = {
339
                .component_index = i,
340
                .vertex_id = vertex_id,
341
                .type = type,
342
            };
343
            cout << "adding component_vertex_pair (" << i << " " << vertex_id << ")\n";
344
            Q.push(elem);
345
        }
346
    }
347
}
348

    
349
void BiConnectedComponents::process_component_vertex_pair(int comp_index, string vertex_id) {
350
    int size = BCCs[comp_index].num_of_vertices() - 1;
351
    for (string s : BCCs[comp_index].art_points_id()) {
352
        if (s.compare(vertex_id) != 0) {
353
            int weight = BCCs[comp_index].get_weight_map(s);
354
            if (weight != -1) {
355
                size += num_of_vertices_ - weight - 1;
356
            }
357
        }
358
    }
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

    
368
    BCCs[comp_index].update_weight_map(vertex_id, link_weight);
369
    find_unknown_weight_wrt_art_point(vertex_id);
370
}
371

    
372
void BiConnectedComponents::find_unknown_weight_wrt_art_point(string vertex_id) {
373
    int count = 0;
374
    int comp_index = -1;
375
    cout << "find_unknown_weight_wrt_art_point " << vertex_id << "\n";
376

    
377
    for (int i = 0; i < num_of_bcc_; ++i) {
378
        if (BCCs[i].vertex_exists(vertex_id)) {
379
            if (BCCs[i].get_weight_map(vertex_id) == -1) {
380
                cout << "     comp_index = " << i << endl;
381
                ++count;
382
                comp_index = i;
383
            }
384

    
385
            if (count > 1) break;
386
        }
387
    }
388

    
389
    if (count == 1) {
390
        // Add new element to QueueElem
391
        QueueElem elem = {
392
            .component_index = comp_index,
393
            .vertex_id = vertex_id,
394
            .type = "vertex_component_pair"
395
        };
396

    
397
        cout << "        Add vertex_component_pair: " << comp_index << " - " << vertex_id << endl;
398
        Q.push(elem);
399
    }
400
}
401

    
402
void BiConnectedComponents::process_vertex_component_pair(int comp_index, string vertex_id) {
403
    int size = 0;
404

    
405
    for (int i = 0; i < num_of_bcc_; ++i) {
406
        if (i != comp_index) {
407
            if (BCCs[i].vertex_exists(vertex_id)) {
408
                int weight = BCCs[i].get_weight_map(vertex_id);
409
                if (weight != -1) {
410
                    size += weight;
411
                }
412
            }
413
        }
414
    }
415

    
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

    
425
    BCCs[comp_index].update_weight_map(vertex_id, link_weight);
426
    find_unknown_weight_wrt_component(comp_index);
427
}
428

    
429
void BiConnectedComponents::find_unknown_weight_wrt_component(int comp_index) {
430
    // The 'counting' solution is found here: http://stackoverflow.com/questions/5517615/counting-number-of-same-values-in-map
431
    typedef NameToIntMap::value_type MapEntry;
432
    int count = std::count_if(
433
        BCCs[comp_index].weight_map().begin(),
434
        BCCs[comp_index].weight_map().end(),
435
        second_equal_to<MapEntry>(-1));
436

    
437
    if (count == 1) {
438
        // Find the vertex id for the vertex with unknown link weight
439
        string vertex_id = BCCs[comp_index].first_vertex_id_with_unknown_weight();
440

    
441
        QueueElem elem = {
442
            .component_index = comp_index,
443
            .vertex_id = vertex_id,
444
            .type = "component_vertex_pair",
445
        };
446
        cout << "Add component_vertex_pair: " << comp_index << " - " << vertex_id << endl;
447
        Q.push(elem);
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());
505
}