Revision efed924d custompackages/graph-parser/src/sub_component.cpp

View differences:

custompackages/graph-parser/src/sub_component.cpp
6 6

  
7 7

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

  
11
SubComponent::SubComponent(VertexVec aart_points, Graph asubGraph) : art_points(aart_points), subGraph(asubGraph) {
12
SubComponent::SubComponent(StringSet art_points, Graph sub_graph) : art_points_(art_points), sub_graph_(sub_graph) {
12 13
// SubComponent::SubComponent(VertexVec aart_points, Graph asubGraph) {
13 14
    // art_points = aart_points;
14 15
    // subGraph = asubGraph;
......
21 22
    //     cout << "    subGraph " << subGraph[*vi].name << endl;
22 23
    // }
23 24

  
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 25

  
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();
26
    // init();
58 27
}
59 28

  
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();
29
StringSet SubComponent::art_points() const {
30
    return art_points_;
100 31
}
101 32

  
102
VertexVec SubComponent::get_art_points() {
103
    return art_points;
33
void SubComponent::set_art_points(StringSet& art_points) {
34
    art_points_ = art_points;
104 35
}
105 36

  
106 37
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
    }
38
    return boost::num_vertices(sub_graph_);
165 39
}
166 40

  
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
    }
41
void SubComponent::AddEdge(Router r1, Router r2, Link l) {
42
    cout << "add edge " << r1.label << " - " << r2.label << endl;
174 43

  
175
    // Reset the main diagonal to 0
176
    for (int j = 0; j < size; ++j) {
177
        trafficMatrix[j][j] = 0;
178
    }
179
}
44
    string s1 = r1.id;
45
    string s2 = r2.id;
46
    Vertex v1;
47
    Vertex v2;
180 48

  
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 49
    try {
190
        return boost::get(v_index_map, v);
50
        v1 = get_vertex_from_id(s1);
191 51
    }
192 52
    catch (exception& e) {
193
        // TODO handle exception here
194
        cout << "ERROR _indexOfVertex() " << e.what() << endl;
195
        return -1;
53
        v1 = boost::add_vertex(r1, sub_graph_);
54
        name_vertex_map_[s1] = v1;
196 55
    }
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 56
    try {
232
        return trafficMatrix[i_1][i_2];
57
        v2 = get_vertex_from_id(s2);
233 58
    }
234 59
    catch (exception& e) {
235
        cout << "ERROR: getTrafficMatrix: " << e.what() << endl;
60
        v2 = boost::add_vertex(r2, sub_graph_);
61
        name_vertex_map_[s2] = v2;
236 62
    }
237

  
63
    boost::add_edge(v1, v2, l, sub_graph_);
238 64
}
239 65

  
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

  
66
bool SubComponent::vertex_existed(string s) {
67
    std::map<std::string, Vertex>::iterator it;
68
    it = name_vertex_map_.find(s);
69
    return (it != name_vertex_map_.end());
254 70
}
255 71

  
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;
72
const Vertex& SubComponent::get_vertex_from_id(string s) {
73
    if (vertex_existed(s)) {
74
        return name_vertex_map_[s];
267 75
    }
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;
76
    else {
77
        throw std::runtime_error("Vertex not found\n");
273 78
    }
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 79
}
293 80

  
294
void SubComponent::printBetweennessCentrality() {
295
    cout << "Vertex betweenness" << endl;
81
std::ostream& operator<<(std::ostream& os, const SubComponent& sc) {
82
    cout << "Sub-component" << endl;
83
    outops::operator<<(cout, sc.sub_graph());
84
    outops::operator<<(cout, sc.art_points());
85
    return os;
86
}
296 87

  
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
    }
88
Graph const& SubComponent::sub_graph() const {
89
    return sub_graph_;
303 90
}
91

  

Also available in: Unified diff