Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (9.25 KB)

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

    
5
#include "sub_component.h"
6

    
7

    
8
SubComponent::SubComponent() {
9
}
10

    
11
SubComponent::SubComponent(VertexVec aart_points, Graph asubGraph) : art_points(aart_points), subGraph(asubGraph) {
12
// SubComponent::SubComponent(VertexVec aart_points, Graph asubGraph) {
13
    // art_points = aart_points;
14
    // subGraph = asubGraph;
15
    // Deep copy for art_points
16
    // cout << "ABC " << endl;
17
    // for (VertexVecIter vi = aart_points.begin(); vi != aart_points.end(); ++vi) {
18
    //     Vertex v = Vertex(*vi);
19
    //     this->art_points.insert(this->art_points.end(), v);
20
    //     cout << "   asubGraph " << asubGraph[*vi].name << endl;
21
    //     cout << "    subGraph " << subGraph[*vi].name << endl;
22
    // }
23

    
24
    // Test if deep copy is performed for aart_points
25
    cout << "Test if deep copy is performed for art_points" << endl;
26
    cout << "&art_points " <<  &aart_points << endl;
27
    cout << "&this->art_points " << &this->art_points << endl;
28
    cout << "art_points[0] " <<  aart_points[0] << endl;
29
    cout << "this->art_points[0] " << this->art_points[0] << endl;
30

    
31
     // create Vertex -> Index Mapping
32
    v_index_map = VertexIndexMap(v_index_std_map);
33
    int i = 0;
34
    BGL_FORALL_VERTICES(vertex, this->subGraph, Graph) {
35
            boost::put(v_index_map, vertex, i);
36
            ++i;
37
    }
38

    
39
    // Deep copy for subGraph
40
    // TODO: optimize - is there anyway that we can avoid using deep copy
41

    
42
    // This is not working
43
    // copy_graph(asubGraph, this->subGraph, vertex_index_map(v_index_map));
44

    
45
    // this->subGraph = Graph(asubGraph);
46

    
47
    // Vertices in this->subGraph
48
    cout << "Vertices in this->subGraph | constructor" << endl;
49
    BGL_FORALL_VERTICES(vertex, this->subGraph, Graph) {
50
        cout << vertex << " " << this->subGraph[vertex].name << endl;
51
    }
52

    
53
    cout << "Vertices in asubGraph | constructor" << endl;
54
    BGL_FORALL_VERTICES(vertex, asubGraph, Graph) {
55
        cout << vertex << " " << asubGraph[vertex].name << endl;
56
    }
57
    init();
58
}
59

    
60
void SubComponent::init() {
61
    // create list of normal vertices
62
    Viter vi, vi_end;
63
    boost::tie(vi, vi_end) = boost::vertices(subGraph);
64
    std::set_difference(vi, vi_end,
65
                        art_points.begin(), art_points.end(),
66
                        back_inserter(normal_vertices)
67
    );
68

    
69

    
70
    cout << "Vertices in this->subGraph | init()" << endl;
71
    BGL_FORALL_VERTICES(vertex, this->subGraph, Graph) {
72
        cout << vertex << " " << this->subGraph[vertex].name << endl;
73
    }
74

    
75
    cout << "Test normal_vertices | init()" << endl;
76
    for (vector<Vertex>::iterator vi = normal_vertices.begin(); vi != normal_vertices.end(); ++vi) {
77
        cout << *vi << " ";
78
        cout << subGraph[*vi].name << endl;
79
    }
80

    
81
    /* STEP 1
82
    ** Compute Link Weight
83
    ** ==> Link Weight is computed by the main Bi Connected Components.
84
    ** That main BCC will set the Link Weight value for each sub-component.
85
    */
86

    
87
    /* STEP 2
88
    ** Compute Traffic Matrix
89
    */
90
//    _initializeTrafficMatrix();
91
//    _computeTrafficMatrix();
92

    
93
    /* STEP 3
94
    ** Compute the Betweenness Centrality
95
    ** The calculation is executed by the main BCCs calling each sub-component
96
    */
97
    // Initialize variables for calculating BC
98
    _initializeBetweennessCentrality();
99
    findBetweennessCentrality();
100
}
101

    
102
VertexVec SubComponent::get_art_points() {
103
    return art_points;
104
}
105

    
106
int SubComponent::num_vertices() {
107
    return boost::num_vertices(subGraph);
108
}
109

    
110
void SubComponent::_initialize_weight() {
111
    for (VertexVecIter vvi = art_points.begin(); vvi != art_points.end(); ++vvi) {
112
        setWeight(*vvi, -1);
113
    }
114
}
115

    
116
void SubComponent::setWeight(Vertex art_point, int value) {
117
    weightMap[art_point] = value;
118
}
119

    
120
int SubComponent::getWeight(Vertex art_point) {
121
    VertexMapIter vmi;
122

    
123
    vmi = weightMap.find(art_point);
124

    
125
    if (vmi != weightMap.end()) {
126
        return weightMap.at(art_point);
127
    }
128
    else {
129
        return 0;
130
    }
131
}
132

    
133
int SubComponent::getReversedWeight(Vertex art_point) {
134
    VertexMapIter vmi;
135

    
136
    vmi = weightMap.find(art_point);
137

    
138
    if (vmi != weightMap.end()) {
139
        return (boost::num_vertices(subGraph) - weightMap.at(art_point) - 1);
140
    }
141
    else {
142
        return 0;
143
    }
144
}
145

    
146
void SubComponent::printWeight() {
147
    for (VertexMapIter vmi = weightMap.begin(); vmi != weightMap.end(); ++vmi) {
148
        cout << subGraph[(*vmi).first].name << " = " << (*vmi).second << endl;
149
    }
150
}
151

    
152
void SubComponent::_find_vertices_with_unknown_weight(VertexVec& unknown_weight_vertices) {
153
    VertexMapIter wi;
154
    Vertex vertex;
155

    
156
    int current_weight;
157
    for (wi = weightMap.begin(); wi != weightMap.end(); ++wi) {
158
        vertex = (*wi).first;
159
        current_weight = (*wi).second;
160

    
161
        if (current_weight == -1) {
162
            unknown_weight_vertices.insert(unknown_weight_vertices.end(), vertex);
163
        }
164
    }
165
}
166

    
167
void SubComponent::_initializeTrafficMatrix() {
168
    // generate_empty_traffic_matrix, with 1 every where, and 0 in the main diagonal
169
    int size = boost::num_vertices(subGraph);
170
    trafficMatrix = vector<vector<int> >(size);
171
    for (int j = 0; j < size; ++j) {
172
        trafficMatrix[j] = vector<int>(size, 1);
173
    }
174

    
175
    // Reset the main diagonal to 0
176
    for (int j = 0; j < size; ++j) {
177
        trafficMatrix[j][j] = 0;
178
    }
179
}
180

    
181
void SubComponent::_setTrafficMatrix(Vertex v_1, Vertex v_2, int value) {
182
    int i_1 = _indexOfVertex(v_1);
183
    int i_2 = _indexOfVertex(v_2);
184
    trafficMatrix[i_1][i_2] = value;
185
    trafficMatrix[i_2][i_1] = value; // because Traffic Matrix is symmetric
186
}
187

    
188
int SubComponent::_indexOfVertex(Vertex v) {
189
    try {
190
        return boost::get(v_index_map, v);
191
    }
192
    catch (exception& e) {
193
        // TODO handle exception here
194
        cout << "ERROR _indexOfVertex() " << e.what() << endl;
195
        return -1;
196
    }
197
}
198

    
199
void SubComponent::_computeTrafficMatrix() {
200
    // Update the value when one vertex is a cut-point, another vertex is not a cut-point
201
    for (int j = 0; j < art_points.size(); ++j) {
202
        for (int k = 0; k < normal_vertices.size(); ++k) {
203
            int communication_intensity = getReversedWeight(art_points[j]) + 1;
204
            _setTrafficMatrix(art_points[j], normal_vertices[k], communication_intensity);
205
        }
206
    }
207

    
208
    // Update the value when both vertices are cut-points
209
    int size = art_points.size();
210
    if (size > 1) {
211
        for (int j = 0; j < size - 1; ++j) {
212
            for (int k = 1; k < size; ++k) {
213
                if (j == k) {
214
                    continue;
215
                }
216

    
217
                int communication_intensity = (
218
                        (getReversedWeight(art_points[j]) + 1) *
219
                        (getReversedWeight(art_points[k]) + 1)
220
                );
221

    
222
                _setTrafficMatrix(art_points[j], art_points[k], communication_intensity);
223
            }
224
        }
225
    }
226
}
227

    
228
int SubComponent::getTrafficMatrix(Vertex v_1, Vertex v_2) {
229
    int i_1 = _indexOfVertex(v_1);
230
    int i_2 = _indexOfVertex(v_2);
231
    try {
232
        return trafficMatrix[i_1][i_2];
233
    }
234
    catch (exception& e) {
235
        cout << "ERROR: getTrafficMatrix: " << e.what() << endl;
236
    }
237

    
238
}
239

    
240
void SubComponent::_initializeBetweennessCentrality() {
241
    v_centrality_vec = CentralityVec(boost::num_vertices(subGraph), 0);
242
    v_centrality_map = CentralityMap(v_centrality_vec.begin(), v_index_map);
243
    cout << "Test v_index_map" << endl;
244
    BGL_FORALL_VERTICES(vertex, subGraph, Graph) {
245
        cout << subGraph[vertex].name << " " << boost::get(v_index_map, vertex) << endl;
246
    }
247

    
248
    cout << "Vertices in this->subGraph | init BC()" << endl;
249
    BGL_FORALL_VERTICES(vertex, this->subGraph, Graph) {
250
        cout << vertex << " " << this->subGraph[vertex].id << endl;
251
    }
252

    
253

    
254
}
255

    
256
void SubComponent::findBetweennessCentrality() {
257
    cout << "****** find BC() *******" << endl;
258
    cout << "Test art_points" << endl;
259
    for (VertexVecIter vi = art_points.begin(); vi != art_points.end(); ++vi) {
260
        cout << *vi << " ";
261
        cout << subGraph[*vi].name << endl;
262
    }
263

    
264
    cout << "Vertices in this->subGraph | find BC()" << endl;
265
    BGL_FORALL_VERTICES(vertex, this->subGraph, Graph) {
266
        cout << vertex << " " << this->subGraph[vertex].id << endl;
267
    }
268

    
269
    cout << "Test normal_vertices 2" << endl;
270
    for (vector<Vertex>::iterator vi = normal_vertices.begin(); vi != normal_vertices.end(); ++vi) {
271
        cout << *vi << " " << endl;
272
        cout << subGraph[*vi].name << endl;
273
    }
274
    cout << "BC abc " << endl;
275
    /* Test v_index_map */
276
    // BGL_FORALL_VERTICES(vertex, subGraph, Graph) {
277
    //     cout << subGraph[vertex].name << " " << boost::get(v_index_map, vertex) << endl;
278
    // }
279

    
280
    // /* Test v_centrality_map
281
    // **
282
    // */
283
    // cout << "v_centrality_map" << endl;
284
    // BGL_FORALL_VERTICES(vertex, subGraph, Graph) {
285
    //     cout << subGraph[vertex].name << endl;
286
    //     // double score = boost::get(v_centrality_map, vertex);
287
    //     // cout << vertex << " " << score << endl;
288
    // }
289

    
290
    // brandes_betweenness_centrality(subGraph, boost::centrality_map(v_centrality_map).vertex_index_map(v_index_map));
291
    cout << "BC done" << endl;
292
}
293

    
294
void SubComponent::printBetweennessCentrality() {
295
    cout << "Vertex betweenness" << endl;
296

    
297
    Viter vi, vi_end;
298
    int i = 0;
299
    for (boost::tie(vi, vi_end) = boost::vertices(subGraph); vi != vi_end; ++vi) {
300
        cout << subGraph[*vi].id << "\t" << v_centrality_vec.at(i) << endl;
301
        ++i;
302
    }
303
}