Statistics
| Branch: | Revision:

root / custompackages / graph-parser / src / sub_component.cpp @ 20756421

History | View | Annotate | Download (6.31 KB)

1 ee0dd796 Quynh PX Nguyen
//
2
// Created by quynh on 1/9/16.
3
//
4
5
#include "sub_component.h"
6
7
8
SubComponent::SubComponent() {
9 efed924d Quynh PX Nguyen
    // do nothing
10 ee0dd796 Quynh PX Nguyen
}
11
12 cb770240 Quynh PX Nguyen
/* GETTERS & SETTERS & UPDATERS */
13
GraphManager const& SubComponent::gm() const {
14
    return gm_;
15
}
16 ee0dd796 Quynh PX Nguyen
17 cb770240 Quynh PX Nguyen
StringSet const& SubComponent::all_vertices_id() const {
18
    return all_vertices_id_;
19
}
20 ee0dd796 Quynh PX Nguyen
21 cb770240 Quynh PX Nguyen
StringSet const& SubComponent::art_points_id() const {
22
    return art_points_id_;
23 ee0dd796 Quynh PX Nguyen
}
24
25 cb770240 Quynh PX Nguyen
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 ee0dd796 Quynh PX Nguyen
}
33
34 cb770240 Quynh PX Nguyen
NameToIntMap const& SubComponent::weight_reversed_map() const {
35
    return weight_reversed_map_;
36 ee0dd796 Quynh PX Nguyen
}
37
38 cb770240 Quynh PX Nguyen
vector< vector< int > > const& SubComponent::traffic_matrix() const {
39
    return traffic_matrix_;
40 ee0dd796 Quynh PX Nguyen
}
41
42 cb770240 Quynh PX Nguyen
/* CREATE SUB-COMPONENT */
43 efed924d Quynh PX Nguyen
void SubComponent::AddEdge(Router r1, Router r2, Link l) {
44 cb770240 Quynh PX Nguyen
    gm_.AddEdge(r1, r2, l);
45
}
46
47
void SubComponent::FinalizeSubComponent(StringSet all_art_points_id) {
48
    // Create set of vertices id
49
    graphext::id_of_all_vertices(gm_.g_, all_vertices_id_);
50
51
    // Create set of this sub-component's articulation points id
52
    using namespace setops;
53
    art_points_id_ = all_vertices_id_ / all_art_points_id;
54 ee0dd796 Quynh PX Nguyen
55 cb770240 Quynh PX Nguyen
    // Create set of vertices id (such that those vertices are not articulation points)
56
    non_art_points_id_ = all_vertices_id_ - art_points_id_;
57 ee0dd796 Quynh PX Nguyen
58 cb770240 Quynh PX Nguyen
    // Create name -> index map
59
    int index = 0;
60
    for (string s : all_vertices_id_) {
61
        name_index_map_[s] = index;
62
        ++index;
63 ee0dd796 Quynh PX Nguyen
    }
64 cb770240 Quynh PX Nguyen
}
65
66
67
/* LINK WEIGHT CALCULATION */
68
void SubComponent::initialize_weight() {
69
    for (string s : art_points_id_) {
70
        update_weight_map(s, -1);
71 ee0dd796 Quynh PX Nguyen
    }
72 cb770240 Quynh PX Nguyen
}
73
74
int SubComponent::get_weight_map(string name) {
75
    // Return only the weight for the vertex with the given name.
76
    // Check out weight_map()
77
    if (stdhelper::exists(weight_map_, name)) {
78
        return weight_map_[name];
79 ee0dd796 Quynh PX Nguyen
    }
80 cb770240 Quynh PX Nguyen
    else {
81
        return 0;
82 ee0dd796 Quynh PX Nguyen
    }
83
}
84
85 cb770240 Quynh PX Nguyen
int SubComponent::get_weight_reversed_map(string name) {
86
    // Return only the 'weight reversed' for the vertex with the given name.
87
    // Check out weight_reversed_map(). Those 2 functions serve different purpose
88
    if (stdhelper::exists(weight_reversed_map_, name)) {
89
        return weight_reversed_map_[name];
90
    }
91
    else {
92
        return 0;
93
    }
94 ee0dd796 Quynh PX Nguyen
}
95
96 cb770240 Quynh PX Nguyen
void SubComponent::update_weight_map(string name, int value) {
97
    // cout << "update " << name << " = " << value << endl;
98
    weight_map_[name] = value;
99
}
100
101
/* TRAFFIC MATRIX */
102
void SubComponent::CalculateTrafficMatrix() {
103
    initialize_traffic_matrix();
104
105
    // When only one vertex is an articulation point
106
    for (string a : art_points_id_) {
107
        // cout << a << " ";
108
        for (string non_a : non_art_points_id_) {
109
            // cout << non_a << " ";
110
            int communication_intensity = get_weight_reversed_map(a) + 1;
111
            update_traffic_matrix(a, non_a, communication_intensity);
112
        }
113
        // cout << endl;
114 ee0dd796 Quynh PX Nguyen
    }
115 cb770240 Quynh PX Nguyen
116
    // When both vertices are articulation points
117
    int size = art_points_id_.size();
118
    for (string a1 : art_points_id_) {
119
        for (string a2 : art_points_id_) {
120
            if (a1.compare(a2) == 0)
121
                continue;
122
123
            int communication_intensity = (
124
                (get_weight_reversed_map(a1) + 1) *
125
                (get_weight_reversed_map(a2) + 1)
126
            );
127
            update_traffic_matrix(a1, a2, communication_intensity);
128
        }
129 ee0dd796 Quynh PX Nguyen
    }
130 cb770240 Quynh PX Nguyen
    // cout << "Mark 3\n";
131 ee0dd796 Quynh PX Nguyen
}
132
133 cb770240 Quynh PX Nguyen
void SubComponent::initialize_traffic_matrix() {
134
    // generate_empty_traffic_matrix, with 1 every where, and 0 in the main diagonal
135
    int size = num_of_vertices();
136
    traffic_matrix_ = vector< vector<int> >(size);
137
    for (int i = 0; i < size; ++i) {
138
        traffic_matrix_[i] = vector< int >(size, 1);
139
    }
140
141
    // Reset the main diagonal to 0
142
    for (int i = 0; i < size; ++i) {
143
        traffic_matrix_[i][i] = 0;
144
    }
145
}
146
147
int SubComponent::get_traffic_matrix(string name_1, string name_2) {
148
    int i1 = index_of_vertex_id(name_1);
149
    int i2 = index_of_vertex_id(name_2);
150
    // TODO: exception
151
    return traffic_matrix_[i1][i2];
152
}
153
154
void SubComponent::update_traffic_matrix(string name_1, string name_2, int value) {
155
    int i1 = index_of_vertex_id(name_1);
156
    int i2 = index_of_vertex_id(name_2);
157 20756421 Quynh PX Nguyen
    // cout << i1 << " " << i2 << " = " << value << endl;
158 cb770240 Quynh PX Nguyen
    traffic_matrix_[i1][i2] = value;
159
    traffic_matrix_[i2][i1] = value; // because Traffic Matrix is symmetric
160
}
161
162 20756421 Quynh PX Nguyen
/* BETWEENNESS CENTRALITY */
163
void SubComponent::CalculateBetweennessCentrality() {
164
    initialize_betweenness_centrality();
165
166
    cout << "Mark 1" << endl;
167
168
    boost::brandes_betweenness_centrality(gm_.g_,
169
        boost::centrality_map(v_centrality_map_).vertex_index_map(
170
            gm_.v_index_map())
171
    );
172
173
    cout << "Mark 2" << endl;
174
175
    cout << "Vertex betweenness\n" << endl;
176
    for (int i = 0; i < num_of_vertices(); ++i) {
177
        cout << v_centrality_vec_.at(i) << endl;
178
    }
179
}
180
181
void SubComponent::initialize_betweenness_centrality() {
182
    v_centrality_vec_ = CentralityVec(num_of_vertices());
183
    v_centrality_map_ = CentralityMap(v_centrality_vec_.begin(), gm_.v_index_map());
184
}
185
186 cb770240 Quynh PX Nguyen
/* HELPERS */
187
int SubComponent::num_of_vertices() {
188
    return boost::num_vertices(gm_.g_);
189
}
190
191
int SubComponent::index_of_vertex_id(string vertex_id) {
192
    // TODO: might throw exception here
193
    return name_index_map_[vertex_id];
194 efed924d Quynh PX Nguyen
}
195 ee0dd796 Quynh PX Nguyen
196 cb770240 Quynh PX Nguyen
bool SubComponent::vertex_exists(string name) {
197
    stdhelper::exists(art_points_id_, name);
198
}
199
200
string SubComponent::first_vertex_id_with_unknown_weight() {
201
    string vertex_id = "";
202
    for (auto &i : weight_map_) {
203
        if (i.second == -1) {
204
            vertex_id = i.first;
205
            break;
206
        }
207
    }
208
    return vertex_id;
209 ee0dd796 Quynh PX Nguyen
}
210 efed924d Quynh PX Nguyen
211 cb770240 Quynh PX Nguyen
/* HELPERS FOR OUTPUTTING RESULT */
212
void SubComponent::print_traffic_matrix() {
213
214
}
215
216
std::ostream& operator<<(std::ostream& os, const SubComponent& sc) {
217
    cout << "Sub-component:" << endl;
218
    cout << sc.gm_;
219
220
    cout << "\nArticulation points ID:\n";
221
    outops::operator<<(cout, sc.art_points_id());
222
223
    cout << "\nNormal Vertices ID:\n";
224
    outops::operator<<(cout, sc.all_vertices_id());
225
226
    cout << "\nLink Weight:\n";
227
    outops::operator<<(cout, sc.weight_map());
228
    // printhelper::for_map<string, int>(sc.weight_map());
229
230
    cout << "\nTraffic Matrix:\n";
231
    outops::operator<<(cout, sc.traffic_matrix());
232
233
    return os;
234
}