Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (9.48 KB)

1 ee0dd796 Quynh PX Nguyen
//
2
// Created by quynh on 1/9/16.
3
//
4
5
#include "sub_component.h"
6
7 d5b7a27f Quynh PX Nguyen
SubComponent::SubComponent(bool weighted_graph) {
8
    // cout << "===> Start SubComponent() constructor, weighted =" << weighted_graph << endl;
9
    gm_ = GraphManager(weighted_graph);
10
    // cout << "<=== Finish SubComponent() constructor\n";
11 ee0dd796 Quynh PX Nguyen
}
12
13 cb770240 Quynh PX Nguyen
/* GETTERS & SETTERS & UPDATERS */
14
GraphManager const& SubComponent::gm() const {
15
    return gm_;
16
}
17 ee0dd796 Quynh PX Nguyen
18 cb770240 Quynh PX Nguyen
StringSet const& SubComponent::all_vertices_id() const {
19
    return all_vertices_id_;
20
}
21 ee0dd796 Quynh PX Nguyen
22 cb770240 Quynh PX Nguyen
StringSet const& SubComponent::art_points_id() const {
23
    return art_points_id_;
24 ee0dd796 Quynh PX Nguyen
}
25
26 cb770240 Quynh PX Nguyen
StringSet const& SubComponent::non_art_points_id() const {
27
    return non_art_points_id_;
28
}
29 d5b7a27f Quynh PX Nguyen
30 cb770240 Quynh PX Nguyen
NameToIntMap const& SubComponent::weight_map() const {
31
    // Returns the whole weight_map_, for all the vertices
32
    // This one is different from get_weight_map(name)
33
    return weight_map_;
34 ee0dd796 Quynh PX Nguyen
}
35
36 cb770240 Quynh PX Nguyen
NameToIntMap const& SubComponent::weight_reversed_map() const {
37
    return weight_reversed_map_;
38 ee0dd796 Quynh PX Nguyen
}
39
40 162e1bda Quynh PX Nguyen
std::map< std::pair<string, string>, int > const& SubComponent::traffic_matrix() const {
41 cb770240 Quynh PX Nguyen
    return traffic_matrix_;
42 ee0dd796 Quynh PX Nguyen
}
43
44 437fd680 Quynh PX Nguyen
CentralityVec const& SubComponent::v_centrality_vec() const {
45
    return v_centrality_vec_;
46
}
47
48 cb770240 Quynh PX Nguyen
/* CREATE SUB-COMPONENT */
49 efed924d Quynh PX Nguyen
void SubComponent::AddEdge(Router r1, Router r2, Link l) {
50 cb770240 Quynh PX Nguyen
    gm_.AddEdge(r1, r2, l);
51
}
52
53
void SubComponent::FinalizeSubComponent(StringSet all_art_points_id) {
54 437fd680 Quynh PX Nguyen
    // TODO: is there anyway to not have to call this function after the graph was created completely?
55
    gm_.ResetVerticesAndEdgesIndexMap();
56
57 cb770240 Quynh PX Nguyen
    // Create set of vertices id
58
    graphext::id_of_all_vertices(gm_.g_, all_vertices_id_);
59
60
    // Create set of this sub-component's articulation points id
61
    using namespace setops;
62
    art_points_id_ = all_vertices_id_ / all_art_points_id;
63 ee0dd796 Quynh PX Nguyen
64 cb770240 Quynh PX Nguyen
    // Create set of vertices id (such that those vertices are not articulation points)
65
    non_art_points_id_ = all_vertices_id_ - art_points_id_;
66 ee0dd796 Quynh PX Nguyen
67 cb770240 Quynh PX Nguyen
    // Create name -> index map
68
    int index = 0;
69
    for (string s : all_vertices_id_) {
70 437fd680 Quynh PX Nguyen
        name_index_pmap_[s] = index;
71 cb770240 Quynh PX Nguyen
        ++index;
72 ee0dd796 Quynh PX Nguyen
    }
73 cb770240 Quynh PX Nguyen
}
74
75
76
/* LINK WEIGHT CALCULATION */
77
void SubComponent::initialize_weight() {
78
    for (string s : art_points_id_) {
79
        update_weight_map(s, -1);
80 ee0dd796 Quynh PX Nguyen
    }
81 cb770240 Quynh PX Nguyen
}
82
83
int SubComponent::get_weight_map(string name) {
84
    // Return only the weight for the vertex with the given name.
85
    // Check out weight_map()
86
    if (stdhelper::exists(weight_map_, name)) {
87
        return weight_map_[name];
88 ee0dd796 Quynh PX Nguyen
    }
89 cb770240 Quynh PX Nguyen
    else {
90
        return 0;
91 ee0dd796 Quynh PX Nguyen
    }
92
}
93
94 cb770240 Quynh PX Nguyen
int SubComponent::get_weight_reversed_map(string name) {
95
    // Return only the 'weight reversed' for the vertex with the given name.
96
    // Check out weight_reversed_map(). Those 2 functions serve different purpose
97
    if (stdhelper::exists(weight_reversed_map_, name)) {
98
        return weight_reversed_map_[name];
99
    }
100
    else {
101
        return 0;
102
    }
103 ee0dd796 Quynh PX Nguyen
}
104
105 cb770240 Quynh PX Nguyen
void SubComponent::update_weight_map(string name, int value) {
106
    // cout << "update " << name << " = " << value << endl;
107
    weight_map_[name] = value;
108
}
109
110 162e1bda Quynh PX Nguyen
void SubComponent::update_weight_reversed_map(string name, int value) {
111
    weight_reversed_map_[name] = value;
112
}
113
114
void SubComponent::calculate_weight_reversed(int V) {
115
    // V is the total number of vertices in the parent component
116
    for (string name : all_vertices_id_) {
117
        int value = get_weight_map(name);
118
        update_weight_reversed_map(name, V - 1 - value);
119
    }
120
}
121
122 cb770240 Quynh PX Nguyen
/* TRAFFIC MATRIX */
123
void SubComponent::CalculateTrafficMatrix() {
124 162e1bda Quynh PX Nguyen
    traffic_matrix_pmap_ = TrafficMatrixPMap(traffic_matrix_);
125
126 cb770240 Quynh PX Nguyen
    initialize_traffic_matrix();
127
128
    // When only one vertex is an articulation point
129
    for (string a : art_points_id_) {
130
        // cout << a << " ";
131
        for (string non_a : non_art_points_id_) {
132
            // cout << non_a << " ";
133
            int communication_intensity = get_weight_reversed_map(a) + 1;
134
            update_traffic_matrix(a, non_a, communication_intensity);
135
        }
136
        // cout << endl;
137 ee0dd796 Quynh PX Nguyen
    }
138 cb770240 Quynh PX Nguyen
139
    // When both vertices are articulation points
140
    int size = art_points_id_.size();
141
    for (string a1 : art_points_id_) {
142
        for (string a2 : art_points_id_) {
143
            if (a1.compare(a2) == 0)
144
                continue;
145
146
            int communication_intensity = (
147
                (get_weight_reversed_map(a1) + 1) *
148
                (get_weight_reversed_map(a2) + 1)
149
            );
150
            update_traffic_matrix(a1, a2, communication_intensity);
151
        }
152 ee0dd796 Quynh PX Nguyen
    }
153 cb770240 Quynh PX Nguyen
    // cout << "Mark 3\n";
154 ee0dd796 Quynh PX Nguyen
}
155
156 cb770240 Quynh PX Nguyen
void SubComponent::initialize_traffic_matrix() {
157 162e1bda Quynh PX Nguyen
    // generate_empty_traffic_matrix, with 1 for different vertices, and 0 for the same vertices
158
    for (string id1 : all_vertices_id_) {
159
        for (string id2 : all_vertices_id_) {
160
            if (id1.compare(id2) == 0) {
161
                update_traffic_matrix(id1, id2, 0);
162
            }
163
            else {
164
                update_traffic_matrix(id1, id2, 1);
165
            }
166
        }
167 cb770240 Quynh PX Nguyen
    }
168
}
169
170
int SubComponent::get_traffic_matrix(string name_1, string name_2) {
171 162e1bda Quynh PX Nguyen
    std::pair<string, string> p;
172
    if (name_1.compare(name_2) <= 0) {
173
        p = std::pair<string, string>(name_1, name_2);
174
    }
175
    else {
176
        p = std::pair<string, string>(name_2, name_1);
177
    }
178
    return traffic_matrix_[p];
179 cb770240 Quynh PX Nguyen
}
180
181
void SubComponent::update_traffic_matrix(string name_1, string name_2, int value) {
182 162e1bda Quynh PX Nguyen
    std::pair<string, string> p;
183
    if (name_1.compare(name_2) <= 0) {
184
        p = std::pair<string, string>(name_1, name_2);
185
    }
186
    else {
187
        p = std::pair<string, string>(name_2, name_1);
188
    }
189
    traffic_matrix_[p] = value;
190 cb770240 Quynh PX Nguyen
}
191
192 20756421 Quynh PX Nguyen
/* BETWEENNESS CENTRALITY */
193 162e1bda Quynh PX Nguyen
void SubComponent::CalculateBetweennessCentralityHeuristic() {
194 20756421 Quynh PX Nguyen
    initialize_betweenness_centrality();
195
196 d5b7a27f Quynh PX Nguyen
    if (gm_.weighted_graph()) {
197
        cout << "---- Sub Component BC for weighted graph -----\n";
198
199
        typedef map<Edge, double> EdgeWeightStdMap;
200
        typedef boost::associative_property_map<EdgeIndexStdMap> EdgeWeightPMap;
201
        EdgeIndexStdMap edge_weight_std_map;
202
        EdgeWeightPMap edge_weight_pmap = EdgeWeightPMap(edge_weight_std_map);
203
204
        BGL_FORALL_EDGES(edge, gm_.g_, Graph) {
205
            edge_weight_std_map[edge] = gm_.g_[edge].cost;
206
        }
207
208
        boost::brandes_betweenness_centrality_heuristic(gm_.g_,
209
            traffic_matrix_pmap_,
210
            boost::centrality_map(
211
                v_centrality_pmap_).vertex_index_map(
212
                gm_.v_index_pmap()).weight_map(
213
                edge_weight_pmap)
214
        );
215
    }
216
    else {
217
        cout << "---- Sub Component BC for unweighted graph -----\n";
218
        boost::brandes_betweenness_centrality_heuristic(gm_.g_,
219
            traffic_matrix_pmap_,
220
            boost::centrality_map(
221
                v_centrality_pmap_).vertex_index_map(
222
                gm_.v_index_pmap())
223
        );
224
    }
225 20756421 Quynh PX Nguyen
}
226
227
void SubComponent::initialize_betweenness_centrality() {
228
    v_centrality_vec_ = CentralityVec(num_of_vertices());
229 437fd680 Quynh PX Nguyen
    v_centrality_pmap_ = CentralityPMap(v_centrality_vec_.begin(), gm_.v_index_pmap());
230
}
231
232
double SubComponent::get_betweenness_centrality(string name) {
233
    // There are 2 ways to retrieve the BC score
234
    // 1st way - through v_centrality_vec_
235
    int index = gm_.get_index_from_id(name);
236
    return v_centrality_vec_.at(index);
237
}
238
239
double SubComponent::get_betweenness_centrality(Vertex v) {
240
    // 2nd way - uncomment to use v_centrality_pmap
241
    return boost::get(v_centrality_pmap_, v);
242 20756421 Quynh PX Nguyen
}
243
244 cb770240 Quynh PX Nguyen
/* HELPERS */
245
int SubComponent::num_of_vertices() {
246
    return boost::num_vertices(gm_.g_);
247
}
248
249
int SubComponent::index_of_vertex_id(string vertex_id) {
250
    // TODO: might throw exception here
251 437fd680 Quynh PX Nguyen
    return name_index_pmap_[vertex_id];
252 efed924d Quynh PX Nguyen
}
253 ee0dd796 Quynh PX Nguyen
254 cb770240 Quynh PX Nguyen
bool SubComponent::vertex_exists(string name) {
255 4ca27bae Quynh PX Nguyen
    return stdhelper::exists(art_points_id_, name);
256 cb770240 Quynh PX Nguyen
}
257
258
string SubComponent::first_vertex_id_with_unknown_weight() {
259
    string vertex_id = "";
260
    for (auto &i : weight_map_) {
261
        if (i.second == -1) {
262
            vertex_id = i.first;
263
            break;
264
        }
265
    }
266
    return vertex_id;
267 ee0dd796 Quynh PX Nguyen
}
268 efed924d Quynh PX Nguyen
269 cb770240 Quynh PX Nguyen
/* HELPERS FOR OUTPUTTING RESULT */
270 437fd680 Quynh PX Nguyen
void SubComponent::print() {
271
    cout << "Sub-component:" << endl;
272
    gm_.print();
273
274
    cout << "\nArticulation points ID:\n";
275
    outops::operator<<(cout, art_points_id());
276
277
    cout << "\nNormal Vertices ID:\n";
278
    outops::operator<<(cout, all_vertices_id());
279 cb770240 Quynh PX Nguyen
280 437fd680 Quynh PX Nguyen
    cout << "\nLink Weight:\n";
281
    outops::operator<< <int> (cout, weight_map());
282
    // printhelper::for_map<string, int>(sc.weight_map());
283
284
    cout << "\nTraffic Matrix:\n";
285 162e1bda Quynh PX Nguyen
    print_traffic_matrix();
286 437fd680 Quynh PX Nguyen
287
    cout << "\nBetweenness Centrality:\n";
288
    outops::operator<< <double>(cout, v_centrality_vec());
289 cb770240 Quynh PX Nguyen
}
290
291 162e1bda Quynh PX Nguyen
void SubComponent::print_traffic_matrix() {
292
    typedef std::map<std::pair<string, string>, int>::const_iterator Iter;
293
294
    for (auto elem : traffic_matrix_) {
295
        cout << elem.first.first << " - " << elem.first.second << ": " << elem.second << endl;
296
    }
297
    // for (Iter iter = traffic_matrix_.begin(); iter != traffic_matrix_.end(); ++iter) {
298
    //     cout << *(iter->first) << " - " << endl;
299
    // }
300
}
301
302 cb770240 Quynh PX Nguyen
std::ostream& operator<<(std::ostream& os, const SubComponent& sc) {
303
    cout << "Sub-component:" << endl;
304
    cout << sc.gm_;
305
306
    cout << "\nArticulation points ID:\n";
307
    outops::operator<<(cout, sc.art_points_id());
308
309
    cout << "\nNormal Vertices ID:\n";
310
    outops::operator<<(cout, sc.all_vertices_id());
311
312
    cout << "\nLink Weight:\n";
313 437fd680 Quynh PX Nguyen
    outops::operator<< <int> (cout, sc.weight_map());
314 cb770240 Quynh PX Nguyen
    // printhelper::for_map<string, int>(sc.weight_map());
315
316
    cout << "\nTraffic Matrix:\n";
317 162e1bda Quynh PX Nguyen
    // I didn't write the << for traffic_matrix
318
    // outops::operator<<(cout, sc.traffic_matrix());
319 cb770240 Quynh PX Nguyen
320 437fd680 Quynh PX Nguyen
    cout << "\nBetweenness Centrality:\n";
321
    outops::operator<< <double>(cout, sc.v_centrality_vec());
322
323 cb770240 Quynh PX Nguyen
    return os;
324
}