Statistics
| Branch: | Revision:

root / custompackages / graph-parser / src / bi_connected_components.cpp @ 33e5ad95

History | View | Annotate | Download (16.2 KB)

1 ee0dd796 Quynh PX Nguyen
//
2
// Created by quynh on 1/9/16.
3
//
4
5
#include "bi_connected_components.h"
6
using namespace std;
7
8 cb770240 Quynh PX Nguyen
/******************************
9
* Public functions
10
******************************/
11 d5b7a27f Quynh PX Nguyen
BiConnectedComponents::BiConnectedComponents(GraphManager &gm) : gm_(gm) {
12 ee0dd796 Quynh PX Nguyen
    init();
13
}
14
15
void BiConnectedComponents::init() {
16 cb770240 Quynh PX Nguyen
    // Set some variables
17
    num_of_vertices_ = boost::num_vertices(gm_.g_);
18 ee0dd796 Quynh PX Nguyen
19 162e1bda Quynh PX Nguyen
    component_vec_ = ComponentVec(boost::num_edges(gm_.g_), -1);
20 437fd680 Quynh PX Nguyen
    component_map_ = ComponentMap(component_vec_.begin(), gm_.e_index_pmap());
21 ee0dd796 Quynh PX Nguyen
}
22
23 cb770240 Quynh PX Nguyen
/* GETTER */
24 437fd680 Quynh PX Nguyen
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 cb770240 Quynh PX Nguyen
StringSet const& BiConnectedComponents::all_art_points_id() const {
33
    return all_art_points_id_;
34
}
35 ee0dd796 Quynh PX Nguyen
36 437fd680 Quynh PX Nguyen
NameToDoubleMap const& BiConnectedComponents::bc_score() const {
37
    return bc_score_;
38
}
39
40 162e1bda Quynh PX Nguyen
NameToDoubleMap const& BiConnectedComponents::bc_relative_score() const {
41
    return bc_relative_score_;
42
}
43 ee0dd796 Quynh PX Nguyen
44 162e1bda Quynh PX Nguyen
// AUTO RUN
45
void BiConnectedComponents::run() {
46
    /* Auto run all the necessary functions
47
    */
48 d5b7a27f Quynh PX Nguyen
    cout << "Running FindBiConnectedComponents" << endl;
49 162e1bda Quynh PX Nguyen
    FindBiConnectedComponents();
50 ee0dd796 Quynh PX Nguyen
51 162e1bda Quynh PX Nguyen
    // Calculate Link Weight + Link Weight Reversed
52
    cout << "Calculate Link Weight + Link Weight Reversed\n";
53 cb770240 Quynh PX Nguyen
    CalculateLinkWeight();
54 162e1bda Quynh PX Nguyen
    CalculateLinkWeightReversed();
55
    verify_link_weight();
56 ee0dd796 Quynh PX Nguyen
57 cb770240 Quynh PX Nguyen
    // Calculate Traffic Matrix
58
    cout << "Calculate Traffic Matrix\n";
59
    CalculateTrafficMatrix();
60 ee0dd796 Quynh PX Nguyen
61 162e1bda Quynh PX Nguyen
    // Calculate Betweenness Centrality Heuristic
62
    cout << "Calculate Betweenness Centrality Heuristic\n";
63
    CalculateBetweennessCentralityHeuristic();
64 cb770240 Quynh PX Nguyen
}
65
66 162e1bda Quynh PX Nguyen
// 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 e263e3c7 Quynh PX Nguyen
    // Set some necessary variables
73 162e1bda Quynh PX Nguyen
    graphext::id_of_some_vertices(gm_.g_, art_points_, all_art_points_id_);
74 e263e3c7 Quynh PX Nguyen
    reset_num_of_bcc();
75
    cout << "Total # of components: " << num_of_bcc_ << endl;
76 162e1bda Quynh PX Nguyen
77
    // Process the result from boost::biconnected_components
78
    cout << "Create Sub Components\n";
79
    CreateSubComponents();
80 ee0dd796 Quynh PX Nguyen
}
81
82 162e1bda Quynh PX Nguyen
// LINK WEIGHT
83 cb770240 Quynh PX Nguyen
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 ee0dd796 Quynh PX Nguyen
    }
