Statistics
| Branch: | Revision:

root / custompackages / graph-parser / src / sub_component.cpp @ 4ca27bae

History | View | Annotate | Download (9.48 KB)

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

    
5
#include "sub_component.h"
6

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

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

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

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

    
26
StringSet const& SubComponent::non_art_points_id() const {
27
    return non_art_points_id_;
28
}
29

    
30
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
}
35

    
36
NameToIntMap const& SubComponent::weight_reversed_map() const {
37
    return weight_reversed_map_;
38
}
39

    
40
std::map< std::pair<string, string>, int > const& SubComponent::traffic_matrix() const {
41
    return traffic_matrix_;
42
}
43

    
44
CentralityVec const& SubComponent::v_centrality_vec() const {
45
    return v_centrality_vec_;
46
}
47

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

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

    
57
    // 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

    
64
    // 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

    
67
    // Create name -> index map
68
    int index = 0;
69
    for (string s : all_vertices_id_) {
70
        name_index_pmap_[s] = index;
71
        ++index;
72
    }
73
}
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
    }
81
}
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
    }
89
    else {
90
        return 0;
91
    }
92
}
93

    
94
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
}
104

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

    
110
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
/* TRAFFIC MATRIX */
123
void SubComponent::CalculateTrafficMatrix() {
124
    traffic_matrix_pmap_ = TrafficMatrixPMap(traffic_matrix_);
125

    
126
    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
    }
138

    
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
    }
153
    // cout << "Mark 3\n";
154
}
155

    
156
void SubComponent::initialize_traffic_matrix() {
157
    // 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
    }
168
}
169

    
170
int SubComponent::get_traffic_matrix(string name_1, string name_2) {
171
    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
}
180

    
181
void SubComponent::update_traffic_matrix(string name_1, string name_2, int value) {
182
    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
}
191

    
192
/* BETWEENNESS CENTRALITY */
193
void SubComponent::CalculateBetweennessCentralityHeuristic() {
194
    initialize_betweenness_centrality();
195

    
196
    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
}
226

    
227
void SubComponent::initialize_betweenness_centrality() {
228
    v_centrality_vec_ = CentralityVec(num_of_vertices());
229
    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
}
243

    
244
/* 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
    return name_index_pmap_[vertex_id];
252
}
253

    
254
bool SubComponent::vertex_exists(string name) {
255
    return stdhelper::exists(art_points_id_, name);
256
}
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
}
268

    
269
/* HELPERS FOR OUTPUTTING RESULT */
270
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

    
280
    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
    print_traffic_matrix();
286

    
287
    cout << "\nBetweenness Centrality:\n";
288
    outops::operator<< <double>(cout, v_centrality_vec());
289
}
290

    
291
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
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
    outops::operator<< <int> (cout, sc.weight_map());
314
    // printhelper::for_map<string, int>(sc.weight_map());
315

    
316
    cout << "\nTraffic Matrix:\n";
317
    // I didn't write the << for traffic_matrix
318
    // outops::operator<<(cout, sc.traffic_matrix());
319

    
320
    cout << "\nBetweenness Centrality:\n";
321
    outops::operator<< <double>(cout, sc.v_centrality_vec());
322

    
323
    return os;
324
}