Statistics
| Branch: | Revision:

root / custompackages / graph-parser / src / bi_connected_components.cpp @ 20756421

History | View | Annotate | Download (7.76 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
BiConnectedComponents::BiConnectedComponents(GraphManager &gm) : gm_(gm) {
12
    cout << "BCC constructor \n";
13 ee0dd796 Quynh PX Nguyen
    init();
14 cb770240 Quynh PX Nguyen
    FindBiConnectedComponents();
15 ee0dd796 Quynh PX Nguyen
}
16
17
void BiConnectedComponents::init() {
18 cb770240 Quynh PX Nguyen
    // Set some variables
19
    num_of_vertices_ = boost::num_vertices(gm_.g_);
20 ee0dd796 Quynh PX Nguyen
21 cb770240 Quynh PX Nguyen
    component_vec_ = ComponentVec(boost::num_edges(gm_.g_), 0);
22
    component_map_ = ComponentMap(component_vec_.begin(), gm_.e_index_map());
23 ee0dd796 Quynh PX Nguyen
}
24
25 cb770240 Quynh PX Nguyen
/* GETTER */
26
StringSet const& BiConnectedComponents::all_art_points_id() const {
27
    return all_art_points_id_;
28
}
29 ee0dd796 Quynh PX Nguyen
30 cb770240 Quynh PX Nguyen
/* SUB-COMPONENT */
31
void BiConnectedComponents::FindBiConnectedComponents() {
32
    cout << "Running FindBiConnectedComponents" << endl;
33 ee0dd796 Quynh PX Nguyen
34 cb770240 Quynh PX Nguyen
    boost::biconnected_components(gm_.g_, component_map_,
35
                                  back_inserter(art_points_),
36
                                  boost::vertex_index_map(gm_.v_index_map()));
37 ee0dd796 Quynh PX Nguyen
38 cb770240 Quynh PX Nguyen
    // Set some variables
39
    graphext::id_of_some_vertices(gm_.g_, art_points_, all_art_points_id_);
40 ee0dd796 Quynh PX Nguyen
41
    // Process the result from boost::biconnected_components
42 cb770240 Quynh PX Nguyen
    BCCs = Component_t(num_of_bcc());
43
    CreateSubComponents();
44 ee0dd796 Quynh PX Nguyen
45 cb770240 Quynh PX Nguyen
    // Calculate Link Weight
46
    cout << "Calculate Link Weight\n";
47
    CalculateLinkWeight();
48 ee0dd796 Quynh PX Nguyen
49 cb770240 Quynh PX Nguyen
    // Calculate Traffic Matrix
50
    cout << "Calculate Traffic Matrix\n";
51
    CalculateTrafficMatrix();
52 ee0dd796 Quynh PX Nguyen
53 20756421 Quynh PX Nguyen
    // Calculate Betweenness Centrality
54
    cout << "Calculate Betweenness Centrality\n";
55
    CalculateBetweennessCentrality();
56
57 cb770240 Quynh PX Nguyen
    print();
58
}
59
60
void BiConnectedComponents::CreateSubComponents() {
61 efed924d Quynh PX Nguyen
    // Generating subgraph for each sub-component
62 cb770240 Quynh PX Nguyen
    BGL_FORALL_EDGES(edge, gm_.g_, Graph) {
63
        int comp_index = boost::get(component_map_, edge);
64
        Router r1 = gm_.g_[boost::source(edge, gm_.g_)];
65
        Router r2 = gm_.g_[boost::target(edge, gm_.g_)];
66
        Link l = gm_.g_[edge];
67 efed924d Quynh PX Nguyen
        BCCs[comp_index].AddEdge(r1, r2, l);
68 ee0dd796 Quynh PX Nguyen
    }
69
70 cb770240 Quynh PX Nguyen
    // Finalizing each sub components
71
    for (int i = 0; i < num_of_bcc(); ++i) {
72
        BCCs[i].FinalizeSubComponent(all_art_points_id_);
73 ee0dd796 Quynh PX Nguyen
    }
74
}
75
76 cb770240 Quynh PX Nguyen
/* LINK WEIGHT */
77
void BiConnectedComponents::CalculateLinkWeight() {
78
    initialize_weight();
79
    initialize_queue();
80
81
    while (!Q.empty()) {
82
        QueueElem elem = Q.front();
83
        Q.pop();
84
        int comp_index = elem.component_index;
85
        string vertex_id = elem.vertex_id;
86
87
        if (elem.type == "component_vertex_pair") {
88
            // cout << "component_vertex_pair: " << comp_index << " - " << vertex_id << endl;
89
            process_component_vertex_pair(comp_index, vertex_id);
90
        }
91
        else if (elem.type == "vertex_component_pair") {
92
            // cout << "vertex_component_pair: " << comp_index << " - " << vertex_id << endl;
93
            process_vertex_component_pair(comp_index, vertex_id);
94
        }
95 ee0dd796 Quynh PX Nguyen
    }
96
}
97
98 cb770240 Quynh PX Nguyen
/* TRAFFIC MATRIX */
99
void BiConnectedComponents::CalculateTrafficMatrix() {
100
    for (int i = 0; i < num_of_bcc_; ++i) {
101
        BCCs[i].CalculateTrafficMatrix();
102
    }
103
}
104
105 20756421 Quynh PX Nguyen
/* BETWEENNESS CENTRALITY */
106
void BiConnectedComponents::CalculateBetweennessCentrality() {
107
    for (int i = 0; i < num_of_bcc_; ++i) {
108
        BCCs[i].CalculateBetweennessCentrality();
109
    }
110
}
111
112 cb770240 Quynh PX Nguyen
/* HELPERS */
113
int BiConnectedComponents::num_of_bcc() {
114
    if (num_of_bcc_ == -1) { // calculate it
115 ee0dd796 Quynh PX Nguyen
        // +1 to counteract for the zero-indexing
116 cb770240 Quynh PX Nguyen
        num_of_bcc_ = *std::max_element(component_vec_.begin(), component_vec_.end()) + 1;
117 ee0dd796 Quynh PX Nguyen
    }
118
119 cb770240 Quynh PX Nguyen
    return num_of_bcc_;
120 ee0dd796 Quynh PX Nguyen
}
121
122 cb770240 Quynh PX Nguyen
/* HELPERS FOR OUTPUTTING RESULT */
123
void BiConnectedComponents::print() {
124
    for (int i = 0; i < num_of_bcc(); ++i) {
125
        cout << BCCs[i] << endl;
126
    }
127
}
128 ee0dd796 Quynh PX Nguyen
129 cb770240 Quynh PX Nguyen
std::ostream& operator<<(std::ostream& os, const BiConnectedComponents& rhs) {
130
    cout << "\n\nBi-Connected Components\n\n";
131
    cout << rhs.gm_;
132 ee0dd796 Quynh PX Nguyen
133 cb770240 Quynh PX Nguyen
    cout << "\nArticulation points:\n";
134
    outops::operator<<(cout, rhs.all_art_points_id());
135
    return os;
136 ee0dd796 Quynh PX Nguyen
137 cb770240 Quynh PX Nguyen
    // TODO: output the result of BCC
138
    // Test the biconnected components
139
    // Eiter ei, ei_end;
140
    // size_t i = 0;
141
    // for (boost::tie(ei, ei_end) = boost::edges(gm_.g_); ei != ei_end; ++ei) {
142
    //     string source = gm_.g_[(*ei).m_source].id;
143
    //     string target = gm_.g_[(*ei).m_target].id;
144
    //     edges_size_type comp = component_vec_.at(i);
145
    //     cout << source << " " << target << " " << comp << endl;
146
    //     ++i;
147
    // }
148 ee0dd796 Quynh PX Nguyen
}
149
150 cb770240 Quynh PX Nguyen
/******************************
151
* Private functions
152
******************************/
153 ee0dd796 Quynh PX Nguyen
154 cb770240 Quynh PX Nguyen
/* LINK WEIGHT */
155
void BiConnectedComponents::initialize_weight() {
156
    for (int i = 0; i < num_of_bcc_; ++i) {
157
        BCCs[i].initialize_weight();
158 ee0dd796 Quynh PX Nguyen
    }
159
}
160
161 cb770240 Quynh PX Nguyen
void BiConnectedComponents::initialize_queue() {
162
    for (int i = 0; i < num_of_bcc_; ++i) {
163
        if (BCCs[i].art_points_id().size() == 1) {
164
            string vertex_id = *(BCCs[i].art_points_id().begin());
165
            string type = "component_vertex_pair";
166
            QueueElem elem = {
167
                .component_index = i,
168
                .vertex_id = vertex_id,
169
                .type = type,
170
            };
171
172
            Q.push(elem);
173
        }
174 ee0dd796 Quynh PX Nguyen
    }
175
}
176
177 cb770240 Quynh PX Nguyen
void BiConnectedComponents::process_component_vertex_pair(int comp_index, string vertex_id) {
178
    int size = BCCs[comp_index].num_of_vertices() - 1;
179
    for (string s : BCCs[comp_index].art_points_id()) {
180
        if (s.compare(vertex_id) != 0) {
181
            int weight = BCCs[comp_index].get_weight_map(s);
182
            if (weight != -1) {
183
                size += num_of_vertices_ - weight - 1;
184 ee0dd796 Quynh PX Nguyen
            }
185
        }
186
    }
187 cb770240 Quynh PX Nguyen
    int link_weight = size;
188
    BCCs[comp_index].update_weight_map(vertex_id, link_weight);
189
    find_unknown_weight_wrt_art_point(vertex_id);
190 ee0dd796 Quynh PX Nguyen
}
191
192 cb770240 Quynh PX Nguyen
void BiConnectedComponents::find_unknown_weight_wrt_art_point(string vertex_id) {
193
    int count = 0;
194
    int comp_index = -1;
195
    for (int i = 0; i < num_of_bcc_; ++i) {
196
        if (BCCs[i].vertex_exists(vertex_id)) {
197
            if (BCCs[i].get_weight_map(vertex_id) == -1) {
198
                ++count;
199
                comp_index = i;
200
            }
201 ee0dd796 Quynh PX Nguyen
202 cb770240 Quynh PX Nguyen
            if (count > 1) break;
203 ee0dd796 Quynh PX Nguyen
        }
204
    }
205
206 cb770240 Quynh PX Nguyen
    if (count == 1) {
207
        // Add new element to QueueElem
208
        QueueElem elem = {
209
            .component_index = comp_index,
210
            .vertex_id = vertex_id,
211
            .type = "vertex_component_pair"
212
        };
213 ee0dd796 Quynh PX Nguyen
214 cb770240 Quynh PX Nguyen
        // cout << "Add vertex_component_pair: " << comp_index << " - " << vertex_id << endl;
215
        Q.push(elem);
216 ee0dd796 Quynh PX Nguyen
    }
217
}
218
219 cb770240 Quynh PX Nguyen
void BiConnectedComponents::process_vertex_component_pair(int comp_index, string vertex_id) {
220
    int size = 0;
221 ee0dd796 Quynh PX Nguyen
222 cb770240 Quynh PX Nguyen
    for (int i = 0; i < num_of_bcc_; ++i) {
223
        if (i != comp_index) {
224
            if (BCCs[i].vertex_exists(vertex_id)) {
225
                int weight = BCCs[i].get_weight_map(vertex_id);
226
                if (weight != -1) {
227
                    size += weight;
228
                }
229
            }
230
        }
231
    }
232 ee0dd796 Quynh PX Nguyen
233 cb770240 Quynh PX Nguyen
    int link_weight = num_of_vertices_ - 1 - size;
234
    BCCs[comp_index].update_weight_map(vertex_id, link_weight);
235
    find_unknown_weight_wrt_component(comp_index);
236 ee0dd796 Quynh PX Nguyen
}
237
238 cb770240 Quynh PX Nguyen
void BiConnectedComponents::find_unknown_weight_wrt_component(int comp_index) {
239
    // The 'counting' solution is found here: http://stackoverflow.com/questions/5517615/counting-number-of-same-values-in-map
240
    typedef NameToIntMap::value_type MapEntry;
241
    int count = std::count_if(
242
        BCCs[comp_index].weight_map().begin(),
243
        BCCs[comp_index].weight_map().end(),
244
        second_equal_to<MapEntry>(-1));
245
246
    if (count == 1) {
247
        // Find the vertex id for the vertex with unknown link weight
248
        string vertex_id = BCCs[comp_index].first_vertex_id_with_unknown_weight();
249
250
        QueueElem elem = {
251
            .component_index = comp_index,
252
            .vertex_id = vertex_id,
253
            .type = "component_vertex_pair",
254
        };
255
        // cout << "Add component_vertex_pair: " << comp_index << " - " << vertex_id << endl;
256
        Q.push(elem);
257
    }
258
}