102
}
103
104 162e1bda Quynh PX Nguyen
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 cb770240 Quynh PX Nguyen
void BiConnectedComponents::CalculateTrafficMatrix() {
112
    for (int i = 0; i < num_of_bcc_; ++i) {
113
        BCCs[i].CalculateTrafficMatrix();
114
    }
115
}
116
117 162e1bda Quynh PX Nguyen
// BETWEENNESS CENTRALITY HEURISTIC
118
void BiConnectedComponents::CalculateBetweennessCentralityHeuristic() {
119
    cout << "BETWEENNESS CENTRALITY HEURISTIC\n";
120 437fd680 Quynh PX Nguyen
121 162e1bda Quynh PX Nguyen
    initialize_betweenness_centrality_heuristic();
122
    calculate_bc_inter();
123 437fd680 Quynh PX Nguyen
124 20756421 Quynh PX Nguyen
    for (int i = 0; i < num_of_bcc_; ++i) {
125 162e1bda Quynh PX Nguyen
        BCCs[i].CalculateBetweennessCentralityHeuristic();
126 20756421 Quynh PX Nguyen
    }
127 437fd680 Quynh PX Nguyen
128
    double score;
129
    for (int i = 0; i < num_of_bcc_; ++i) {
130 162e1bda Quynh PX Nguyen
        // For all points
131
        for (string id: BCCs[i].all_vertices_id()) {
132 437fd680 Quynh PX Nguyen
            score = BCCs[i].get_betweenness_centrality(id);
133 162e1bda Quynh PX Nguyen
            bc_score_[id] += score;
134 437fd680 Quynh PX Nguyen
        }
135
    }
136
137 e263e3c7 Quynh PX Nguyen
    // Update the BC score for articulation points
138 6575aa2e Quynh PX Nguyen
    for (string id : all_art_points_id_) {
139
        bc_score_[id] -= bc_inter_[id];
140
    }
141 437fd680 Quynh PX Nguyen
142 162e1bda Quynh PX Nguyen
    finalize_betweenness_centrality_heuristic();
143
144 437fd680 Quynh PX Nguyen
    cout << "DONE WITH BETWEENNESS CENTRALITY\n";
145 20756421 Quynh PX Nguyen
}
146
147 162e1bda Quynh PX Nguyen
// BETWEENNESS CENTRALITY - NORMAL CALCULATION
148 33e5ad95 Quynh PX Nguyen
void BiConnectedComponents::CalculateBetweennessCentrality(bool endpoints_inclusion) {
149 162e1bda Quynh PX Nguyen
    initialize_betweenness_centrality();
150 ee0dd796 Quynh PX Nguyen
151 d5b7a27f Quynh PX Nguyen
    if (gm_.weighted_graph()) { // calculate BC for weighted graph
152
        cout << "======= BCC - BC for weighted graph ======\n";
153
154 e263e3c7 Quynh PX Nguyen
        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 33e5ad95 Quynh PX Nguyen
        boost::brandes_betweenness_centrality_endpoints_inclusion(gm_.g_,
163
            endpoints_inclusion,
164 e263e3c7 Quynh PX Nguyen
            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 33e5ad95 Quynh PX Nguyen
        boost::brandes_betweenness_centrality_endpoints_inclusion(gm_.g_,
172
            endpoints_inclusion,
173 e263e3c7 Quynh PX Nguyen
            boost::centrality_map(
174
                v_centrality_pmap_).vertex_index_map(
175
                gm_.v_index_pmap())
176
        );
177
    }
178 437fd680 Quynh PX Nguyen
179 162e1bda Quynh PX Nguyen
    boost::relative_betweenness_centrality(gm_.g_, v_centrality_pmap_);
180
}
181
182
// HELPERS FOR OUTPUTTING RESULT
183
void BiConnectedComponents::print_all_sub_components() {
184 e263e3c7 Quynh PX Nguyen
    for (int i = 0; i < num_of_bcc_; ++i) {
185 162e1bda Quynh PX Nguyen
        // cout << BCCs[i]; // Since I call another print() function inside, I cannot use cout
186
        BCCs[i].print();
187 437fd680 Quynh PX Nguyen
    }
188
}
189
190 d5b7a27f Quynh PX Nguyen
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 162e1bda Quynh PX Nguyen
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 437fd680 Quynh PX Nguyen
    }
