Revision cb770240 custompackages/graph-parser/src/bi_connected_components.cpp

View differences:

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
}

Also available in: Unified diff