Statistics
| Branch: | Revision:

root / custompackages / graph-parser / src / sub_component.cpp @ 162e1bda

History | View | Annotate | Download (8.43 KB)

1
//
2
// Created by quynh on 1/9/16.
3
//
4

    
5
#include "sub_component.h"
6

    
7
SubComponent::SubComponent() {
8
    // do nothing
9
}
10

    
11
/* GETTERS & SETTERS & UPDATERS */
12
GraphManager const& SubComponent::gm() const {
13
    return gm_;
14
}
15

    
16
StringSet const& SubComponent::all_vertices_id() const {
17
    return all_vertices_id_;
18
}
19

    
20
StringSet const& SubComponent::art_points_id() const {
21
    return art_points_id_;
22
}
23

    
24
StringSet const& SubComponent::non_art_points_id() const {
25
    return non_art_points_id_;
26
}
27
NameToIntMap const& SubComponent::weight_map() const {
28
    // Returns the whole weight_map_, for all the vertices
29
    // This one is different from get_weight_map(name)
30
    return weight_map_;
31
}
32

    
33
NameToIntMap const& SubComponent::weight_reversed_map() const {
34
    return weight_reversed_map_;
35
}
36

    
37
std::map< std::pair<string, string>, int > const& SubComponent::traffic_matrix() const {
38
    return traffic_matrix_;
39
}
40

    
41
CentralityVec const& SubComponent::v_centrality_vec() const {
42
    return v_centrality_vec_;
43
}
44

    
45
/* CREATE SUB-COMPONENT */
46
void SubComponent::AddEdge(Router r1, Router r2, Link l) {
47
    gm_.AddEdge(r1, r2, l);
48
}
49

    
50
void SubComponent::FinalizeSubComponent(StringSet all_art_points_id) {
51
    // TODO: is there anyway to not have to call this function after the graph was created completely?
52
    gm_.ResetVerticesAndEdgesIndexMap();
53

    
54
    // Create set of vertices id
55
    graphext::id_of_all_vertices(gm_.g_, all_vertices_id_);
56

    
57
    // Create set of this sub-component's articulation points id
58
    using namespace setops;
59
    art_points_id_ = all_vertices_id_ / all_art_points_id;
60

    
61
    // Create set of vertices id (such that those vertices are not articulation points)
62
    non_art_points_id_ = all_vertices_id_ - art_points_id_;
63

    
64
    // Create name -> index map
65
    int index = 0;
66
    for (string s : all_vertices_id_) {
67
        name_index_pmap_[s] = index;
68
        ++index;
69
    }
70
}
71

    
72

    
73
/* LINK WEIGHT CALCULATION */
74
void SubComponent::initialize_weight() {
75
    for (string s : art_points_id_) {
76
        update_weight_map(s, -1);
77
    }
78
}
79

    
80
int SubComponent::get_weight_map(string name) {
81
    // Return only the weight for the vertex with the given name.
82
    // Check out weight_map()
83
    if (stdhelper::exists(weight_map_, name)) {
84
        return weight_map_[name];
85
    }
86
    else {
87
        return 0;
88
    }
89
}
90

    
91
int SubComponent::get_weight_reversed_map(string name) {
92
    // Return only the 'weight reversed' for the vertex with the given name.
93
    // Check out weight_reversed_map(). Those 2 functions serve different purpose
94
    if (stdhelper::exists(weight_reversed_map_, name)) {
95
        return weight_reversed_map_[name];
96
    }
97
    else {
98
        return 0;
99
    }
100
}
101

    
102
void SubComponent::update_weight_map(string name, int value) {
103
    // cout << "update " << name << " = " << value << endl;
104
    weight_map_[name] = value;
105
}
106

    
107
void SubComponent::update_weight_reversed_map(string name, int value) {
108
    weight_reversed_map_[name] = value;
109
}
110

    
111
void SubComponent::calculate_weight_reversed(int V) {
112
    // V is the total number of vertices in the parent component
113
    for (string name : all_vertices_id_) {
114
        int value = get_weight_map(name);
115
        update_weight_reversed_map(name, V - 1 - value);
116
    }
117
}
118

    
119
/* TRAFFIC MATRIX */
120
void SubComponent::CalculateTrafficMatrix() {
121
    traffic_matrix_pmap_ = TrafficMatrixPMap(traffic_matrix_);
122

    
123
    initialize_traffic_matrix();
124

    
125
    // When only one vertex is an articulation point
126
    for (string a : art_points_id_) {
127
        // cout << a << " ";
128
        for (string non_a : non_art_points_id_) {
129
            // cout << non_a << " ";
130
            int communication_intensity = get_weight_reversed_map(a) + 1;
131
            update_traffic_matrix(a, non_a, communication_intensity);
132
        }
133
        // cout << endl;
134
    }
135

    
136
    // When both vertices are articulation points
137
    int size = art_points_id_.size();
138
    for (string a1 : art_points_id_) {
139
        for (string a2 : art_points_id_) {
140
            if (a1.compare(a2) == 0)
141
                continue;
142

    
143
            int communication_intensity = (
144
                (get_weight_reversed_map(a1) + 1) *
145
                (get_weight_reversed_map(a2) + 1)
146
            );
147
            update_traffic_matrix(a1, a2, communication_intensity);
148
        }
149
    }
150
    // cout << "Mark 3\n";
151
}
152

    
153
void SubComponent::initialize_traffic_matrix() {
154
    // generate_empty_traffic_matrix, with 1 for different vertices, and 0 for the same vertices
155
    for (string id1 : all_vertices_id_) {
156
        for (string id2 : all_vertices_id_) {
157
            if (id1.compare(id2) == 0) {
158
                update_traffic_matrix(id1, id2, 0);
159
            }
160
            else {
161
                update_traffic_matrix(id1, id2, 1);
162
            }
163
        }
164
    }
165
}
166

    
167
int SubComponent::get_traffic_matrix(string name_1, string name_2) {
168
    std::pair<string, string> p;
169
    if (name_1.compare(name_2) <= 0) {
170
        p = std::pair<string, string>(name_1, name_2);
171
    }
172
    else {
173
        p = std::pair<string, string>(name_2, name_1);
174
    }
175
    return traffic_matrix_[p];
176
}
177

    
178
void SubComponent::update_traffic_matrix(string name_1, string name_2, int value) {
179
    std::pair<string, string> p;
180
    if (name_1.compare(name_2) <= 0) {
181
        p = std::pair<string, string>(name_1, name_2);
182
    }
183
    else {
184
        p = std::pair<string, string>(name_2, name_1);
185
    }
186
    traffic_matrix_[p] = value;
187
}
188

    
189
/* BETWEENNESS CENTRALITY */
190
void SubComponent::CalculateBetweennessCentralityHeuristic() {
191
    initialize_betweenness_centrality();
192

    
193
    boost::brandes_betweenness_centrality_heuristic(gm_.g_,
194
        traffic_matrix_pmap_,
195
        boost::centrality_map(
196
            v_centrality_pmap_).vertex_index_map(
197
            gm_.v_index_pmap())
198
    );
199
}
200

    
201
void SubComponent::initialize_betweenness_centrality() {
202
    v_centrality_vec_ = CentralityVec(num_of_vertices());
203
    v_centrality_pmap_ = CentralityPMap(v_centrality_vec_.begin(), gm_.v_index_pmap());
204
}
205

    
206
double SubComponent::get_betweenness_centrality(string name) {
207
    // There are 2 ways to retrieve the BC score
208
    // 1st way - through v_centrality_vec_
209
    int index = gm_.get_index_from_id(name);
210
    return v_centrality_vec_.at(index);
211
}
212

    
213
double SubComponent::get_betweenness_centrality(Vertex v) {
214
    // 2nd way - uncomment to use v_centrality_pmap
215
    return boost::get(v_centrality_pmap_, v);
216
}
217

    
218
/* HELPERS */
219
int SubComponent::num_of_vertices() {
220
    return boost::num_vertices(gm_.g_);
221
}
222

    
223
int SubComponent::index_of_vertex_id(string vertex_id) {
224
    // TODO: might throw exception here
225
    return name_index_pmap_[vertex_id];
226
}
227

    
228
bool SubComponent::vertex_exists(string name) {
229
    stdhelper::exists(art_points_id_, name);
230
}
231

    
232
string SubComponent::first_vertex_id_with_unknown_weight() {
233
    string vertex_id = "";
234
    for (auto &i : weight_map_) {
235
        if (i.second == -1) {
236
            vertex_id = i.first;
237
            break;
238
        }
239
    }
240
    return vertex_id;
241
}
242

    
243
/* HELPERS FOR OUTPUTTING RESULT */
244
void SubComponent::print() {
245
    cout << "Sub-component:" << endl;
246
    gm_.print();
247

    
248
    cout << "\nArticulation points ID:\n";
249
    outops::operator<<(cout, art_points_id());
250

    
251
    cout << "\nNormal Vertices ID:\n";
252
    outops::operator<<(cout, all_vertices_id());
253

    
254
    cout << "\nLink Weight:\n";
255
    outops::operator<< <int> (cout, weight_map());
256
    // printhelper::for_map<string, int>(sc.weight_map());
257

    
258
    cout << "\nTraffic Matrix:\n";
259
    print_traffic_matrix();
260

    
261
    cout << "\nBetweenness Centrality:\n";
262
    outops::operator<< <double>(cout, v_centrality_vec());
263
}
264

    
265
void SubComponent::print_traffic_matrix() {
266
    typedef std::map<std::pair<string, string>, int>::const_iterator Iter;
267

    
268
    for (auto elem : traffic_matrix_) {
269
        cout << elem.first.first << " - " << elem.first.second << ": " << elem.second << endl;
270
    }
271
    // for (Iter iter = traffic_matrix_.begin(); iter != traffic_matrix_.end(); ++iter) {
272
    //     cout << *(iter->first) << " - " << endl;
273
    // }
274
}
275

    
276
std::ostream& operator<<(std::ostream& os, const SubComponent& sc) {
277
    cout << "Sub-component:" << endl;
278
    cout << sc.gm_;
279

    
280
    cout << "\nArticulation points ID:\n";
281
    outops::operator<<(cout, sc.art_points_id());
282

    
283
    cout << "\nNormal Vertices ID:\n";
284
    outops::operator<<(cout, sc.all_vertices_id());
285

    
286
    cout << "\nLink Weight:\n";
287
    outops::operator<< <int> (cout, sc.weight_map());
288
    // printhelper::for_map<string, int>(sc.weight_map());
289

    
290
    cout << "\nTraffic Matrix:\n";
291
    // I didn't write the << for traffic_matrix
292
    // outops::operator<<(cout, sc.traffic_matrix());
293

    
294
    cout << "\nBetweenness Centrality:\n";
295
    outops::operator<< <double>(cout, sc.v_centrality_vec());
296

    
297
    return os;
298
}