Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (17 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 e263e3c7 Quynh PX Nguyen
        // cout << "BC for component " << i << endl;
126 162e1bda Quynh PX Nguyen
        BCCs[i].CalculateBetweennessCentralityHeuristic();
127 20756421 Quynh PX Nguyen
    }
128 437fd680 Quynh PX Nguyen
129
    double score;
130
    for (int i = 0; i < num_of_bcc_; ++i) {
131 162e1bda Quynh PX Nguyen
        // For all points
132
        for (string id: BCCs[i].all_vertices_id()) {
133 437fd680 Quynh PX Nguyen
            score = BCCs[i].get_betweenness_centrality(id);
134 e263e3c7 Quynh PX Nguyen
            // cout << "XXX score from component << " << i << ", id " << id << " = " << score << endl;
135 162e1bda Quynh PX Nguyen
            bc_score_[id] += score;
136 437fd680 Quynh PX Nguyen
        }
137
    }
138
139 162e1bda Quynh PX Nguyen
    // // 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 e263e3c7 Quynh PX Nguyen
    // Update the BC score for articulation points
155 6575aa2e Quynh PX Nguyen
    for (string id : all_art_points_id_) {
156
    //     bc_score_[id] = bc_sum_art_points_[id];
157 437fd680 Quynh PX Nguyen
158 6575aa2e Quynh PX Nguyen
        // 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 e263e3c7 Quynh PX Nguyen
    //     cout << bc_score_[id] << endl;
162 6575aa2e Quynh PX Nguyen
    }
163 437fd680 Quynh PX Nguyen
164 162e1bda Quynh PX Nguyen
    finalize_betweenness_centrality_heuristic();
165
166 437fd680 Quynh PX Nguyen
    cout << "DONE WITH BETWEENNESS CENTRALITY\n";
167 20756421 Quynh PX Nguyen
}
168
169 162e1bda Quynh PX Nguyen
// BETWEENNESS CENTRALITY - NORMAL CALCULATION
170 d5b7a27f Quynh PX Nguyen
void BiConnectedComponents::CalculateBetweennessCentrality(bool targets_inclusion) {
171 162e1bda Quynh PX Nguyen
    initialize_betweenness_centrality();
172 ee0dd796 Quynh PX Nguyen
173 d5b7a27f Quynh PX Nguyen
    if (gm_.weighted_graph()) { // calculate BC for weighted graph
174
        cout << "======= BCC - BC for weighted graph ======\n";
175
176 e263e3c7 Quynh PX Nguyen
        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 d5b7a27f Quynh PX Nguyen
        boost::brandes_betweenness_centrality_targets_inclusion(gm_.g_,
185
            targets_inclusion,
186 e263e3c7 Quynh PX Nguyen
            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 d5b7a27f Quynh PX Nguyen
        boost::brandes_betweenness_centrality_targets_inclusion(gm_.g_,
194
            targets_inclusion,
195 e263e3c7 Quynh PX Nguyen
            boost::centrality_map(
196
                v_centrality_pmap_).vertex_index_map(
197
                gm_.v_index_pmap())
198
        );
199
    }
200 437fd680 Quynh PX Nguyen
201 162e1bda Quynh PX Nguyen
    boost::relative_betweenness_centrality(gm_.g_, v_centrality_pmap_);
202
}
203
204
// HELPERS FOR OUTPUTTING RESULT
205
void BiConnectedComponents::print_all_sub_components() {
206 e263e3c7 Quynh PX Nguyen
    for (int i = 0; i < num_of_bcc_; ++i) {
207 162e1bda Quynh PX Nguyen
        // cout << BCCs[i]; // Since I call another print() function inside, I cannot use cout
208
        BCCs[i].print();
209 437fd680 Quynh PX Nguyen
    }
210
}
211
212 d5b7a27f Quynh PX Nguyen
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 162e1bda Quynh PX Nguyen
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 437fd680 Quynh PX Nguyen
    }
