Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (7.44 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
    print();
54
}
55

    
56
void BiConnectedComponents::CreateSubComponents() {
57
    // Generating subgraph for each sub-component
58
    BGL_FORALL_EDGES(edge, gm_.g_, Graph) {
59
        int comp_index = boost::get(component_map_, edge);
60
        Router r1 = gm_.g_[boost::source(edge, gm_.g_)];
61
        Router r2 = gm_.g_[boost::target(edge, gm_.g_)];
62
        Link l = gm_.g_[edge];
63
        BCCs[comp_index].AddEdge(r1, r2, l);
64
    }
65

    
66
    // Finalizing each sub components
67
    for (int i = 0; i < num_of_bcc(); ++i) {
68
        BCCs[i].FinalizeSubComponent(all_art_points_id_);
69
    }
70
}
71

    
72
/* LINK WEIGHT */
73
void BiConnectedComponents::CalculateLinkWeight() {
74
    initialize_weight();
75
    initialize_queue();
76

    
77
    while (!Q.empty()) {
78
        QueueElem elem = Q.front();
79
        Q.pop();
80
        int comp_index = elem.component_index;
81
        string vertex_id = elem.vertex_id;
82

    
83
        if (elem.type == "component_vertex_pair") {
84
            // cout << "component_vertex_pair: " << comp_index << " - " << vertex_id << endl;
85
            process_component_vertex_pair(comp_index, vertex_id);
86
        }
87
        else if (elem.type == "vertex_component_pair") {
88
            // cout << "vertex_component_pair: " << comp_index << " - " << vertex_id << endl;
89
            process_vertex_component_pair(comp_index, vertex_id);
90
        }
91
    }
92
}
93

    
94
/* TRAFFIC MATRIX */
95
void BiConnectedComponents::CalculateTrafficMatrix() {
96
    for (int i = 0; i < num_of_bcc_; ++i) {
97
        BCCs[i].CalculateTrafficMatrix();
98
    }
99
}
100

    
101
/* HELPERS */
102
int BiConnectedComponents::num_of_bcc() {
103
    if (num_of_bcc_ == -1) { // calculate it
104
        // +1 to counteract for the zero-indexing
105
        num_of_bcc_ = *std::max_element(component_vec_.begin(), component_vec_.end()) + 1;
106
    }
107

    
108
    return num_of_bcc_;
109
}
110

    
111
/* HELPERS FOR OUTPUTTING RESULT */
112
void BiConnectedComponents::print() {
113
    for (int i = 0; i < num_of_bcc(); ++i) {
114
        cout << BCCs[i] << endl;
115
    }
116
}
117

    
118
std::ostream& operator<<(std::ostream& os, const BiConnectedComponents& rhs) {
119
    cout << "\n\nBi-Connected Components\n\n";
120
    cout << rhs.gm_;
121

    
122
    cout << "\nArticulation points:\n";
123
    outops::operator<<(cout, rhs.all_art_points_id());
124
    return os;
125

    
126
    // TODO: output the result of BCC
127
    // Test the biconnected components
128
    // Eiter ei, ei_end;
129
    // size_t i = 0;
130
    // for (boost::tie(ei, ei_end) = boost::edges(gm_.g_); ei != ei_end; ++ei) {
131
    //     string source = gm_.g_[(*ei).m_source].id;
132
    //     string target = gm_.g_[(*ei).m_target].id;
133
    //     edges_size_type comp = component_vec_.at(i);
134
    //     cout << source << " " << target << " " << comp << endl;
135
    //     ++i;
136
    // }
137
}
138

    
139
/******************************
140
* Private functions
141
******************************/
142

    
143
/* LINK WEIGHT */
144
void BiConnectedComponents::initialize_weight() {
145
    for (int i = 0; i < num_of_bcc_; ++i) {
146
        BCCs[i].initialize_weight();
147
    }
148
}
149

    
150
void BiConnectedComponents::initialize_queue() {
151
    for (int i = 0; i < num_of_bcc_; ++i) {
152
        if (BCCs[i].art_points_id().size() == 1) {
153
            string vertex_id = *(BCCs[i].art_points_id().begin());
154
            string type = "component_vertex_pair";
155
            QueueElem elem = {
156
                .component_index = i,
157
                .vertex_id = vertex_id,
158
                .type = type,
159
            };
160

    
161
            Q.push(elem);
162
        }
163
    }
164
}
165

    
166
void BiConnectedComponents::process_component_vertex_pair(int comp_index, string vertex_id) {
167
    int size = BCCs[comp_index].num_of_vertices() - 1;
168
    for (string s : BCCs[comp_index].art_points_id()) {
169
        if (s.compare(vertex_id) != 0) {
170
            int weight = BCCs[comp_index].get_weight_map(s);
171
            if (weight != -1) {
172
                size += num_of_vertices_ - weight - 1;
173
            }
174
        }
175
    }
176
    int link_weight = size;
177
    BCCs[comp_index].update_weight_map(vertex_id, link_weight);
178
    find_unknown_weight_wrt_art_point(vertex_id);
179
}
180

    
181
void BiConnectedComponents::find_unknown_weight_wrt_art_point(string vertex_id) {
182
    int count = 0;
183
    int comp_index = -1;
184
    for (int i = 0; i < num_of_bcc_; ++i) {
185
        if (BCCs[i].vertex_exists(vertex_id)) {
186
            if (BCCs[i].get_weight_map(vertex_id) == -1) {
187
                ++count;
188
                comp_index = i;
189
            }
190

    
191
            if (count > 1) break;
192
        }
193
    }
194

    
195
    if (count == 1) {
196
        // Add new element to QueueElem
197
        QueueElem elem = {
198
            .component_index = comp_index,
199
            .vertex_id = vertex_id,
200
            .type = "vertex_component_pair"
201
        };
202

    
203
        // cout << "Add vertex_component_pair: " << comp_index << " - " << vertex_id << endl;
204
        Q.push(elem);
205
    }
206
}
207

    
208
void BiConnectedComponents::process_vertex_component_pair(int comp_index, string vertex_id) {
209
    int size = 0;
210

    
211
    for (int i = 0; i < num_of_bcc_; ++i) {
212
        if (i != comp_index) {
213
            if (BCCs[i].vertex_exists(vertex_id)) {
214
                int weight = BCCs[i].get_weight_map(vertex_id);
215
                if (weight != -1) {
216
                    size += weight;
217
                }
218
            }
219
        }
220
    }
221

    
222
    int link_weight = num_of_vertices_ - 1 - size;
223
    BCCs[comp_index].update_weight_map(vertex_id, link_weight);
224
    find_unknown_weight_wrt_component(comp_index);
225
}
226

    
227
void BiConnectedComponents::find_unknown_weight_wrt_component(int comp_index) {
228
    // The 'counting' solution is found here: http://stackoverflow.com/questions/5517615/counting-number-of-same-values-in-map
229
    typedef NameToIntMap::value_type MapEntry;
230
    int count = std::count_if(
231
        BCCs[comp_index].weight_map().begin(),
232
        BCCs[comp_index].weight_map().end(),
233
        second_equal_to<MapEntry>(-1));
234

    
235
    if (count == 1) {
236
        // Find the vertex id for the vertex with unknown link weight
237
        string vertex_id = BCCs[comp_index].first_vertex_id_with_unknown_weight();
238

    
239
        QueueElem elem = {
240
            .component_index = comp_index,
241
            .vertex_id = vertex_id,
242
            .type = "component_vertex_pair",
243
        };
244
        // cout << "Add component_vertex_pair: " << comp_index << " - " << vertex_id << endl;
245
        Q.push(elem);
246
    }
247
}