Revision cb770240

View differences:

custompackages/graph-parser/src/Makefile
5 5
INCLUDES = -I/usr/local/boost/
6 6

  
7 7
# define the C source files
8
SRCS = main.cpp bi_connected_components.cpp centrality.cpp parser.cpp sub_component.cpp utility.cpp
8
SRCS = main.cpp bi_connected_components.cpp centrality.cpp graph_manager.cpp parser.cpp sub_component.cpp utility.cpp
9 9

  
10 10

  
11 11
# define the C object files
custompackages/graph-parser/src/bi_connected_components.cpp
5 5
#include "bi_connected_components.h"
6 6
using namespace std;
7 7

  
8
BiConnectedComponents::BiConnectedComponents(const Graph &g) : g(g) {
8
/******************************
9
* Public functions
10
******************************/
11
BiConnectedComponents::BiConnectedComponents(GraphManager &gm) : gm_(gm) {
12
    cout << "BCC constructor \n";
9 13
    init();
10
    findBiConnectedComponents();
14
    FindBiConnectedComponents();
11 15
}
12 16

  
13

  
14 17
void BiConnectedComponents::init() {
15
    size_t i = 0; // for indexing in the loop
16

  
17
    // Populate the e_index_map, by changing the value of the original e_index_std_map
18
    e_index_map = EdgeIndexMap(e_index_std_map);
19
    i = 0;
20
    BGL_FORALL_EDGES(edge, g, Graph) {
21
        e_index_std_map.insert(pair<Edge, size_t>(edge, i));
22
        ++i;
23
    }
18
    // Set some variables
19
    num_of_vertices_ = boost::num_vertices(gm_.g_);
24 20

  
25
    this->component_vec = ComponentVec(boost::num_edges(g), 0);
26
    this->component_map = ComponentMap(this->component_vec.begin(), e_index_map);
27

  
28
    // Populate the VertexIndexMap - by using the put() from Property Map
29
    v_index_map = VertexIndexMap(v_index_std_map);
30
    Viter vi, ve; // vertex_iterator, vertex_iterator_end
31
    i = 0;
32
    for (boost::tie(vi, ve) = boost::vertices(g); vi != ve; ++vi) {
33
        boost::put(this->v_index_map, *vi, i);
34
        ++i;
35
    }
21
    component_vec_ = ComponentVec(boost::num_edges(gm_.g_), 0);
22
    component_map_ = ComponentMap(component_vec_.begin(), gm_.e_index_map());
36 23
}
37 24

  
38
void BiConnectedComponents::findBiConnectedComponents() {
39
    cout << "Running findBiConnectedComponents" << endl;
40
    size_t i;
25
/* GETTER */
26
StringSet const& BiConnectedComponents::all_art_points_id() const {
27
    return all_art_points_id_;
28
}
41 29

  
30
/* SUB-COMPONENT */
31
void BiConnectedComponents::FindBiConnectedComponents() {
32
    cout << "Running FindBiConnectedComponents" << endl;
42 33

  
43
    boost::biconnected_components(g, component_map,
44
                                  back_inserter(art_points),
45
                                  boost::vertex_index_map(this->v_index_map));
34
    boost::biconnected_components(gm_.g_, component_map_,
35
                                  back_inserter(art_points_),
36
                                  boost::vertex_index_map(gm_.v_index_map()));
46 37

  
47
    cout << "Articulation points: \n";
48
    set<string> art_point_ids;
49
    graphext::id_of_vertices(g, art_points, art_point_ids);
50
    outops::operator<<(cout, art_point_ids);
38
    // Set some variables
39
    graphext::id_of_some_vertices(gm_.g_, art_points_, all_art_points_id_);
51 40

  
52 41
    // Process the result from boost::biconnected_components
53
    BCCs = Component_t(num_bcc());
54
    verticesInBCC();
55
    // testVerticesInBCC();
56
    processArtPoints();
57
    // testProcessArtPoints();
58
    // _test_set_difference();
59
    createSubComponents();
60
}
42
    BCCs = Component_t(num_of_bcc());
43
    CreateSubComponents();
61 44

  
62
void BiConnectedComponents::createSubComponents() {
63
    // Generating articulation points for each sub-component
64
    for (int i = 0; i < num_bcc(); ++i) {
65
        StringSet art_point_ids;
66
        VertexVec art_points_vec;
67
        art_points_vec = get_art_points_for_component(i);
68
        graphext::id_of_vertices(g, art_points_vec, art_point_ids);
45
    // Calculate Link Weight
46
    cout << "Calculate Link Weight\n";
47
    CalculateLinkWeight();
69 48

  
70
        outops::operator<<(cout, art_point_ids);
71
        BCCs[i].set_art_points(art_point_ids);
72
    }
49
    // Calculate Traffic Matrix
50
    cout << "Calculate Traffic Matrix\n";
51
    CalculateTrafficMatrix();
73 52

  
53
    print();
54
}
55

  
56
void BiConnectedComponents::CreateSubComponents() {
74 57
    // Generating subgraph for each sub-component
75
    BGL_FORALL_EDGES(edge, g, Graph) {
76
        int comp_index = boost::get(component_map, edge);
77
        Router r1 = g[boost::source(edge, g)];
78
        Router r2 = g[boost::target(edge, g)];
79
        Link l = g[edge];
58
    BGL_FORALL_EDGES(edge, gm_.g_, Graph) {
59
        int comp_index = boost::get(component_map_, edge);
60
        Router r1 = gm_.g_[boost::source(edge, gm_.g_)];
61
        Router r2 = gm_.g_[boost::target(edge, gm_.g_)];
62
        Link l = gm_.g_[edge];
80 63
        BCCs[comp_index].AddEdge(r1, r2, l);
81 64
    }
82 65

  
83
    for (int i = 0; i < num_bcc(); ++i) {
84
        cout << BCCs[i] << endl;
66
    // Finalizing each sub components
67
    for (int i = 0; i < num_of_bcc(); ++i) {
68
        BCCs[i].FinalizeSubComponent(all_art_points_id_);
85 69
    }
86 70
}
87 71

  
88
void BiConnectedComponents::print() {
89
    // Test the biconnected components
90
    Eiter ei, ei_end;
91
    size_t i = 0;
92
    for (boost::tie(ei, ei_end) = boost::edges(g); ei != ei_end; ++ei) {
93
        string source = g[(*ei).m_source].id;
94
        string target = g[(*ei).m_target].id;
95
        edges_size_type comp = this->component_vec.at(i);
96
        cout << source << " " << target << " " << comp << endl;
97
        ++i;
72
/* LINK WEIGHT */
73
void BiConnectedComponents::CalculateLinkWeight() {
74
    initialize_weight();
75
    initialize_queue();
76

  
77
    while (!Q.empty()) {
78
        QueueElem elem = Q.front();
79
        Q.pop();
80
        int comp_index = elem.component_index;
81
        string vertex_id = elem.vertex_id;
82

  
83
        if (elem.type == "component_vertex_pair") {
84
            // cout << "component_vertex_pair: " << comp_index << " - " << vertex_id << endl;
85
            process_component_vertex_pair(comp_index, vertex_id);
86
        }
87
        else if (elem.type == "vertex_component_pair") {
88
            // cout << "vertex_component_pair: " << comp_index << " - " << vertex_id << endl;
89
            process_vertex_component_pair(comp_index, vertex_id);
90
        }
98 91
    }
99 92
}
100 93

  
101
int BiConnectedComponents::num_bcc() {
102
    if (num_of_bcc == -1) { // calculate it
94
/* TRAFFIC MATRIX */
95
void BiConnectedComponents::CalculateTrafficMatrix() {
96
    for (int i = 0; i < num_of_bcc_; ++i) {
97
        BCCs[i].CalculateTrafficMatrix();
98
    }
99
}
100

  
101
/* HELPERS */
102
int BiConnectedComponents::num_of_bcc() {
103
    if (num_of_bcc_ == -1) { // calculate it
103 104
        // +1 to counteract for the zero-indexing
104
        num_of_bcc = *std::max_element(component_vec.begin(), component_vec.end()) + 1;
105
        num_of_bcc_ = *std::max_element(component_vec_.begin(), component_vec_.end()) + 1;
105 106
    }
106 107

  
107
    return num_of_bcc;
108
    return num_of_bcc_;
108 109
}
109 110

  
110
void BiConnectedComponents::verticesInBCC() {
111
    size_t size = num_bcc();
112

  
113
    vector<set<Vertex> > set_vertices(size);
111
/* HELPERS FOR OUTPUTTING RESULT */
112
void BiConnectedComponents::print() {
113
    for (int i = 0; i < num_of_bcc(); ++i) {
114
        cout << BCCs[i] << endl;
115
    }
116
}
114 117

  
115
    Edge edge;
116
    Vertex source;
117
    Vertex target;
118
std::ostream& operator<<(std::ostream& os, const BiConnectedComponents& rhs) {
119
    cout << "\n\nBi-Connected Components\n\n";
120
    cout << rhs.gm_;
118 121

  
119
    int comp_id;
120
    BGL_FORALL_EDGES(edge, g, Graph) {
121
        comp_id = boost::get(component_map, edge);
122
        source = edge.m_source;
123
        target = edge.m_target;
124
        set_vertices[comp_id].insert(source);
125
        set_vertices[comp_id].insert(target);
126
    }
122
    cout << "\nArticulation points:\n";
123
    outops::operator<<(cout, rhs.all_art_points_id());
124
    return os;
127 125

  
128
    bcc_vertices = vector<VertexVec>(size);
129
    size_t i = 0;
130
    for (i = 0; i < size; ++i) {
131
        bcc_vertices[i] = vector<Vertex>(set_vertices[i].begin(), set_vertices[i].end());
132
    }
126
    // TODO: output the result of BCC
127
    // Test the biconnected components
128
    // Eiter ei, ei_end;
129
    // size_t i = 0;
130
    // for (boost::tie(ei, ei_end) = boost::edges(gm_.g_); ei != ei_end; ++ei) {
131
    //     string source = gm_.g_[(*ei).m_source].id;
132
    //     string target = gm_.g_[(*ei).m_target].id;
133
    //     edges_size_type comp = component_vec_.at(i);
134
    //     cout << source << " " << target << " " << comp << endl;
135
    //     ++i;
136
    // }
133 137
}
134 138

  
135
void BiConnectedComponents::testVerticesInBCC() {
136
    size_t i = 0;
137
    for (i; i < num_of_bcc; ++i) {
138
        vector<Vertex> abc = bcc_vertices[i];
139
        cout << "vertices in BCC " << i << endl;
140
        for (int j = 0; j < abc.size(); ++j) {
139
/******************************
140
* Private functions
141
******************************/
141 142

  
142
            cout << g[bcc_vertices[i][j]].id << endl;
143
        }
143
/* LINK WEIGHT */
144
void BiConnectedComponents::initialize_weight() {
145
    for (int i = 0; i < num_of_bcc_; ++i) {
146
        BCCs[i].initialize_weight();
144 147
    }
145 148
}
146 149

  
147
bool BiConnectedComponents::hasVertex(Vertex v, int comp_index) {
148
    vector<Vertex> vv = bcc_vertices[comp_index];
149
    vector<Vertex>::iterator it;
150

  
151
    it = std::find(vv.begin(), vv.end(), v);
152
    if (it == vv.end()) {
153
        return false;
154
    }
155
    else {
156
        return true;
150
void BiConnectedComponents::initialize_queue() {
151
    for (int i = 0; i < num_of_bcc_; ++i) {
152
        if (BCCs[i].art_points_id().size() == 1) {
153
            string vertex_id = *(BCCs[i].art_points_id().begin());
154
            string type = "component_vertex_pair";
155
            QueueElem elem = {
156
                .component_index = i,
157
                .vertex_id = vertex_id,
158
                .type = type,
159
            };
160

  
161
            Q.push(elem);
162
        }
157 163
    }
158 164
}
159 165

  
160
void BiConnectedComponents::processArtPoints() {
161
    // For each articulation points, quickly identify (through the std::map) all the component containing those points.
162
    art_point_component_map = ArtPointComponentMap(art_point_component_std_map);
163

  
164
    std::vector<Vertex>::iterator vi = art_points.begin();
165
    std::vector<int>::iterator ii;
166

  
167
    for (vi; vi < art_points.end(); ++vi) {
168
        Vertex articulation_point = *vi;
169

  
170
        size_t i = 0;
171
        std::vector<int> components;
172
        for (i = 0; i < num_of_bcc; ++i) {
173
            ii = components.end();
174
            if (hasVertex(articulation_point, i)) {
175
                components.insert(ii, i);
166
void BiConnectedComponents::process_component_vertex_pair(int comp_index, string vertex_id) {
167
    int size = BCCs[comp_index].num_of_vertices() - 1;
168
    for (string s : BCCs[comp_index].art_points_id()) {
169
        if (s.compare(vertex_id) != 0) {
170
            int weight = BCCs[comp_index].get_weight_map(s);
171
            if (weight != -1) {
172
                size += num_of_vertices_ - weight - 1;
176 173
            }
177 174
        }
178
        boost::put(art_point_component_map, articulation_point, components);
179
    }
180

  
181
    // For each component, quickly identify (through the std::map) all the articulation points belonging to it.
182
    component_art_point_map = ComponentArtPointMap(component_art_point_std_map);
183

  
184
    BccIter_t bi = bcc_vertices.begin();
185
    BccIter_t bi_end = bcc_vertices.end();
186

  
187
    VertexVecIter vvi = art_points.begin();
188
    VertexVecIter vvi_end = art_points.end();
189

  
190
    int i = 0;
191
    for (bi; bi != bi_end; ++bi) {
192
        // intersection
193
        VertexVec component = *bi;
194
        VertexVec intersection_result;
195
        std::set_intersection(component.begin(), component.end(), vvi, vvi_end, back_inserter(intersection_result));
196

  
197
        boost::put(component_art_point_map, i, intersection_result);
198
        ++i;
199

  
200 175
    }
176
    int link_weight = size;
177
    BCCs[comp_index].update_weight_map(vertex_id, link_weight);
178
    find_unknown_weight_wrt_art_point(vertex_id);
201 179
}
202 180

  
181
void BiConnectedComponents::find_unknown_weight_wrt_art_point(string vertex_id) {
182
    int count = 0;
183
    int comp_index = -1;
184
    for (int i = 0; i < num_of_bcc_; ++i) {
185
        if (BCCs[i].vertex_exists(vertex_id)) {
186
            if (BCCs[i].get_weight_map(vertex_id) == -1) {
187
                ++count;
188
                comp_index = i;
189
            }
203 190

  
204
void BiConnectedComponents::testProcessArtPoints() {
205
    std::vector<Vertex>::iterator vi = art_points.begin();
206
    std::vector<int>::iterator ii;
207

  
208
    for (vi; vi < art_points.end(); ++vi) {
209
        Vertex articulation_point = *vi;
210

  
211
        std::vector<int> components = boost::get(art_point_component_map, articulation_point);
212

  
213
        cout << "Components belonging to articulation point " << g[articulation_point].label << endl;
214

  
215
        for (ii = components.begin(); ii < components.end(); ++ii) {
216
            cout << *ii << endl;
191
            if (count > 1) break;
217 192
        }
218 193
    }
219 194

  
220
    VertexVecIter vvi;
221
    int i = 0;
222
    for (i; i < num_bcc(); ++i) {
223
        VertexVec vv = boost::get(component_art_point_map, i);
195
    if (count == 1) {
196
        // Add new element to QueueElem
197
        QueueElem elem = {
198
            .component_index = comp_index,
199
            .vertex_id = vertex_id,
200
            .type = "vertex_component_pair"
201
        };
224 202

  
225
        cout << "Articulation points from the component " << i << endl;
226

  
227
        for (vvi = vv.begin(); vvi != vv.end(); ++vvi) {
228
            cout << *vvi << endl;
229
        }
203
        // cout << "Add vertex_component_pair: " << comp_index << " - " << vertex_id << endl;
204
        Q.push(elem);
230 205
    }
231 206
}
232 207

  
233
VertexVec BiConnectedComponents::get_art_points_for_component(int comp_index) {
234
    return boost::get(component_art_point_map, comp_index);
235
}
236

  
237
vector<int> BiConnectedComponents::get_components_for_art_point(Vertex vertex) {
238
    return boost::get(art_point_component_map, vertex);
239
}
240

  
241
int BiConnectedComponents::num_of_vertices_in_component(int comp_index) {
242
    return bcc_vertices[comp_index].size();
243
}
208
void BiConnectedComponents::process_vertex_component_pair(int comp_index, string vertex_id) {
209
    int size = 0;
244 210

  
245
VertexVec BiConnectedComponents::get_normal_vertices_for_component(int comp_index) {
246
    VertexVec normal_points;
247
    std::set_difference(bcc_vertices[comp_index].begin(),
248
                        bcc_vertices[comp_index].end(),
249
                        art_points.begin(),
250
                        art_points.end(),
251
                        back_inserter(normal_points)
211
    for (int i = 0; i < num_of_bcc_; ++i) {
212
        if (i != comp_index) {
213
            if (BCCs[i].vertex_exists(vertex_id)) {
214
                int weight = BCCs[i].get_weight_map(vertex_id);
215
                if (weight != -1) {
216
                    size += weight;
217
                }
218
            }
219
        }
220
    }
252 221

  
253
    );
254
    return normal_points;
222
    int link_weight = num_of_vertices_ - 1 - size;
223
    BCCs[comp_index].update_weight_map(vertex_id, link_weight);
224
    find_unknown_weight_wrt_component(comp_index);
255 225
}
256 226

  
257
// void BiConnectedComponents::compute_weight() {
258
//     _initialize_weight();
259
//     _initialize_queue();
260

  
261
//     while (!Q.empty()) {
262
//         QueueElem elem = Q.front();
263
//         Q.pop();
264
//         int comp_index = elem.component_index;
265
//         Vertex current_art_point = elem.art_point;
266

  
267
//         if (elem.type == "component_vertex_pair") {
268
//             int size = BCCs[comp_index].num_vertices() - 1;
269
//             VertexVec art_points = BCCs[comp_index].art_points();
270

  
271
//             // TODO: I assume here that vvi != art_points.end(), aka. the element is always found.
272
//             VertexVecIter vvi;
273
//             vvi = std::find(art_points.begin(), art_points.end(), current_art_point);
274
//             try {
275
//                 art_points.erase(vvi);
276
//             }
277
//             catch (exception& e) {
278
//                 cout << "Standard exception: " << e.what() << endl;
279
//             }
280

  
281
//             for (vvi = art_points.begin(); vvi != art_points.end(); ++vvi) {
282
//                 cout << "    " << g[*vvi].label << endl;
283
//                 int weight = BCCs[comp_index].getWeight(*vvi);
284
//                 if (weight != -1) {
285
//                     size += boost::num_vertices(g) - weight - 1;
286
//                 }
287
//             }
288

  
289
//             int link_weight = size;
290
// //            _verify_weight(comp_index, current_art_point, link_weight);
291
//             BCCs[comp_index].setWeight(current_art_point, link_weight);
292

  
293
//             _find_unknown_weight_wrt_art_point(current_art_point);
294
//         }
295

  
296
//         if (elem.type == "vertex_component_pair") {
297
//             vector<int> comp_indices = get_components_for_art_point(current_art_point);;
298

  
299
//             vector<int>::iterator vi;
300
//             vi = std::find(comp_indices.begin(), comp_indices.end(), comp_index);
301
//             try {
302
//                 comp_indices.erase(vi);
303
//             }
304
//             catch (exception& e) {
305
//                 cout << "Standard exception: " << e.what() << endl;
306
//             }
307

  
308
//             int size = 0;
309
//             for (vi = comp_indices.begin(); vi != comp_indices.end(); ++vi) {
310
//                 int weight = BCCs[*vi].getWeight(current_art_point);
311
//                 if (weight != -1) {
312
//                     size += weight;
313
//                 }
314
//             }
315

  
316
//             int link_weight = boost::num_vertices(g) - 1 - size;
317
// //            _verify_weight(comp_index, current_art_point, link_weight);
318
//             BCCs[comp_index].setWeight(current_art_point, link_weight);
319
//             _find_unknown_weight_wrt_component(comp_index);
320

  
321
//         }
322
//     }
323
// }
324

  
325
// void BiConnectedComponents::_initialize_weight() {
326
//     ComponentIter_t ci;
327
//     for (ComponentIter_t ci = BCCs.begin(); ci != BCCs.end(); ++ci) {
328
//         (*ci)._initialize_weight();
329
//     }
330
// }
331

  
332
// void BiConnectedComponents::_initialize_queue() {
333
//     VertexVecIter vvi;
334

  
335
//     int i = 0;
336
//     VertexVec current_art_points;
337
//     for (i; i < num_bcc(); ++i) {
338
//         current_art_points = BCCs[i].art_points();
339
//         if (curr ent_art_points.size() == 1) {
340
//             // creating element for queue Q
341
//             Vertex art_point = current_art_points[0];
342
//             string type = "component_vertex_pair";
343
//             QueueElem qe = {
344
//                     .component_index = i,
345
//                     .art_point = art_point,
346
//                     .type = type,
347
//             };
348

  
349
//             Q.push(qe);
350
//         }
351
//     }
352
// }
353

  
354
// void BiConnectedComponents::_find_unknown_weight_wrt_art_point(Vertex art_point) {
355
//     int num_of_uncomputed_weight = 0;
356
//     vector<int> uncomputed_weight_component_indices;
357

  
358
//     size_t i;
359
//     for (i = 0; i < num_bcc(); ++i) {
360
//         if (hasVertex(art_point, i)) {
361
//             // Check if value -1 appear exactly 1 time
362
//             if (BCCs[i].getWeight(art_point) == -1) {
363
//                 num_of_uncomputed_weight += 1;
364
//                 uncomputed_weight_component_indices.insert(uncomputed_weight_component_indices.end(), i);
365
//             }
366
//         }
367

  
368
//         if (num_of_uncomputed_weight > 1) {
369
//             break;
370
//         }
371
//     }
372

  
373
//     if (num_of_uncomputed_weight == 1) {
374
//         QueueElem elem = {
375
//                 component_index: uncomputed_weight_component_indices[0],
376
//                 art_point: art_point,
377
//                 type: "vertex_component_pair",
378
//         };
379
//         Q.push(elem);
380
//     }
381
// }
382

  
383
// void BiConnectedComponents::_find_unknown_weight_wrt_component(int comp_index) {
384
//     VertexVec unknown_weight_vertices;
385
//     BCCs[comp_index]._find_vertices_with_unknown_weight(unknown_weight_vertices);
386

  
387
//     if (unknown_weight_vertices.size() == 1) {
388
//         QueueElem elem = {
389
//                 .component_index = comp_index,
390
//                 .art_point = unknown_weight_vertices[0],
391
//                 .type = "component_vertex_pair",
392
//         };
393

  
394
//         Q.push(elem);
395
//     }
396
// }
397

  
398
// void BiConnectedComponents::print_weight() {
399
//     for (int i = 0; i < num_bcc(); ++i) {
400
//         BCCs[i].printWeight();
401
//     }
402
// }
403

  
404
// void BiConnectedComponents::findBetweennessCentrality() {
405
//     for (int i = 0; i < num_bcc(); ++i) {
406
//         // BCCs[i]._computeTrafficMatrix();
407
//         cout << "###########" << endl;
408
//         _print_art_points();
409
//         cout << "###########" << endl;
410
//         BCCs[i].findBetweennessCentrality();
411
//     }
412
// }
413

  
414
// void BiConnectedComponents::printBetweennessCentrality() {
415
//     for (int i = 0; i < num_bcc(); ++i) {
416
//         BCCs[i].printBetweennessCentrality();
417
//     }
418
// }
419

  
420
// void BiConnectedComponents::_print_art_points() {
421
//     for (int i = 0; i < art_points.size(); ++i) {
422
//         cout << &art_points[i] << endl;
423
//     }
424
// }
425

  
426
// void BiConnectedComponents::_test_set_difference() {
427
//     VertexVec component = bcc_vertices[0];
428
//     VertexVec intersection_result;
429

  
430
//     cout << "******** Test set_difference ********" << endl;
431
//     cout << "  Component" << endl;
432
//     for (VertexVecIter vvi = component.begin(); vvi != component.end(); ++vvi) {
433
//         cout << "\t" << *vvi << endl;
434
//     }
435
//     cout << "  Articulation points" << endl;
436
//     cout << "  " << &art_points[0] << endl;
437
//     cout << "  " << &art_points[1] << endl;
438

  
439
//     for (VertexVecIter vvi = art_points.begin(); vvi != art_points.end(); ++vvi) {
440
//         cout << "\t" << *vvi << endl;
441
//     }
442

  
443
//     VertexVec copy_art_points = VertexVec(art_points);
444
//     cout << "  Copy Articulation points" << endl;
445
//     cout << "  " << &copy_art_points << endl;
446
//     // cout << "  " << &(*copy_art_points) << endl;
447
//     cout << "  " << &(copy_art_points[0]) << " " << copy_art_points[0] << endl;
448
//     cout << "    " << &(*(&copy_art_points[0])) << " " << *(&copy_art_points[0]) << endl;
449
//     cout << "  " << &copy_art_points[1] << " " << copy_art_points[1] << endl;
450
//     for (VertexVecIter vvi = copy_art_points.begin(); vvi != copy_art_points.end(); ++vvi) {
451
//         cout << "\t" << *vvi << endl;
452
//     }
453

  
454
//     std::set_intersection(component.begin(), component.end(), art_points.begin(), art_points.end(), back_inserter(intersection_result));
455

  
456
//     cout << "  Intersection result" << endl;
457
//     for (VertexVecIter vvi = intersection_result.begin(); vvi != intersection_result.end(); ++vvi) {
458
//         cout << "\t" << *vvi << endl;
459
//     }
460

  
461
//     VertexVec difference_result;
462
//     std::set_intersection(component.begin(), component.end(), art_points.begin(), art_points.end(), back_inserter(difference_result));
463

  
464
//     cout << "  Difference result" << endl;
465
//     for (VertexVecIter vvi = difference_result.begin(); vvi != difference_result.end(); ++vvi) {
466
//         cout << "\t" << *vvi << endl;
467
//     }
468
// }
227
void BiConnectedComponents::find_unknown_weight_wrt_component(int comp_index) {
228
    // The 'counting' solution is found here: http://stackoverflow.com/questions/5517615/counting-number-of-same-values-in-map
229
    typedef NameToIntMap::value_type MapEntry;
230
    int count = std::count_if(
231
        BCCs[comp_index].weight_map().begin(),
232
        BCCs[comp_index].weight_map().end(),
233
        second_equal_to<MapEntry>(-1));
234

  
235
    if (count == 1) {
236
        // Find the vertex id for the vertex with unknown link weight
237
        string vertex_id = BCCs[comp_index].first_vertex_id_with_unknown_weight();
238

  
239
        QueueElem elem = {
240
            .component_index = comp_index,
241
            .vertex_id = vertex_id,
242
            .type = "component_vertex_pair",
243
        };
244
        // cout << "Add component_vertex_pair: " << comp_index << " - " << vertex_id << endl;
245
        Q.push(elem);
246
    }
247
}
custompackages/graph-parser/src/bi_connected_components.h
8 8
#include <boost/graph/biconnected_components.hpp>
9 9
#include <queue>
10 10
#include "common.h"
11
#include "parser.h"
11
#include "parser.h" // ? check to remove
12 12
#include "utility.h"
13 13
#include "sub_component.h"
14
#include "graph_manager.h"
14 15

  
15 16

  
16 17
typedef std::vector<edges_size_type> ComponentVec;
17 18
typedef boost::iterator_property_map<ComponentVec::iterator, EdgeIndexMap> ComponentMap;
18 19

  
19
typedef map<Vertex, vector<int> > ArtPointComponentStdMap;
20
typedef boost::associative_property_map<ArtPointComponentStdMap> ArtPointComponentMap;
20
typedef map<string, vector<int> > VertexIdToComponentStdMap;
21
typedef boost::associative_property_map<VertexIdToComponentStdMap> VertexIdToComponentMap;
21 22

  
22
typedef std::map<int, vector<Vertex> > ComponentArtPointStdMap;
23
typedef boost::associative_property_map<ComponentArtPointStdMap> ComponentArtPointMap;
23
typedef std::map<int, vector<string> > ComponentToVertexIdStdMap;
24
typedef boost::associative_property_map<ComponentToVertexIdStdMap> ComponentToVertexIdMap;
24 25

  
25 26
typedef vector<vector<Vertex> > Bcc_t;
26 27
typedef vector<vector<Vertex> >::iterator BccIter_t;
27 28

  
28

  
29

  
30 29
typedef struct {
31 30
    int component_index;
32
    Vertex art_point;
31
    string vertex_id;
33 32
    string type;
34 33
} QueueElem;
35 34

  
36 35
class BiConnectedComponents {
37
private:
38
    // EdgeIndexMap - boost will return the component id that each edge in the graph belongs to.
39
    StdEdgeIndexMap e_index_std_map;
40
    EdgeIndexMap e_index_map;
41

  
42
    // VertexIndexMap - since we use listS instead of vecS, this one maps each vertex to an id
43
    StdVertexIndexMap v_index_std_map;
36
public:
37
    BiConnectedComponents(GraphManager &gm);
38
    void init();
44 39

  
45
    int num_of_bcc = -1;
40
    // Getter functions
41
    set<string> const& all_art_points_id() const;
42
    int num_of_vertices() const;
46 43

  
47
    std::queue<QueueElem> Q;
44
    // SUB-COMPONENT
45
    void FindBiConnectedComponents();
46
    void CreateSubComponents();
48 47

  
49
public:
50
    typedef vector<SubComponent> Component_t;
51
    typedef vector<SubComponent>::iterator ComponentIter_t;
48
    // LINK WEIGHT - calculation for all sub-components
49
    void CalculateLinkWeight();
52 50

  
53
    Graph g;
51
    // TRAFFIC MATRIX - calculation for all sub-components
52
    void CalculateTrafficMatrix();
54 53

  
55
    VertexIndexMap v_index_map;
56
    ComponentVec component_vec;
57
    ComponentMap component_map;
54
    // HELPERS
55
    int num_of_bcc();
58 56

  
59
    vector<Vertex> art_points;
57
    // HELPERS FOR OUTPUTTING RESULT
58
    void print();
59
    friend std::ostream& operator<<(std::ostream& os, const BiConnectedComponents& rhs);
60 60

  
61
    Bcc_t bcc_vertices;
61
    // Public variables
62
    GraphManager gm_;
63
    typedef vector<SubComponent> Component_t;
64
    typedef vector<SubComponent>::iterator ComponentIter_t;
62 65
    Component_t BCCs;
63 66

  
64
    ArtPointComponentStdMap art_point_component_std_map;
65
    ArtPointComponentMap art_point_component_map;
67
private:
68
    // LINK WEIGHT - calculation for all sub-components
69
    void initialize_weight();
70
    void initialize_queue();
71
    void process_component_vertex_pair(int comp_index, string vertex_id);
72
    void process_vertex_component_pair(int comp_index, string vertex_id);
73
    void find_unknown_weight_wrt_art_point(string vertex_id);
74
    void find_unknown_weight_wrt_component(int comp_index);
66 75

  
67
    ComponentArtPointStdMap component_art_point_std_map;
68
    ComponentArtPointMap component_art_point_map;
76
    // Private variables
77
    ComponentVec component_vec_;
78
    ComponentMap component_map_;
79
    vector<Vertex> art_points_;
69 80

  
81
    int num_of_bcc_ = -1;
82
    int num_of_vertices_ = -1;
70 83

  
71
    BiConnectedComponents(const Graph &g);
72
    void init();
73
    void findBiConnectedComponents();
74
    void createSubComponents();
75
    void print();
84
    StringSet all_art_points_id_;
76 85

  
77
    int num_bcc();
78
    void verticesInBCC();
79
    void testVerticesInBCC();
86
    std::queue<QueueElem> Q;
80 87

  
81
    bool hasVertex(Vertex v, int comp_index);
88
    // Old code
82 89
    void processArtPoints();
83 90
    void testProcessArtPoints();
84 91

  
85
    VertexVec get_art_points_for_component(int comp_index);
86
    vector<int> get_components_for_art_point(Vertex vertex);
87

  
88 92
    VertexVec get_normal_vertices_for_component(int comp_index);
89 93

  
90
    int num_of_vertices_in_component(int comp_index);
91

  
92
    // Calculate link weight (component tree weight)
93
    void compute_weight();
94
    void _initialize_weight();
95
    void _initialize_queue();
96
    void _find_unknown_weight_wrt_art_point(Vertex art_point);
97
    void _find_unknown_weight_wrt_component(int comp_index);
98
    void _find_unknown_weight_for_component(int comp_index, VertexVec& unknown_weight_vertices);
99
    bool _verify_weight(int comp_index, Vertex art_point, int weight);
100
    void print_weight();
101

  
102 94
    // Calculate Betweenness Centrality
103 95
    void findBetweennessCentrality();
104 96
    void printBetweennessCentrality();
custompackages/graph-parser/src/common.h
55 55
typedef std::pair<Eiter, Eiter> Epair;
56 56
typedef boost::graph_traits<Graph>::edges_size_type edges_size_type;
57 57

  
58
typedef map<Vertex, size_t> StdVertexIndexMap;
58
typedef map<Vertex, size_t> VertexIndexStdMap;
59 59
// This property map is an adaptor that converts any type that is a model of Unique Associative Container such as std::map into a mutable Lvalue Property Map.
60
typedef boost::associative_property_map<StdVertexIndexMap> VertexIndexMap;
60
typedef boost::associative_property_map<VertexIndexStdMap> VertexIndexMap;
61 61

  
62
typedef map<Edge, size_t> StdEdgeIndexMap;
63
typedef boost::associative_property_map<StdEdgeIndexMap> EdgeIndexMap;
62
typedef map<Edge, size_t> EdgeIndexStdMap;
63
typedef boost::associative_property_map<EdgeIndexStdMap> EdgeIndexMap;
64 64

  
65 65
typedef std::vector<Vertex> VertexVec;
66 66
typedef std::vector<Vertex>::iterator VertexVecIter;
......
68 68
typedef std::map<Vertex, int> VertexMap;
69 69
typedef std::map<Vertex, int>::iterator VertexMapIter;
70 70

  
71
// TODO: this StringVec is currently un-used
71
typedef std::map<std::string, int> NameToIntMap;
72

  
72 73
typedef std::vector<std::string> StringVec;
73 74
typedef std::vector<std::string>::iterator StringVecIter;
74 75

  
custompackages/graph-parser/src/graph_manager.cpp
1
#include "graph_manager.h"
2

  
3
GraphManager::GraphManager() {
4
    v_index_map_ = VertexIndexMap(v_index_std_map_);
5
    e_index_map_ = EdgeIndexMap(e_index_std_map_);
6
}
7

  
8
GraphManager::GraphManager(const GraphManager& other) {
9
    cout << "\n\n*******COPY CONSTRUCTOR******\n\n";
10
    g_ = other.g_;
11
    reset_v_id_vertex_map();
12
    reset_v_index_map();
13
    reset_e_index_map();
14
}
15

  
16
GraphManager& GraphManager::operator=(GraphManager& rhs) {
17
    cout << "\n\n*******ASSIGNMENT OPERATOR******\n\n";
18
    g_ = rhs.g_;
19
    reset_v_id_vertex_map();
20
    reset_v_index_map();
21
    reset_e_index_map();
22

  
23
    return *this;
24
}
25

  
26
void GraphManager::AddEdge(VertexProperties vp1, VertexProperties vp2, EdgeProperties ep) {
27
    // cout << "add edge GM " << vp1.label << " - " << vp2.label << endl;
28

  
29
    string s1 = vp1.id;
30
    string s2 = vp2.id;
31
    Vertex v1;
32
    Vertex v2;
33

  
34
    try {
35
        v1 = get_vertex_from_id(s1);
36
    }
37
    catch (exception& e) {
38
        v1 = boost::add_vertex(vp1, g_);
39
        v_id_vertex_map_[s1] = v1;
40
        update_v_index_map(v1);
41
    }
42
    try {
43
        v2 = get_vertex_from_id(s2);
44
    }
45
    catch (exception& e) {
46
        v2 = boost::add_vertex(vp2, g_);
47
        v_id_vertex_map_[s2] = v2;
48
        update_v_index_map(v2);
49
    }
50

  
51
    Edge e;
52
    bool inserted;
53
    boost::tie(e, inserted) = boost::add_edge(v1, v2, ep, g_);
54
    update_e_index_map(e);
55
    // print_e_index_map();
56

  
57
    // Print the VertexIndexMap and EdgeIndexMap
58
    // print_v_index_map();
59
    // graphext::print_v_index_map(g_, v_index_map_);
60
}
61

  
62
bool GraphManager::vertex_existed(string s) {
63
    std::map<std::string, Vertex>::iterator it;
64
    it = v_id_vertex_map_.find(s);
65
    return (it != v_id_vertex_map_.end());
66
}
67

  
68
const Vertex& GraphManager::get_vertex_from_id(string s) {
69
    if (vertex_existed(s)) {
70
        return v_id_vertex_map_[s];
71
    }
72
    else {
73
        throw std::runtime_error("Vertex not found\n");
74
    }
75
}
76

  
77
void GraphManager::ResetVerticesAndEdgesIndexMap() {
78
    v_index_std_map_.erase(v_index_std_map_.begin(), v_index_std_map_.end());
79
    e_index_std_map_.erase(e_index_std_map_.begin(), e_index_std_map_.end());
80
    int i;
81

  
82
    // Reset VertexIndexMap
83
    i = 0;
84
    BGL_FORALL_VERTICES(v, g_, Graph) {
85
        boost::put(v_index_map_, v, i);
86
        ++i;
87
    }
88

  
89
    // Reset EdgeIndexMap
90
    i = 0;
91
    BGL_FORALL_EDGES(e, g_, Graph) {
92
        boost::put(e_index_map_, e, i);
93
        ++i;
94
    }
95
}
96

  
97
std::ostream& operator<<(std::ostream& os, const GraphManager& gm) {
98
    cout << "Graph Manager: " << endl;
99
    outops::operator<<(cout, gm.g_);
100
    return os;
101
}
102

  
103
void GraphManager::print_v_index_map() {
104
    graphext::print_v_index_map(g_, v_index_map_);
105
}
106

  
107
void GraphManager::print_e_index_map() {
108
    std::list<std::string> outputs;
109
    BGL_FORALL_EDGES_T(e, g_, Graph) {
110
        int index = boost::get(e_index_map_, e);
111
        std::string source_id = g_[boost::source(e, g_)].id;
112
        std::string target_id = g_[boost::target(e, g_)].id;
113
        outputs.push_back("edge (" + source_id + ", " + target_id + ")" + ": " + std::to_string(index));
114
    }
115

  
116
    using namespace boost::spirit::karma;
117
    cout << "Edge Index Map:\n";
118
    cout << format("[\n  " << (auto_ % "\n  ") << "\n]\n", outputs);
119
}
120

  
121
const VertexIndexMap& GraphManager::v_index_map() const {
122
    return v_index_map_;
123
}
124

  
125
const EdgeIndexMap& GraphManager::e_index_map() const {
126
    return e_index_map_;
127
}
128

  
129
void GraphManager::reset_v_id_vertex_map() {
130
    v_id_vertex_map_ = NameVertexMap();
131
    BGL_FORALL_VERTICES(v, g_, Graph) {
132
        string id = g_[v].id;
133
        v_id_vertex_map_[id] = v;
134
    }
135
}
136

  
137
void GraphManager::reset_v_index_map() {
138
    v_index_std_map_ = VertexIndexStdMap();
139
    v_index_map_ = VertexIndexMap(v_index_std_map_);
140
    int i = 0;
141
    BGL_FORALL_VERTICES(v, g_, Graph) {
142
        boost::put(v_index_map_, v, i);
143
        ++i;
144
    }
145
}
146

  
147
void GraphManager::reset_e_index_map() {
148
    e_index_std_map_ = EdgeIndexStdMap();
149
    e_index_map_ = EdgeIndexMap(e_index_std_map_);
150
    int i = 0;
151
    BGL_FORALL_EDGES(e, g_, Graph) {
152
        boost::put(e_index_map_, e, i);
153
        ++i;
154
    }
155
}
156

  
157
void GraphManager::update_v_index_map(Vertex new_vertex) {
158
    int index = boost::num_vertices(g_);
159
    v_index_std_map_[new_vertex] = index - 1;
160
}
161

  
162
void GraphManager::update_e_index_map(Edge new_edge) {
163
    int index = boost::num_edges(g_);
164
    e_index_std_map_[new_edge] = index - 1;
165
}
custompackages/graph-parser/src/graph_manager.h
1
//
2
// Created by quynh on 1/15/15.
3
//
4

  
5
#ifndef GRAPH_PARSER_GRAPH_MANAGER_H
6
#define GRAPH_PARSER_GRAPH_MANAGER_H
7

  
8
#include "common.h"
9
#include "utility.h"
10

  
11
class GraphManager {
12
public:
13
    typedef boost::vertex_bundle_type<Graph>::type VertexProperties; // aka Router in common.h
14
    typedef boost::edge_bundle_type<Graph>::type EdgeProperties; // aka Link in common.h
15
    typedef std::map<std::string, Vertex> NameVertexMap;
16

  
17
    GraphManager(); // constructor
18
    GraphManager(const GraphManager& other); // copy constructor
19
    GraphManager& operator=(GraphManager& rhs); // assignment operator
20
    // check out more here: http://www.cplusplus.com/articles/y8hv0pDG/
21

  
22
    void AddEdge(VertexProperties vp1, VertexProperties vp2, EdgeProperties ep);
23
    bool vertex_existed(string s);
24
    const Vertex& get_vertex_from_id(string s);
25

  
26
    StringSet vertices_id();
27

  
28
    void ResetVerticesAndEdgesIndexMap();
29

  
30
    // Function to print results
31
    // TODO: checkout utility.h, I can't overload << operator to output
32
    // the correct result. Therefore, I use print() ufnction as a replacement.
33
    void print_v_index_map();
34
    void print_e_index_map();
35

  
36
    // Getter
37
    const VertexIndexMap& v_index_map() const;
38
    const EdgeIndexMap& e_index_map() const;
39

  
40
    // Output Operators
41
    friend std::ostream& operator<<(std::ostream& os, const GraphManager& gm);
42

  
43
    Graph g_;
44
private:
45
    void reset_v_id_vertex_map();
46
    void reset_v_index_map();
47
    void reset_e_index_map();
48
    void update_v_index_map(Vertex new_vertex);
49
    void update_e_index_map(Edge new_edge);
50

  
51
    NameVertexMap v_id_vertex_map_;
52

  
53
    // VertexIndexMap - since we use listS instead of vecS, this one maps each vertex to an id
54
    VertexIndexStdMap v_index_std_map_;
55
    VertexIndexMap v_index_map_; //
56

  
57
    // EdgeIndexMap - boost will return the component id that each edge in the graph belongs to.
58
    EdgeIndexStdMap e_index_std_map_;
59
    EdgeIndexMap e_index_map_;
60
};
61

  
62
#endif //GRAPH_PARSER_GRAPH_MANAGER_H
63

  
custompackages/graph-parser/src/main.cpp
3 3
#include "utility.h"
4 4
#include "centrality.h"
5 5
#include "bi_connected_components.h"
6
#include "graph_manager.h"
6 7

  
7 8

  
8 9
void handleSimpleGraph() {
......
68 69
}
69 70

  
70 71
void testHeuristic(string filePath) {
71
    Graph g;
72
    readEdgeFile(filePath, g);
73
    outops::operator<<(cout, g);
74
    BiConnectedComponents bcc(g);
75
    // bcc.compute_weight();
76
    // bcc.findBetweennessCentrality();
77
    // bcc.printBetweennessCentrality();
78
    // bcc.print_weight();
79
    // bcc.print();
72
    GraphManager gm;
73
    readEdgeFileGraphManager(filePath, gm);
74
    BiConnectedComponents bcc(gm);
80 75
    cout << "DONE" << endl;
76
}
81 77

  
78
void testGraphManager(string filePath) {
79
    GraphManager gm;
80
    readEdgeFileGraphManager(filePath, gm);
81
    cout << gm;
82

  
83
    gm.ResetVerticesAndEdgesIndexMap();
84
    gm.print_v_index_map();
82 85

  
83 86
}
84 87

  
......
93 96
//    string complexJsonFilePath = "../input/jsoninfo_topo.json";
94 97
//    handleComplexJsonInput(complexJsonFilePath);
95 98

  
99
    // string simpleGraphFilePath = "../input/simple.edges";
100
    // testGraphManager(simpleGraphFilePath);
96 101

  
97 102
    string simpleGraphFilePath = "../input/simple.edges";
98 103
    testHeuristic(simpleGraphFilePath);
104

  
99 105
    return 0;
100 106
}
custompackages/graph-parser/src/parser.cpp
108 108

  
109 109
        addLinkToGraph(source, target, cost, g, routers);
110 110
    }
111
}
112

  
113
void readEdgeFileGraphManager(string filePath, GraphManager &gm) {
114
    // NameVertexMap is to keep track of which router has already been added
115
    ifstream inFile(filePath.c_str());
116

  
117
    vector<string> strs;
118
    for (string line; getline(inFile, line); /**/) {
119
        boost::split(strs, line, boost::is_any_of(" "));
120

  
121
        // Cast vector<string> to array<string, 3>
122
        // TODO: this is really crude way to do it.
123
        // TODO: how to copy some element of vector to array
124
        if (strs.size() == 3) {
125
            string source = strs[0];
126
            string target = strs[1];
127

  
128
            GraphManager::VertexProperties vp1 = GraphManager::VertexProperties(source, source);
129
            GraphManager::VertexProperties vp2 = GraphManager::VertexProperties(target, target);
130

  
131
            // TODO: use atof as a way around the error: ‘stof’ was not declared in this scope
132
            // double cost = stof(strs[2]);
133
            double cost = atof(strs[2].c_str());
134

  
135
            GraphManager::EdgeProperties ep = GraphManager::EdgeProperties(cost);
136

  
137
            gm.AddEdge(vp1, vp2, ep);
138

  
139
        }
140
    }
141
    inFile.close();
111 142
}
custompackages/graph-parser/src/parser.h
9 9
#include <boost/property_tree/json_parser.hpp>
10 10
#include <boost/foreach.hpp>
11 11
#include "common.h"
12
#include "graph_manager.h"
12 13

  
13 14
template<typename NameVertexMap>
14 15
void addLinkToGraph(string s1, string s2, double cost, Graph &g, NameVertexMap &routers);
......
17 18
void readJson(string filePath, Graph &g);
18 19
void readComplexJson(string filePath, Graph &g);
19 20

  
21
void readEdgeFileGraphManager(string filePath, GraphManager& gm);
20 22

  
21 23
#endif //GRAPH_PARSER_PARSER_H
22 24

  
custompackages/graph-parser/src/sub_component.cpp
9 9
    // do nothing
10 10
}
11 11

  
12
SubComponent::SubComponent(StringSet art_points, Graph sub_graph) : art_points_(art_points), sub_graph_(sub_graph) {
13
// SubComponent::SubComponent(VertexVec aart_points, Graph asubGraph) {
14
    // art_points = aart_points;
15
    // subGraph = asubGraph;
16
    // Deep copy for art_points
17
    // cout << "ABC " << endl;
18
    // for (VertexVecIter vi = aart_points.begin(); vi != aart_points.end(); ++vi) {
19
    //     Vertex v = Vertex(*vi);
20
    //     this->art_points.insert(this->art_points.end(), v);
21
    //     cout << "   asubGraph " << asubGraph[*vi].name << endl;
22
    //     cout << "    subGraph " << subGraph[*vi].name << endl;
23
    // }
12
/* GETTERS & SETTERS & UPDATERS */
13
GraphManager const& SubComponent::gm() const {
14
    return gm_;
15
}
24 16

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

  
26
    // init();
21
StringSet const& SubComponent::art_points_id() const {
22
    return art_points_id_;
27 23
}
28 24

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

  
33
void SubComponent::set_art_points(StringSet& art_points) {
34
    art_points_ = art_points;
34
NameToIntMap const& SubComponent::weight_reversed_map() const {
35
    return weight_reversed_map_;
35 36
}
36 37

  
37
int SubComponent::num_vertices() {
38
    return boost::num_vertices(sub_graph_);
38
vector< vector< int > > const& SubComponent::traffic_matrix() const {
39
    return traffic_matrix_;
39 40
}
40 41

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

  
44
    string s1 = r1.id;
45
    string s2 = r2.id;
46
    Vertex v1;
47
    Vertex v2;
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_;
48 57

  
49
    try {
50
        v1 = get_vertex_from_id(s1);
58
    // Create name -> index map
59
    int index = 0;
60
    for (string s : all_vertices_id_) {
61
        name_index_map_[s] = index;
62
        ++index;
51 63
    }
52
    catch (exception& e) {
53
        v1 = boost::add_vertex(r1, sub_graph_);
54
        name_vertex_map_[s1] = v1;
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);
55 71
    }
56
    try {
57
        v2 = get_vertex_from_id(s2);
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];
58 79
    }
59
    catch (exception& e) {
60
        v2 = boost::add_vertex(r2, sub_graph_);
61
        name_vertex_map_[s2] = v2;
80
    else {
81
        return 0;
62 82
    }
63
    boost::add_edge(v1, v2, l, sub_graph_);
64 83
}
65 84

  
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());
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
    }
70 94
}
71 95

  
72
const Vertex& SubComponent::get_vertex_from_id(string s) {
73
    if (vertex_existed(s)) {
74
        return name_vertex_map_[s];
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;
75 114
    }
76
    else {
77
        throw std::runtime_error("Vertex not found\n");
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
        }
78 129
    }
130
    // cout << "Mark 3\n";
79 131
}
80 132

  
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;
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
/* HELPERS */
163
int SubComponent::num_of_vertices() {
164
    return boost::num_vertices(gm_.g_);
165
}
166

  
167
int SubComponent::index_of_vertex_id(string vertex_id) {
168
    // TODO: might throw exception here
169
    return name_index_map_[vertex_id];
86 170
}
87 171

  
88
Graph const& SubComponent::sub_graph() const {
89
    return sub_graph_;
172
bool SubComponent::vertex_exists(string name) {
173
    stdhelper::exists(art_points_id_, name);
174
}
175

  
176
string SubComponent::first_vertex_id_with_unknown_weight() {
177
    string vertex_id = "";
178
    for (auto &i : weight_map_) {
179
        if (i.second == -1) {
180
            vertex_id = i.first;
181
            break;
182
        }
183
    }
184
    return vertex_id;
90 185
}
91 186

  
187
/* HELPERS FOR OUTPUTTING RESULT */
188
void SubComponent::print_traffic_matrix() {
189

  
190
}
191

  
192
std::ostream& operator<<(std::ostream& os, const SubComponent& sc) {
193
    cout << "Sub-component:" << endl;
194
    cout << sc.gm_;
195

  
196
    cout << "\nArticulation points ID:\n";
197
    outops::operator<<(cout, sc.art_points_id());
198

  
199
    cout << "\nNormal Vertices ID:\n";
200
    outops::operator<<(cout, sc.all_vertices_id());
201

  
202
    cout << "\nLink Weight:\n";
203
    outops::operator<<(cout, sc.weight_map());
204
    // printhelper::for_map<string, int>(sc.weight_map());
205

  
206
    cout << "\nTraffic Matrix:\n";
207
    outops::operator<<(cout, sc.traffic_matrix());
208

  
209
    return os;
210
}
custompackages/graph-parser/src/sub_component.h
12 12
#include <boost/graph/copy.hpp>
13 13
#include "common.h"
14 14
#include "utility.h"
15
#include "graph_manager.h"
15 16

  
16 17
class SubComponent {
17 18
public:
18 19
    SubComponent();
19
    SubComponent(const StringSet art_points, const Graph sub_graph);
20 20

  
21 21
    // Getter & Setter
22
    StringSet art_points() const;
23
    void set_art_points(StringSet& art_points);
22
    GraphManager const& gm() const;
23
    StringSet const& all_vertices_id() const;
24
    StringSet const& art_points_id() const;
25
    StringSet const& non_art_points_id() const;
24 26

  
25
    // Manipulating subGraph
26
    int num_vertices();
27
    void AddEdge(Router r1, Router r2, Link l);
28
    bool vertex_existed(string s);
29
    const Vertex& get_vertex_from_id(string s);
30
    Graph const& sub_graph() const;
27
    NameToIntMap const& weight_map() const;
28
    NameToIntMap const& weight_reversed_map() const;
31 29

  
32
    // Output to console
33
    friend std::ostream& operator<<(std::ostream& os, const SubComponent& sc);
30
    vector< vector< int > > const& traffic_matrix() const;
34 31

  
35
    void init();
... This diff was truncated because it exceeds the maximum size that can be displayed.

Also available in: Unified diff