Statistics
| Branch: | Revision:

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
}