Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (14.9 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
void BiConnectedComponents::init() {
14
    size_t i = 0; // for indexing in the loop
15

    
16
    // Populate the e_index_map, by changing the value of the original e_index_std_map
17
    e_index_map = EdgeIndexMap(e_index_std_map);
18
    i = 0;
19
    BGL_FORALL_EDGES(edge, g, Graph) {
20
        e_index_std_map.insert(pair<Edge, size_t>(edge, i));
21
        ++i;
22
    }
23

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

    
27
    // Populate the VertexIndexMap - by using the put() from Property Map
28
    v_index_map = VertexIndexMap(v_index_std_map);
29
    Viter vi, ve; // vertex_iterator, vertex_iterator_end
30
    i = 0;
31
    for (boost::tie(vi, ve) = boost::vertices(g); vi != ve; ++vi) {
32
        boost::put(this->v_index_map, *vi, i);
33
        ++i;
34
    }
35
}
36

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

    
41

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

    
46
    cout << "Articulation points: \n";
47
    set<string> art_point_ids;
48
    graphext::id_of_vertices(g, art_points, art_point_ids);
49
    outops::operator<<(cout, art_point_ids);
50

    
51
    // Process the result from boost::biconnected_components
52
    // BCCs = Component_t(num_bcc());
53
    // verticesInBCC();
54
    // testVerticesInBCC();
55
    // processArtPoints();
56
    // testProcessArtPoints();
57
    // _test_set_difference();
58
    // createSubComponents();
59
}
60

    
61
void BiConnectedComponents::createSubComponents() {
62
    vector<Graph> subGraphVec(num_bcc());
63
    vector< map<string, Vertex> > nameVertexMapVec(num_bcc());
64

    
65
    // Build subgraphs
66
    int comp_index;
67
    BGL_FORALL_EDGES(edge, g, Graph) {
68
        comp_index = boost::get(component_map, edge);
69
        string source = g[edge.m_source].name;
70
        string target = g[edge.m_target].name;
71
        double cost = g[edge].cost;
72
        addLinkToGraph(source, target, cost, subGraphVec[comp_index], nameVertexMapVec[comp_index]);
73
    }
74

    
75
    // Build articulation points for this each subGraph
76
    vector<VertexVec> art_points_vec(num_bcc());
77
    for (int i = 0; i < num_bcc(); ++i) {
78
        // TODO optimize here - remove the function
79
        art_points_vec[i] = get_art_points_for_component(i);
80
    }
81

    
82
    //
83
    for (int i = 0; i < num_bcc(); ++i) {
84
        SubComponent subComp = SubComponent(
85
                art_points_vec[i],
86
                subGraphVec[i]
87
        );
88
        BCCs[i] = subComp;
89
    }
90

    
91

    
92
}
93

    
94
void BiConnectedComponents::print() {
95
    // Test the biconnected components
96
    Eiter ei, ei_end;
97
    size_t i = 0;
98
    for (boost::tie(ei, ei_end) = boost::edges(g); ei != ei_end; ++ei) {
99
        string source = g[(*ei).m_source].id;
100
        string target = g[(*ei).m_target].id;
101
        edges_size_type comp = this->component_vec.at(i);
102
        cout << source << " " << target << " " << comp << endl;
103
        ++i;
104
    }
105
}
106

    
107
int BiConnectedComponents::num_bcc() {
108
    if (num_of_bcc == -1) { // calculate it
109
        // +1 to counteract for the zero-indexing
110
        num_of_bcc = *std::max_element(component_vec.begin(), component_vec.end()) + 1;
111
    }
112

    
113
    return num_of_bcc;
114
}
115

    
116
void BiConnectedComponents::verticesInBCC() {
117
    size_t size = num_bcc();
118

    
119
    vector<set<Vertex> > set_vertices(size);
120

    
121
    Edge edge;
122
    Vertex source;
123
    Vertex target;
124

    
125
    int comp_id;
126
    BGL_FORALL_EDGES(edge, g, Graph) {
127
        comp_id = boost::get(component_map, edge);
128
        source = edge.m_source;
129
        target = edge.m_target;
130
        set_vertices[comp_id].insert(source);
131
        set_vertices[comp_id].insert(target);
132
    }
133

    
134
    bcc_vertices = vector<VertexVec>(size);
135
    size_t i = 0;
136
    for (i = 0; i < size; ++i) {
137
        bcc_vertices[i] = vector<Vertex>(set_vertices[i].begin(), set_vertices[i].end());
138
    }
139
}
140

    
141
void BiConnectedComponents::testVerticesInBCC() {
142
    size_t i = 0;
143
    for (i; i < num_of_bcc; ++i) {
144
        vector<Vertex> abc = bcc_vertices[i];
145
        cout << "vertices in BCC " << i << endl;
146
        for (int j = 0; j < abc.size(); ++j) {
147

    
148
            cout << g[bcc_vertices[i][j]].id << endl;
149
        }
150
    }
151
}
152

    
153
bool BiConnectedComponents::hasVertex(Vertex v, int comp_index) {
154
    vector<Vertex> vv = bcc_vertices[comp_index];
155
    vector<Vertex>::iterator it;
156

    
157
    it = std::find(vv.begin(), vv.end(), v);
158
    if (it == vv.end()) {
159
        return false;
160
    }
161
    else {
162
        return true;
163
    }
164
}
165

    
166
void BiConnectedComponents::processArtPoints() {
167
    // For each articulation points, quickly identify (through the std::map) all the component containing those points.
168
    art_point_component_map = ArtPointComponentMap(art_point_component_std_map);
169

    
170
    std::vector<Vertex>::iterator vi = art_points.begin();
171
    std::vector<int>::iterator ii;
172

    
173
    for (vi; vi < art_points.end(); ++vi) {
174
        Vertex articulation_point = *vi;
175

    
176
        size_t i = 0;
177
        std::vector<int> components;
178
        for (i = 0; i < num_of_bcc; ++i) {
179
            ii = components.end();
180
            if (hasVertex(articulation_point, i)) {
181
                components.insert(ii, i);
182
            }
183
        }
184
        boost::put(art_point_component_map, articulation_point, components);
185
    }
186

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

    
190
    BccIter_t bi = bcc_vertices.begin();
191
    BccIter_t bi_end = bcc_vertices.end();
192

    
193
    VertexVecIter vvi = art_points.begin();
194
    VertexVecIter vvi_end = art_points.end();
195

    
196
    int i = 0;
197
    for (bi; bi != bi_end; ++bi) {
198
        // intersection
199
        VertexVec component = *bi;
200
        VertexVec intersection_result;
201
        std::set_intersection(component.begin(), component.end(), vvi, vvi_end, back_inserter(intersection_result));
202

    
203
        boost::put(component_art_point_map, i, intersection_result);
204
        ++i;
205

    
206
    }
207
}
208

    
209

    
210
void BiConnectedComponents::testProcessArtPoints() {
211
    std::vector<Vertex>::iterator vi = art_points.begin();
212
    std::vector<int>::iterator ii;
213

    
214
    for (vi; vi < art_points.end(); ++vi) {
215
        Vertex articulation_point = *vi;
216

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

    
219
        cout << "Components belonging to articulation point " << g[articulation_point].name << endl;
220

    
221
        for (ii = components.begin(); ii < components.end(); ++ii) {
222
            cout << *ii << endl;
223
        }
224
    }
225

    
226
    VertexVecIter vvi;
227
    int i = 0;
228
    for (i; i < num_bcc(); ++i) {
229
        VertexVec vv = boost::get(component_art_point_map, i);
230

    
231
        cout << "Articulation points from the component " << i << endl;
232

    
233
        for (vvi = vv.begin(); vvi != vv.end(); ++vvi) {
234
            cout << *vvi << endl;
235
        }
236
    }
237
}
238

    
239
VertexVec BiConnectedComponents::get_art_points_for_component(int comp_index) {
240
    return boost::get(component_art_point_map, comp_index);
241
}
242

    
243
vector<int> BiConnectedComponents::get_components_for_art_point(Vertex vertex) {
244
    return boost::get(art_point_component_map, vertex);
245
}
246

    
247
int BiConnectedComponents::num_of_vertices_in_component(int comp_index) {
248
    return bcc_vertices[comp_index].size();
249
}
250

    
251
VertexVec BiConnectedComponents::get_normal_vertices_for_component(int comp_index) {
252
    VertexVec normal_points;
253
    std::set_difference(bcc_vertices[comp_index].begin(),
254
                        bcc_vertices[comp_index].end(),
255
                        art_points.begin(),
256
                        art_points.end(),
257
                        back_inserter(normal_points)
258

    
259
    );
260
    return normal_points;
261
}
262

    
263
void BiConnectedComponents::compute_weight() {
264
    _initialize_weight();
265
    _initialize_queue();
266

    
267
    while (!Q.empty()) {
268
        QueueElem elem = Q.front();
269
        Q.pop();
270
        int comp_index = elem.component_index;
271
        Vertex current_art_point = elem.art_point;
272

    
273
        if (elem.type == "component_vertex_pair") {
274
            int size = BCCs[comp_index].num_vertices() - 1;
275
            VertexVec art_points = BCCs[comp_index].get_art_points();
276

    
277
            // TODO: I assume here that vvi != art_points.end(), aka. the element is always found.
278
            VertexVecIter vvi;
279
            vvi = std::find(art_points.begin(), art_points.end(), current_art_point);
280
            try {
281
                art_points.erase(vvi);
282
            }
283
            catch (exception& e) {
284
                cout << "Standard exception: " << e.what() << endl;
285
            }
286

    
287
            for (vvi = art_points.begin(); vvi != art_points.end(); ++vvi) {
288
                cout << "    " << g[*vvi].name << endl;
289
                int weight = BCCs[comp_index].getWeight(*vvi);
290
                if (weight != -1) {
291
                    size += boost::num_vertices(g) - weight - 1;
292
                }
293
            }
294

    
295
            int link_weight = size;
296
//            _verify_weight(comp_index, current_art_point, link_weight);
297
            BCCs[comp_index].setWeight(current_art_point, link_weight);
298

    
299
            _find_unknown_weight_wrt_art_point(current_art_point);
300
        }
301

    
302
        if (elem.type == "vertex_component_pair") {
303
            vector<int> comp_indices = get_components_for_art_point(current_art_point);;
304

    
305
            vector<int>::iterator vi;
306
            vi = std::find(comp_indices.begin(), comp_indices.end(), comp_index);
307
            try {
308
                comp_indices.erase(vi);
309
            }
310
            catch (exception& e) {
311
                cout << "Standard exception: " << e.what() << endl;
312
            }
313

    
314
            int size = 0;
315
            for (vi = comp_indices.begin(); vi != comp_indices.end(); ++vi) {
316
                int weight = BCCs[*vi].getWeight(current_art_point);
317
                if (weight != -1) {
318
                    size += weight;
319
                }
320
            }
321

    
322
            int link_weight = boost::num_vertices(g) - 1 - size;
323
//            _verify_weight(comp_index, current_art_point, link_weight);
324
            BCCs[comp_index].setWeight(current_art_point, link_weight);
325
            _find_unknown_weight_wrt_component(comp_index);
326

    
327
        }
328
    }
329
}
330

    
331
void BiConnectedComponents::_initialize_weight() {
332
    ComponentIter_t ci;
333
    for (ComponentIter_t ci = BCCs.begin(); ci != BCCs.end(); ++ci) {
334
        (*ci)._initialize_weight();
335
    }
336
}
337

    
338
void BiConnectedComponents::_initialize_queue() {
339
    VertexVecIter vvi;
340

    
341
    int i = 0;
342
    VertexVec current_art_points;
343
    for (i; i < num_bcc(); ++i) {
344
        current_art_points = BCCs[i].get_art_points();
345
        if (current_art_points.size() == 1) {
346
            // creating element for queue Q
347
            Vertex art_point = current_art_points[0];
348
            string type = "component_vertex_pair";
349
            QueueElem qe = {
350
                    .component_index = i,
351
                    .art_point = art_point,
352
                    .type = type,
353
            };
354

    
355
            Q.push(qe);
356
        }
357
    }
358
}
359

    
360
void BiConnectedComponents::_find_unknown_weight_wrt_art_point(Vertex art_point) {
361
    int num_of_uncomputed_weight = 0;
362
    vector<int> uncomputed_weight_component_indices;
363

    
364
    size_t i;
365
    for (i = 0; i < num_bcc(); ++i) {
366
        if (hasVertex(art_point, i)) {
367
            // Check if value -1 appear exactly 1 time
368
            if (BCCs[i].getWeight(art_point) == -1) {
369
                num_of_uncomputed_weight += 1;
370
                uncomputed_weight_component_indices.insert(uncomputed_weight_component_indices.end(), i);
371
            }
372
        }
373

    
374
        if (num_of_uncomputed_weight > 1) {
375
            break;
376
        }
377
    }
378

    
379
    if (num_of_uncomputed_weight == 1) {
380
        QueueElem elem = {
381
                component_index: uncomputed_weight_component_indices[0],
382
                art_point: art_point,
383
                type: "vertex_component_pair",
384
        };
385
        Q.push(elem);
386
    }
387
}
388

    
389
void BiConnectedComponents::_find_unknown_weight_wrt_component(int comp_index) {
390
    VertexVec unknown_weight_vertices;
391
    BCCs[comp_index]._find_vertices_with_unknown_weight(unknown_weight_vertices);
392

    
393
    if (unknown_weight_vertices.size() == 1) {
394
        QueueElem elem = {
395
                .component_index = comp_index,
396
                .art_point = unknown_weight_vertices[0],
397
                .type = "component_vertex_pair",
398
        };
399

    
400
        Q.push(elem);
401
    }
402
}
403

    
404
void BiConnectedComponents::print_weight() {
405
    for (int i = 0; i < num_bcc(); ++i) {
406
        BCCs[i].printWeight();
407
    }
408
}
409

    
410
void BiConnectedComponents::findBetweennessCentrality() {
411
    for (int i = 0; i < num_bcc(); ++i) {
412
        // BCCs[i]._computeTrafficMatrix();
413
        cout << "###########" << endl;
414
        _print_art_points();
415
        cout << "###########" << endl;
416
        BCCs[i].findBetweennessCentrality();
417
    }
418
}
419

    
420
void BiConnectedComponents::printBetweennessCentrality() {
421
    for (int i = 0; i < num_bcc(); ++i) {
422
        BCCs[i].printBetweennessCentrality();
423
    }
424
}
425

    
426
void BiConnectedComponents::_print_art_points() {
427
    for (int i = 0; i < art_points.size(); ++i) {
428
        cout << &art_points[i] << endl;
429
    }
430
}
431

    
432
void BiConnectedComponents::_test_set_difference() {
433
    VertexVec component = bcc_vertices[0];
434
    VertexVec intersection_result;
435

    
436
    cout << "******** Test set_difference ********" << endl;
437
    cout << "  Component" << endl;
438
    for (VertexVecIter vvi = component.begin(); vvi != component.end(); ++vvi) {
439
        cout << "\t" << *vvi << endl;
440
    }
441
    cout << "  Articulation points" << endl;
442
    cout << "  " << &art_points[0] << endl;
443
    cout << "  " << &art_points[1] << endl;
444

    
445
    for (VertexVecIter vvi = art_points.begin(); vvi != art_points.end(); ++vvi) {
446
        cout << "\t" << *vvi << endl;
447
    }
448

    
449
    VertexVec copy_art_points = VertexVec(art_points);
450
    cout << "  Copy Articulation points" << endl;
451
    cout << "  " << &copy_art_points << endl;
452
    // cout << "  " << &(*copy_art_points) << endl;
453
    cout << "  " << &(copy_art_points[0]) << " " << copy_art_points[0] << endl;
454
    cout << "    " << &(*(&copy_art_points[0])) << " " << *(&copy_art_points[0]) << endl;
455
    cout << "  " << &copy_art_points[1] << " " << copy_art_points[1] << endl;
456
    for (VertexVecIter vvi = copy_art_points.begin(); vvi != copy_art_points.end(); ++vvi) {
457
        cout << "\t" << *vvi << endl;
458
    }
459

    
460
    std::set_intersection(component.begin(), component.end(), art_points.begin(), art_points.end(), back_inserter(intersection_result));
461

    
462
    cout << "  Intersection result" << endl;
463
    for (VertexVecIter vvi = intersection_result.begin(); vvi != intersection_result.end(); ++vvi) {
464
        cout << "\t" << *vvi << endl;
465
    }
466

    
467
    VertexVec difference_result;
468
    std::set_intersection(component.begin(), component.end(), art_points.begin(), art_points.end(), back_inserter(difference_result));
469

    
470
    cout << "  Difference result" << endl;
471
    for (VertexVecIter vvi = difference_result.begin(); vvi != difference_result.end(); ++vvi) {
472
        cout << "\t" << *vvi << endl;
473
    }
474
}