Statistics
| Branch: | Revision:

root / custompackages / graph-parser / src / bi_connected_components.cpp @ efed924d

History | View | Annotate | Download (15.2 KB)

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

    
5
#include "bi_connected_components.h"
6
using namespace std;
7

    
8
BiConnectedComponents::BiConnectedComponents(const Graph &g) : g(g) {
9
    init();
10
    findBiConnectedComponents();
11
}
12

    
13

    
14
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
    }
24

    
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
    }
36
}
37

    
38
void BiConnectedComponents::findBiConnectedComponents() {
39
    cout << "Running findBiConnectedComponents" << endl;
40
    size_t i;
41

    
42

    
43
    boost::biconnected_components(g, component_map,
44
                                  back_inserter(art_points),
45
                                  boost::vertex_index_map(this->v_index_map));
46

    
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);
51

    
52
    // 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
}
61

    
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);
69

    
70
        outops::operator<<(cout, art_point_ids);
71
        BCCs[i].set_art_points(art_point_ids);
72
    }
73

    
74
    // 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];
80
        BCCs[comp_index].AddEdge(r1, r2, l);
81
    }
82

    
83
    for (int i = 0; i < num_bcc(); ++i) {
84
        cout << BCCs[i] << endl;
85
    }
86
}
87

    
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;
98
    }
99
}
100

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

    
107
    return num_of_bcc;
108
}
109

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

    
113
    vector<set<Vertex> > set_vertices(size);
114

    
115
    Edge edge;
116
    Vertex source;
117
    Vertex target;
118

    
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
    }
127

    
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
    }
133
}
134

    
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) {
141

    
142
            cout << g[bcc_vertices[i][j]].id << endl;
143
        }
144
    }
145
}
146

    
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;
157
    }
158
}
159

    
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);
176
            }
177
        }
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
    }
201
}
202

    
203

    
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;
217
        }
218
    }
219

    
220
    VertexVecIter vvi;
221
    int i = 0;
222
    for (i; i < num_bcc(); ++i) {
223
        VertexVec vv = boost::get(component_art_point_map, i);
224

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

    
227
        for (vvi = vv.begin(); vvi != vv.end(); ++vvi) {
228
            cout << *vvi << endl;
229
        }
230
    }
231
}
232

    
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
}
244

    
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)
252

    
253
    );
254
    return normal_points;
255
}
256

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