228 ee0dd796 Quynh PX Nguyen
}
229
230 162e1bda Quynh PX Nguyen
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 437fd680 Quynh PX Nguyen
240 162e1bda Quynh PX Nguyen
    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 d5b7a27f Quynh PX Nguyen
            outFile << id << "\t" << setprecision(4) << fixed << bc_score << "\t" << heuristic_bc_score << endl;
256 162e1bda Quynh PX Nguyen
        }
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 cb770240 Quynh PX Nguyen
    }
263 162e1bda Quynh PX Nguyen
    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 d5b7a27f Quynh PX Nguyen
    print_biconnected_components();
272 e263e3c7 Quynh PX Nguyen
273 162e1bda Quynh PX Nguyen
    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 cb770240 Quynh PX Nguyen
}
282 ee0dd796 Quynh PX Nguyen
283 cb770240 Quynh PX Nguyen
std::ostream& operator<<(std::ostream& os, const BiConnectedComponents& rhs) {
284
    cout << "\n\nBi-Connected Components\n\n";
285
    cout << rhs.gm_;
286 ee0dd796 Quynh PX Nguyen
287 cb770240 Quynh PX Nguyen
    cout << "\nArticulation points:\n";
288
    outops::operator<<(cout, rhs.all_art_points_id());
289 437fd680 Quynh PX Nguyen
290 162e1bda Quynh PX Nguyen
    cout << "\nHeuristic Betweenness Centrality Score:\n";
291 437fd680 Quynh PX Nguyen
    outops::operator<< <double>(cout, rhs.bc_score());
292 ee0dd796 Quynh PX Nguyen
293 162e1bda Quynh PX Nguyen
    cout << "\nHeuristic Betweenness Centrality Relative Score:\n";
294
    outops::operator<< <double>(cout, rhs.bc_relative_score());
295
296
    return os;
297 ee0dd796 Quynh PX Nguyen
}
298
299 cb770240 Quynh PX Nguyen
/******************************
300
* Private functions
301
******************************/
302 162e1bda Quynh PX Nguyen
// SUB-COMPONENT
303 e263e3c7 Quynh PX Nguyen
void BiConnectedComponents::reset_num_of_bcc() {
304
    num_of_bcc_ = *std::max_element(component_vec_.begin(), component_vec_.end()) + 1;
305
}
306
307 162e1bda Quynh PX Nguyen
void BiConnectedComponents::CreateSubComponents() {
308 d5b7a27f Quynh PX Nguyen
    for (int i = 0; i < num_of_bcc_; ++i) {
309
        BCCs.push_back(SubComponent(gm_.weighted_graph()));
310
    }
311
312 162e1bda Quynh PX Nguyen
    // 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 e263e3c7 Quynh PX Nguyen
        cout << comp_index << " ";
319
320 162e1bda Quynh PX Nguyen
        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 e263e3c7 Quynh PX Nguyen
            if (r1 != r2) { // Do not add self-loop edge
330
                BCCs[comp_index].AddEdge(r1, r2, l);
331
            }
332 162e1bda Quynh PX Nguyen
        }
333
    }
334
335
    // Finalizing each sub components
336 e263e3c7 Quynh PX Nguyen
    for (int i = 0; i < num_of_bcc_; ++i) {
337 162e1bda Quynh PX Nguyen
        BCCs[i].FinalizeSubComponent(all_art_points_id_);
338
    }
339
}
340 ee0dd796 Quynh PX Nguyen
341 162e1bda Quynh PX Nguyen
// LINK WEIGHT
342 cb770240 Quynh PX Nguyen
void BiConnectedComponents::initialize_weight() {
343
    for (int i = 0; i < num_of_bcc_; ++i) {
344
        BCCs[i].initialize_weight();
345 ee0dd796 Quynh PX Nguyen
    }
346
}
347
348 cb770240 Quynh PX Nguyen
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 d5b7a27f Quynh PX Nguyen
            // cout << "adding component_vertex_pair (" << i << " " << vertex_id << ")\n";
359 cb770240 Quynh PX Nguyen
            Q.push(elem);
360
        }
361 ee0dd796 Quynh PX Nguyen
    }