206 ee0dd796 Quynh PX Nguyen
}
207
208 162e1bda Quynh PX Nguyen
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 437fd680 Quynh PX Nguyen
218 162e1bda Quynh PX Nguyen
    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 d5b7a27f Quynh PX Nguyen
            outFile << id << "\t" << setprecision(4) << fixed << bc_score << "\t" << heuristic_bc_score << endl;
234 162e1bda Quynh PX Nguyen
        }
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 cb770240 Quynh PX Nguyen
    }
241 162e1bda Quynh PX Nguyen
    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 d5b7a27f Quynh PX Nguyen
    print_biconnected_components();
250 e263e3c7 Quynh PX Nguyen
251 162e1bda Quynh PX Nguyen
    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 cb770240 Quynh PX Nguyen
}
260 ee0dd796 Quynh PX Nguyen
261 cb770240 Quynh PX Nguyen
std::ostream& operator<<(std::ostream& os, const BiConnectedComponents& rhs) {
262
    cout << "\n\nBi-Connected Components\n\n";
263
    cout << rhs.gm_;
264 ee0dd796 Quynh PX Nguyen
265 cb770240 Quynh PX Nguyen
    cout << "\nArticulation points:\n";
266
    outops::operator<<(cout, rhs.all_art_points_id());
267 437fd680 Quynh PX Nguyen
268 162e1bda Quynh PX Nguyen
    cout << "\nHeuristic Betweenness Centrality Score:\n";
269 437fd680 Quynh PX Nguyen
    outops::operator<< <double>(cout, rhs.bc_score());
270 ee0dd796 Quynh PX Nguyen
271 162e1bda Quynh PX Nguyen
    cout << "\nHeuristic Betweenness Centrality Relative Score:\n";
272
    outops::operator<< <double>(cout, rhs.bc_relative_score());
273
274
    return os;
275 ee0dd796 Quynh PX Nguyen
}
276
277 cb770240 Quynh PX Nguyen
/******************************
278
* Private functions
279
******************************/
280 162e1bda Quynh PX Nguyen
// SUB-COMPONENT
281 e263e3c7 Quynh PX Nguyen
void BiConnectedComponents::reset_num_of_bcc() {
282
    num_of_bcc_ = *std::max_element(component_vec_.begin(), component_vec_.end()) + 1;
283
}
284
285 162e1bda Quynh PX Nguyen
void BiConnectedComponents::CreateSubComponents() {
286 d5b7a27f Quynh PX Nguyen
    for (int i = 0; i < num_of_bcc_; ++i) {
287
        BCCs.push_back(SubComponent(gm_.weighted_graph()));
288
    }
289
290 162e1bda Quynh PX Nguyen
    // 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 e263e3c7 Quynh PX Nguyen
        cout << comp_index << " ";
297
298 162e1bda Quynh PX Nguyen
        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 e263e3c7 Quynh PX Nguyen
            if (r1 != r2) { // Do not add self-loop edge
308
                BCCs[comp_index].AddEdge(r1, r2, l);
309
            }
310 162e1bda Quynh PX Nguyen
        }
311
    }
312
313
    // Finalizing each sub components
314 e263e3c7 Quynh PX Nguyen
    for (int i = 0; i < num_of_bcc_; ++i) {
315 162e1bda Quynh PX Nguyen
        BCCs[i].FinalizeSubComponent(all_art_points_id_);
316
    }
317
}
318 ee0dd796 Quynh PX Nguyen
319 162e1bda Quynh PX Nguyen
// LINK WEIGHT
320 cb770240 Quynh PX Nguyen
void BiConnectedComponents::initialize_weight() {
321
    for (int i = 0; i < num_of_bcc_; ++i) {
322
        BCCs[i].initialize_weight();
323 ee0dd796 Quynh PX Nguyen
    }
324
}
325
326 cb770240 Quynh PX Nguyen
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 d5b7a27f Quynh PX Nguyen
            // cout << "adding component_vertex_pair (" << i << " " << vertex_id << ")\n";
337 cb770240 Quynh PX Nguyen
            Q.push(elem);
338
        }
339 ee0dd796 Quynh PX Nguyen
    }
340
}
341
342 cb770240 Quynh PX Nguyen
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 ee0dd796 Quynh PX Nguyen
            }
