Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (7.76 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_map());
23
}
24

    
25
/* GETTER */
26
StringSet const& BiConnectedComponents::all_art_points_id() const {
27
    return all_art_points_id_;
28
}
29

    
30
/* SUB-COMPONENT */
31
void BiConnectedComponents::FindBiConnectedComponents() {
32
    cout << "Running FindBiConnectedComponents" << endl;
33

    
34
    boost::biconnected_components(gm_.g_, component_map_,
35
                                  back_inserter(art_points_),
36
                                  boost::vertex_index_map(gm_.v_index_map()));
37

    
38
    // Set some variables
39
    graphext::id_of_some_vertices(gm_.g_, art_points_, all_art_points_id_);
40

    
41
    // Process the result from boost::biconnected_components
42
    BCCs = Component_t(num_of_bcc());
43
    CreateSubComponents();
44

    
45
    // Calculate Link Weight
46
    cout << "Calculate Link Weight\n";
47
    CalculateLinkWeight();
48

    
49
    // Calculate Traffic Matrix
50
    cout << "Calculate Traffic Matrix\n";
51
    CalculateTrafficMatrix();
52

    
53
    // Calculate Betweenness Centrality
54
    cout << "Calculate Betweenness Centrality\n";
55
    CalculateBetweennessCentrality();
56

    
57
    print();
58
}
59

    
60
void BiConnectedComponents::CreateSubComponents() {
61
    // Generating subgraph for each sub-component
62
    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
        BCCs[comp_index].AddEdge(r1, r2, l);
68
    }
69

    
70
    // Finalizing each sub components
71
    for (int i = 0; i < num_of_bcc(); ++i) {
72
        BCCs[i].FinalizeSubComponent(all_art_points_id_);
73
    }
74
}
75

    
76
/* 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
    }
96
}
97

    
98
/* TRAFFIC MATRIX */
99
void BiConnectedComponents::CalculateTrafficMatrix() {
100
    for (int i = 0; i < num_of_bcc_; ++i) {
101
        BCCs[i].CalculateTrafficMatrix();
102
    }
103
}
104

    
105
/* BETWEENNESS CENTRALITY */
106
void BiConnectedComponents::CalculateBetweennessCentrality() {
107
    for (int i = 0; i < num_of_bcc_; ++i) {
108
        BCCs[i].CalculateBetweennessCentrality();
109
    }
110
}
111

    
112
/* HELPERS */
113
int BiConnectedComponents::num_of_bcc() {
114
    if (num_of_bcc_ == -1) { // calculate it
115
        // +1 to counteract for the zero-indexing
116
        num_of_bcc_ = *std::max_element(component_vec_.begin(), component_vec_.end()) + 1;
117
    }
118

    
119
    return num_of_bcc_;
120
}
121

    
122
/* 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

    
129
std::ostream& operator<<(std::ostream& os, const BiConnectedComponents& rhs) {
130
    cout << "\n\nBi-Connected Components\n\n";
131
    cout << rhs.gm_;
132

    
133
    cout << "\nArticulation points:\n";
134
    outops::operator<<(cout, rhs.all_art_points_id());
135
    return os;
136

    
137
    // 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
}
149

    
150
/******************************
151
* Private functions
152
******************************/
153

    
154
/* LINK WEIGHT */
155
void BiConnectedComponents::initialize_weight() {
156
    for (int i = 0; i < num_of_bcc_; ++i) {
157
        BCCs[i].initialize_weight();
158
    }
159
}
160

    
161
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
    }
175
}
176

    
177
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
            }
185
        }
186
    }
187
    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
}
191

    
192
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

    
202
            if (count > 1) break;
203
        }
204
    }
205

    
206
    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

    
214
        // cout << "Add vertex_component_pair: " << comp_index << " - " << vertex_id << endl;
215
        Q.push(elem);
216
    }
217
}
218

    
219
void BiConnectedComponents::process_vertex_component_pair(int comp_index, string vertex_id) {
220
    int size = 0;
221

    
222
    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

    
233
    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
}
237

    
238
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
}