362
}
363
364 cb770240 Quynh PX Nguyen
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 ee0dd796 Quynh PX Nguyen
            }
372
        }
373
    }
374 cb770240 Quynh PX Nguyen
    int link_weight = size;
375 162e1bda Quynh PX Nguyen
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 e263e3c7 Quynh PX Nguyen
            cout << "ERROR in Link Weight for comp " << comp_index << " | vertex " << vertex_id << old_link_weight << " | " << link_weight << endl;
380 162e1bda Quynh PX Nguyen
        }
381
    }
382
383 cb770240 Quynh PX Nguyen
    BCCs[comp_index].update_weight_map(vertex_id, link_weight);
384 d5b7a27f Quynh PX Nguyen
    // cout << "  update weight for comp " << comp_index << " | vertex " << vertex_id << " = " << link_weight << endl;
385 cb770240 Quynh PX Nguyen
    find_unknown_weight_wrt_art_point(vertex_id);
386 ee0dd796 Quynh PX Nguyen
}
387
388 cb770240 Quynh PX Nguyen
void BiConnectedComponents::find_unknown_weight_wrt_art_point(string vertex_id) {
389
    int count = 0;
390
    int comp_index = -1;
391 e263e3c7 Quynh PX Nguyen
    // cout << "find_unknown_weight_wrt_art_point " << vertex_id << "\n";
392 162e1bda Quynh PX Nguyen
393 cb770240 Quynh PX Nguyen
    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 e263e3c7 Quynh PX Nguyen
                // cout << "     comp_index = " << i << endl;
397 cb770240 Quynh PX Nguyen
                ++count;
398
                comp_index = i;
399
            }
400 ee0dd796 Quynh PX Nguyen
401 cb770240 Quynh PX Nguyen
            if (count > 1) break;
402 ee0dd796 Quynh PX Nguyen
        }
403
    }
404
405 cb770240 Quynh PX Nguyen
    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 ee0dd796 Quynh PX Nguyen
413 e263e3c7 Quynh PX Nguyen
        // cout << "        Add vertex_component_pair: " << comp_index << " - " << vertex_id << endl;
414 cb770240 Quynh PX Nguyen
        Q.push(elem);
415 ee0dd796 Quynh PX Nguyen
    }
416
}
417
418 cb770240 Quynh PX Nguyen
void BiConnectedComponents::process_vertex_component_pair(int comp_index, string vertex_id) {
419
    int size = 0;
420 ee0dd796 Quynh PX Nguyen
421 cb770240 Quynh PX Nguyen
    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 ee0dd796 Quynh PX Nguyen
432 cb770240 Quynh PX Nguyen
    int link_weight = num_of_vertices_ - 1 - size;
433 162e1bda Quynh PX Nguyen
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 e263e3c7 Quynh PX Nguyen
            cout << "ERROR in Link Weight for comp " << comp_index << " | vertex " << vertex_id << old_link_weight << " | " << link_weight << endl;
438 162e1bda Quynh PX Nguyen
        }
439
    }
440
441 cb770240 Quynh PX Nguyen
    BCCs[comp_index].update_weight_map(vertex_id, link_weight);
442 4ca27bae Quynh PX Nguyen
    // cout << "  update weight for vertex_component pair: " << comp_index << " | " << vertex_id << " = " << link_weight << endl;
443 cb770240 Quynh PX Nguyen
    find_unknown_weight_wrt_component(comp_index);
444 ee0dd796 Quynh PX Nguyen
}
445
446 cb770240 Quynh PX Nguyen
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 e263e3c7 Quynh PX Nguyen
        // cout << "Add component_vertex_pair: " << comp_index << " - " << vertex_id << endl;
464 cb770240 Quynh PX Nguyen
        Q.push(elem);
465
    }
466 162e1bda Quynh PX Nguyen
}
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 4ca27bae Quynh PX Nguyen
                cout << "ERROR Link Weight for vertex " << id << " in component " << i << " = " << -1 << endl;
476 162e1bda Quynh PX Nguyen
                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 cb770240 Quynh PX Nguyen
}