350
        }
351
    }
352 cb770240 Quynh PX Nguyen
    int link_weight = size;
353 162e1bda Quynh PX Nguyen
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 e263e3c7 Quynh PX Nguyen
            cout << "ERROR in Link Weight for comp " << comp_index << " | vertex " << vertex_id << old_link_weight << " | " << link_weight << endl;
358 162e1bda Quynh PX Nguyen
        }
359
    }
360
361 cb770240 Quynh PX Nguyen
    BCCs[comp_index].update_weight_map(vertex_id, link_weight);
362 d5b7a27f Quynh PX Nguyen
    // cout << "  update weight for comp " << comp_index << " | vertex " << vertex_id << " = " << link_weight << endl;
363 cb770240 Quynh PX Nguyen
    find_unknown_weight_wrt_art_point(vertex_id);
364 ee0dd796 Quynh PX Nguyen
}
365
366 cb770240 Quynh PX Nguyen
void BiConnectedComponents::find_unknown_weight_wrt_art_point(string vertex_id) {
367
    int count = 0;
368
    int comp_index = -1;
369 e263e3c7 Quynh PX Nguyen
    // cout << "find_unknown_weight_wrt_art_point " << vertex_id << "\n";
370 162e1bda Quynh PX Nguyen
371 cb770240 Quynh PX Nguyen
    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 e263e3c7 Quynh PX Nguyen
                // cout << "     comp_index = " << i << endl;
375 cb770240 Quynh PX Nguyen
                ++count;
376
                comp_index = i;
377
            }
378 ee0dd796 Quynh PX Nguyen
379 cb770240 Quynh PX Nguyen
            if (count > 1) break;
380 ee0dd796 Quynh PX Nguyen
        }
381
    }
382
383 cb770240 Quynh PX Nguyen
    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 ee0dd796 Quynh PX Nguyen
391 e263e3c7 Quynh PX Nguyen
        // cout << "        Add vertex_component_pair: " << comp_index << " - " << vertex_id << endl;
392 cb770240 Quynh PX Nguyen
        Q.push(elem);
393 ee0dd796 Quynh PX Nguyen
    }
394
}
395
396 cb770240 Quynh PX Nguyen
void BiConnectedComponents::process_vertex_component_pair(int comp_index, string vertex_id) {
397
    int size = 0;
398 ee0dd796 Quynh PX Nguyen
399 cb770240 Quynh PX Nguyen
    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 ee0dd796 Quynh PX Nguyen
410 cb770240 Quynh PX Nguyen
    int link_weight = num_of_vertices_ - 1 - size;
411 162e1bda Quynh PX Nguyen
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 e263e3c7 Quynh PX Nguyen
            cout << "ERROR in Link Weight for comp " << comp_index << " | vertex " << vertex_id << old_link_weight << " | " << link_weight << endl;
416 162e1bda Quynh PX Nguyen
        }
417
    }
418
419 cb770240 Quynh PX Nguyen
    BCCs[comp_index].update_weight_map(vertex_id, link_weight);
420 4ca27bae Quynh PX Nguyen
    // cout << "  update weight for vertex_component pair: " << comp_index << " | " << vertex_id << " = " << link_weight << endl;
421 cb770240 Quynh PX Nguyen
    find_unknown_weight_wrt_component(comp_index);
422 ee0dd796 Quynh PX Nguyen
}
423
424 cb770240 Quynh PX Nguyen
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 e263e3c7 Quynh PX Nguyen
        // cout << "Add component_vertex_pair: " << comp_index << " - " << vertex_id << endl;
442 cb770240 Quynh PX Nguyen
        Q.push(elem);
443
    }
444 162e1bda Quynh PX Nguyen
}
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 4ca27bae Quynh PX Nguyen
                cout << "ERROR Link Weight for vertex " << id << " in component " << i << " = " << -1 << endl;
454 162e1bda Quynh PX Nguyen
                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 33e5ad95 Quynh PX Nguyen
484
    if (!gm_.weighted_graph()) {
485
        for (string id : all_art_points_id_) {
486
            bc_inter_[id] /= 2;
487
        }
488
    }
489 162e1bda Quynh PX Nguyen
}
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 cb770240 Quynh PX Nguyen
}