Statistics
| Branch: | Revision:

root / custompackages / graph-parser / src / sub_component.cpp @ 437fd680

History | View | Annotate | Download (7.64 KB)

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

    
5
#include "sub_component.h"
6

    
7

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

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

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

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

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

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

    
38
vector< vector< int > > const& SubComponent::traffic_matrix() const {
39
    return traffic_matrix_;
40
}
41

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

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

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

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

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

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

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

    
73

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

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

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

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

    
108
/* TRAFFIC MATRIX */
109
void SubComponent::CalculateTrafficMatrix() {
110
    initialize_traffic_matrix();
111

    
112
    // When only one vertex is an articulation point
113
    for (string a : art_points_id_) {
114
        // cout << a << " ";
115
        for (string non_a : non_art_points_id_) {
116
            // cout << non_a << " ";
117
            int communication_intensity = get_weight_reversed_map(a) + 1;
118
            update_traffic_matrix(a, non_a, communication_intensity);
119
        }
120
        // cout << endl;
121
    }
122

    
123
    // When both vertices are articulation points
124
    int size = art_points_id_.size();
125
    for (string a1 : art_points_id_) {
126
        for (string a2 : art_points_id_) {
127
            if (a1.compare(a2) == 0)
128
                continue;
129

    
130
            int communication_intensity = (
131
                (get_weight_reversed_map(a1) + 1) *
132
                (get_weight_reversed_map(a2) + 1)
133
            );
134
            update_traffic_matrix(a1, a2, communication_intensity);
135
        }
136
    }
137
    // cout << "Mark 3\n";
138
}
139

    
140
void SubComponent::initialize_traffic_matrix() {
141
    // generate_empty_traffic_matrix, with 1 every where, and 0 in the main diagonal
142
    int size = num_of_vertices();
143
    traffic_matrix_ = vector< vector<int> >(size);
144
    for (int i = 0; i < size; ++i) {
145
        traffic_matrix_[i] = vector< int >(size, 1);
146
    }
147

    
148
    // Reset the main diagonal to 0
149
    for (int i = 0; i < size; ++i) {
150
        traffic_matrix_[i][i] = 0;
151
    }
152
}
153

    
154
int SubComponent::get_traffic_matrix(string name_1, string name_2) {
155
    int i1 = index_of_vertex_id(name_1);
156
    int i2 = index_of_vertex_id(name_2);
157
    // TODO: exception
158
    return traffic_matrix_[i1][i2];
159
}
160

    
161
void SubComponent::update_traffic_matrix(string name_1, string name_2, int value) {
162
    int i1 = index_of_vertex_id(name_1);
163
    int i2 = index_of_vertex_id(name_2);
164
    // cout << i1 << " " << i2 << " = " << value << endl;
165
    traffic_matrix_[i1][i2] = value;
166
    traffic_matrix_[i2][i1] = value; // because Traffic Matrix is symmetric
167
}
168

    
169
/* BETWEENNESS CENTRALITY */
170
void SubComponent::CalculateBetweennessCentrality() {
171
    initialize_betweenness_centrality();
172

    
173
    cout << "Mark 1" << endl;
174

    
175
    boost::brandes_betweenness_centrality(gm_.g_,
176
        boost::centrality_map(v_centrality_pmap_).vertex_index_map(
177
            gm_.v_index_pmap())
178
    );
179

    
180
    cout << "Mark 2" << endl;
181

    
182
    cout << "Vertex betweenness\n" << endl;
183
    for (int i = 0; i < num_of_vertices(); ++i) {
184
        cout << v_centrality_vec_.at(i) << endl;
185
    }
186
}
187

    
188
void SubComponent::initialize_betweenness_centrality() {
189
    v_centrality_vec_ = CentralityVec(num_of_vertices());
190
    v_centrality_pmap_ = CentralityPMap(v_centrality_vec_.begin(), gm_.v_index_pmap());
191
}
192

    
193
double SubComponent::get_betweenness_centrality(string name) {
194
    // There are 2 ways to retrieve the BC score
195
    // 1st way - through v_centrality_vec_
196
    int index = gm_.get_index_from_id(name);
197
    cout << "    index = " << index << endl;
198
    return v_centrality_vec_.at(index);
199
}
200

    
201
double SubComponent::get_betweenness_centrality(Vertex v) {
202
    // 2nd way - uncomment to use v_centrality_pmap
203
    return boost::get(v_centrality_pmap_, v);
204
}
205

    
206
/* HELPERS */
207
int SubComponent::num_of_vertices() {
208
    return boost::num_vertices(gm_.g_);
209
}
210

    
211
int SubComponent::index_of_vertex_id(string vertex_id) {
212
    // TODO: might throw exception here
213
    return name_index_pmap_[vertex_id];
214
}
215

    
216
bool SubComponent::vertex_exists(string name) {
217
    stdhelper::exists(art_points_id_, name);
218
}
219

    
220
string SubComponent::first_vertex_id_with_unknown_weight() {
221
    string vertex_id = "";
222
    for (auto &i : weight_map_) {
223
        if (i.second == -1) {
224
            vertex_id = i.first;
225
            break;
226
        }
227
    }
228
    return vertex_id;
229
}
230

    
231
/* HELPERS FOR OUTPUTTING RESULT */
232
void SubComponent::print() {
233
    cout << "Sub-component:" << endl;
234
    gm_.print();
235

    
236
    cout << "\nArticulation points ID:\n";
237
    outops::operator<<(cout, art_points_id());
238

    
239
    cout << "\nNormal Vertices ID:\n";
240
    outops::operator<<(cout, all_vertices_id());
241

    
242
    cout << "\nLink Weight:\n";
243
    outops::operator<< <int> (cout, weight_map());
244
    // printhelper::for_map<string, int>(sc.weight_map());
245

    
246
    cout << "\nTraffic Matrix:\n";
247
    outops::operator<<(cout, traffic_matrix());
248

    
249
    cout << "\nBetweenness Centrality:\n";
250
    outops::operator<< <double>(cout, v_centrality_vec());
251
}
252

    
253
std::ostream& operator<<(std::ostream& os, const SubComponent& sc) {
254
    cout << "Sub-component:" << endl;
255
    cout << sc.gm_;
256

    
257
    cout << "\nArticulation points ID:\n";
258
    outops::operator<<(cout, sc.art_points_id());
259

    
260
    cout << "\nNormal Vertices ID:\n";
261
    outops::operator<<(cout, sc.all_vertices_id());
262

    
263
    cout << "\nLink Weight:\n";
264
    outops::operator<< <int> (cout, sc.weight_map());
265
    // printhelper::for_map<string, int>(sc.weight_map());
266

    
267
    cout << "\nTraffic Matrix:\n";
268
    outops::operator<<(cout, sc.traffic_matrix());
269

    
270
    cout << "\nBetweenness Centrality:\n";
271
    outops::operator<< <double>(cout, sc.v_centrality_vec());
272

    
273
    return os;
274
}