Statistics
| Branch: | Revision:

root / custompackages / graph-parser / src / bi_connected_components.cpp @ 437fd680

History | View | Annotate | Download (9.87 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_), 0);
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
/* SUB-COMPONENT */
48
void BiConnectedComponents::FindBiConnectedComponents() {
49
    cout << "Running FindBiConnectedComponents" << endl;
50

    
51
    boost::biconnected_components(gm_.g_, component_map_,
52
                                  back_inserter(art_points_),
53
                                  boost::vertex_index_map(gm_.v_index_pmap()));
54

    
55
    // Set some variables
56
    graphext::id_of_some_vertices(gm_.g_, art_points_, all_art_points_id_);
57

    
58
    // Process the result from boost::biconnected_components
59
    BCCs = Component_t(num_of_bcc());
60
    CreateSubComponents();
61

    
62
    // Calculate Link Weight
63
    cout << "Calculate Link Weight\n";
64
    CalculateLinkWeight();
65

    
66
    // Calculate Traffic Matrix
67
    cout << "Calculate Traffic Matrix\n";
68
    CalculateTrafficMatrix();
69

    
70
    // Calculate Betweenness Centrality
71
    cout << "Calculate Betweenness Centrality\n";
72
    CalculateBetweennessCentrality();
73

    
74
    // Print all the sub components
75
    print();
76
}
77

    
78
void BiConnectedComponents::CreateSubComponents() {
79
    // Generating subgraph for each sub-component
80
    BGL_FORALL_EDGES(edge, gm_.g_, Graph) {
81
        int comp_index = boost::get(component_map_, edge);
82
        Router r1 = gm_.g_[boost::source(edge, gm_.g_)];
83
        Router r2 = gm_.g_[boost::target(edge, gm_.g_)];
84
        Link l = gm_.g_[edge];
85
        BCCs[comp_index].AddEdge(r1, r2, l);
86
    }
87

    
88
    // Finalizing each sub components
89
    for (int i = 0; i < num_of_bcc(); ++i) {
90
        BCCs[i].FinalizeSubComponent(all_art_points_id_);
91
    }
92
}
93

    
94
/* LINK WEIGHT */
95
void BiConnectedComponents::CalculateLinkWeight() {
96
    initialize_weight();
97
    initialize_queue();
98

    
99
    while (!Q.empty()) {
100
        QueueElem elem = Q.front();
101
        Q.pop();
102
        int comp_index = elem.component_index;
103
        string vertex_id = elem.vertex_id;
104

    
105
        if (elem.type == "component_vertex_pair") {
106
            // cout << "component_vertex_pair: " << comp_index << " - " << vertex_id << endl;
107
            process_component_vertex_pair(comp_index, vertex_id);
108
        }
109
        else if (elem.type == "vertex_component_pair") {
110
            // cout << "vertex_component_pair: " << comp_index << " - " << vertex_id << endl;
111
            process_vertex_component_pair(comp_index, vertex_id);
112
        }
113
    }
114
}
115

    
116
/* TRAFFIC MATRIX */
117
void BiConnectedComponents::CalculateTrafficMatrix() {
118
    for (int i = 0; i < num_of_bcc_; ++i) {
119
        BCCs[i].CalculateTrafficMatrix();
120
    }
121
}
122

    
123
/* BETWEENNESS CENTRALITY */
124
void BiConnectedComponents::CalculateBetweennessCentrality() {
125
    cout << "BETWEENNESS CENTRALITY\n";
126

    
127
    initialize_betweenness_centrality();
128

    
129
    for (int i = 0; i < num_of_bcc_; ++i) {
130
        cout << "BC for component " << i << endl;
131
        BCCs[i].CalculateBetweennessCentrality();
132
    }
133

    
134
    double score;
135
    // Sum the BC for each sub-component
136
    for (int i = 0; i < num_of_bcc_; ++i) {
137
        // For non articulation points
138
        for (string id: BCCs[i].non_art_points_id()) {
139
            score = BCCs[i].get_betweenness_centrality(id);
140
            cout << "id = " << id << ", score = " << score << endl;
141
            bc_score_[id] = score;
142
        }
143

    
144
        // For articulation points
145
        for (string id: BCCs[i].art_points_id()) {
146
            score = BCCs[i].get_betweenness_centrality(id);
147
            bc_sum_art_points_[id] += score;
148
        }
149
    }
150

    
151
    // Update the BC score for articulation points
152
    for (string id : all_art_points_id_) {
153
        bc_score_[id] = bc_sum_art_points_[id];
154

    
155
        // TODO: Jan 29, 2015: for now, I do not minus the bc_inter_
156
        // bc_score_[id] = bc_sum_art_points_[id] - bc_inter_[id];
157
    }
158

    
159
    cout << "DONE WITH BETWEENNESS CENTRALITY\n";
160
}
161

    
162
void BiConnectedComponents::initialize_betweenness_centrality() {
163
    // Initialize bc_inter_ to be 0
164
    for (string id: all_art_points_id_) {
165
        bc_inter_[id] = 0;
166
    }
167

    
168
    StringSet all_vertices_id;
169
    graphext::id_of_all_vertices(gm_.g_, all_vertices_id);
170

    
171
    // Initialize bc_sum_, bc_score_ to be 0
172
    for (string id: all_vertices_id) {
173
        bc_sum_art_points_[id] = 0;
174
        bc_score_[id] = 0;
175
    }
176
}
177

    
178
void BiConnectedComponents::calculate_bc_inter() {
179
    for (int i = 0; i < num_of_bcc_; ++i) {
180
        for (string id : BCCs[i].art_points_id()) {
181
            bc_inter_[id] += BCCs[i].get_weight_map(id) * BCCs[i].get_weight_reversed_map(id);
182
        }
183
    }
184
}
185

    
186
/* HELPERS FOR OUTPUTTING RESULT */
187

    
188
void BiConnectedComponents::print() {
189
    for (int i = 0; i < num_of_bcc(); ++i) {
190
        // cout << BCCs[i]; // Since I call another print() function inside, I cannot use cout
191
        BCCs[i].print();
192
    }
193
}
194

    
195
std::ostream& operator<<(std::ostream& os, const BiConnectedComponents& rhs) {
196
    cout << "MARK\n";
197
    cout << "\n\nBi-Connected Components\n\n";
198
    cout << rhs.gm_;
199

    
200
    cout << "\nArticulation points:\n";
201
    outops::operator<<(cout, rhs.all_art_points_id());
202

    
203
    cout << "\nBetweenness Centrality Score:\n";
204
    outops::operator<< <double>(cout, rhs.bc_score());
205
    return os;
206

    
207
    // TODO: output the result of BCC
208
    // Test the biconnected components
209
    // Eiter ei, ei_end;
210
    // size_t i = 0;
211
    // for (boost::tie(ei, ei_end) = boost::edges(gm_.g_); ei != ei_end; ++ei) {
212
    //     string source = gm_.g_[(*ei).m_source].id;
213
    //     string target = gm_.g_[(*ei).m_target].id;
214
    //     edges_size_type comp = component_vec_.at(i);
215
    //     cout << source << " " << target << " " << comp << endl;
216
    //     ++i;
217
    // }
218
}
219

    
220
/******************************
221
* Private functions
222
******************************/
223

    
224
/* LINK WEIGHT */
225
void BiConnectedComponents::initialize_weight() {
226
    for (int i = 0; i < num_of_bcc_; ++i) {
227
        BCCs[i].initialize_weight();
228
    }
229
}
230

    
231
void BiConnectedComponents::initialize_queue() {
232
    for (int i = 0; i < num_of_bcc_; ++i) {
233
        if (BCCs[i].art_points_id().size() == 1) {
234
            string vertex_id = *(BCCs[i].art_points_id().begin());
235
            string type = "component_vertex_pair";
236
            QueueElem elem = {
237
                .component_index = i,
238
                .vertex_id = vertex_id,
239
                .type = type,
240
            };
241

    
242
            Q.push(elem);
243
        }
244
    }
245
}
246

    
247
void BiConnectedComponents::process_component_vertex_pair(int comp_index, string vertex_id) {
248
    int size = BCCs[comp_index].num_of_vertices() - 1;
249
    for (string s : BCCs[comp_index].art_points_id()) {
250
        if (s.compare(vertex_id) != 0) {
251
            int weight = BCCs[comp_index].get_weight_map(s);
252
            if (weight != -1) {
253
                size += num_of_vertices_ - weight - 1;
254
            }
255
        }
256
    }
257
    int link_weight = size;
258
    BCCs[comp_index].update_weight_map(vertex_id, link_weight);
259
    find_unknown_weight_wrt_art_point(vertex_id);
260
}
261

    
262
void BiConnectedComponents::find_unknown_weight_wrt_art_point(string vertex_id) {
263
    int count = 0;
264
    int comp_index = -1;
265
    for (int i = 0; i < num_of_bcc_; ++i) {
266
        if (BCCs[i].vertex_exists(vertex_id)) {
267
            if (BCCs[i].get_weight_map(vertex_id) == -1) {
268
                ++count;
269
                comp_index = i;
270
            }
271

    
272
            if (count > 1) break;
273
        }
274
    }
275

    
276
    if (count == 1) {
277
        // Add new element to QueueElem
278
        QueueElem elem = {
279
            .component_index = comp_index,
280
            .vertex_id = vertex_id,
281
            .type = "vertex_component_pair"
282
        };
283

    
284
        // cout << "Add vertex_component_pair: " << comp_index << " - " << vertex_id << endl;
285
        Q.push(elem);
286
    }
287
}
288

    
289
void BiConnectedComponents::process_vertex_component_pair(int comp_index, string vertex_id) {
290
    int size = 0;
291

    
292
    for (int i = 0; i < num_of_bcc_; ++i) {
293
        if (i != comp_index) {
294
            if (BCCs[i].vertex_exists(vertex_id)) {
295
                int weight = BCCs[i].get_weight_map(vertex_id);
296
                if (weight != -1) {
297
                    size += weight;
298
                }
299
            }
300
        }
301
    }
302

    
303
    int link_weight = num_of_vertices_ - 1 - size;
304
    BCCs[comp_index].update_weight_map(vertex_id, link_weight);
305
    find_unknown_weight_wrt_component(comp_index);
306
}
307

    
308
void BiConnectedComponents::find_unknown_weight_wrt_component(int comp_index) {
309
    // The 'counting' solution is found here: http://stackoverflow.com/questions/5517615/counting-number-of-same-values-in-map
310
    typedef NameToIntMap::value_type MapEntry;
311
    int count = std::count_if(
312
        BCCs[comp_index].weight_map().begin(),
313
        BCCs[comp_index].weight_map().end(),
314
        second_equal_to<MapEntry>(-1));
315

    
316
    if (count == 1) {
317
        // Find the vertex id for the vertex with unknown link weight
318
        string vertex_id = BCCs[comp_index].first_vertex_id_with_unknown_weight();
319

    
320
        QueueElem elem = {
321
            .component_index = comp_index,
322
            .vertex_id = vertex_id,
323
            .type = "component_vertex_pair",
324
        };
325
        // cout << "Add component_vertex_pair: " << comp_index << " - " << vertex_id << endl;
326
        Q.push(elem);
327
    }
328
}