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

View differences:

custompackages/graph-parser/src/bi_connected_components.cpp
10 10
    findBiConnectedComponents();
11 11
}
12 12

  
13

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

  
......
49 50
    outops::operator<<(cout, art_point_ids);
50 51

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

  
61 62
void BiConnectedComponents::createSubComponents() {
62
    vector<Graph> subGraphVec(num_bcc());
63
    vector< map<string, Vertex> > nameVertexMapVec(num_bcc());
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);
64 69

  
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]);
70
        outops::operator<<(cout, art_point_ids);
71
        BCCs[i].set_art_points(art_point_ids);
73 72
    }
74 73

  
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);
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);
80 81
    }
81 82

  
82
    //
83 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;
84
        cout << BCCs[i] << endl;
89 85
    }
90

  
91

  
92 86
}
93 87

  
94 88
void BiConnectedComponents::print() {
......
216 210

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

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

  
221 215
        for (ii = components.begin(); ii < components.end(); ++ii) {
222 216
            cout << *ii << endl;
......
260 254
    return normal_points;
261 255
}
262 256

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

Also available in: Unified diff