Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (6.31 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
/* CREATE SUB-COMPONENT */
43
void SubComponent::AddEdge(Router r1, Router r2, Link l) {
44
    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

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

    
58
    // Create name -> index map
59
    int index = 0;
60
    for (string s : all_vertices_id_) {
61
        name_index_map_[s] = index;
62
        ++index;
63
    }
64
}
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
    }
72
}
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
    }
80
    else {
81
        return 0;
82
    }
83
}
84

    
85
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
}
95

    
96
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
    }
115

    
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
    }
130
    // cout << "Mark 3\n";
131
}
132

    
133
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
    // cout << i1 << " " << i2 << " = " << value << endl;
158
    traffic_matrix_[i1][i2] = value;
159
    traffic_matrix_[i2][i1] = value; // because Traffic Matrix is symmetric
160
}
161

    
162
/* 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
/* 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
}
195

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

    
211
/* 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
}