Revision efed924d

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
// }
custompackages/graph-parser/src/common.h
18 18

  
19 19
using namespace std;
20 20

  
21
class Router { // aka Vertex
21
class Router { // aka VertexProperties
22 22
public:
23 23
    string id;
24
    string name;
24
    string label;
25 25

  
26 26
    Router() { };
27
    Router(string id, string name) : id(id), name(name) { };
27
    Router(string i, string l) : id(i), label(l) { };
28 28

  
29 29
    bool operator<(const Router& rhs)
30 30
    {
......
36 36
   }
37 37
};
38 38

  
39
struct Link { // aka Edge
39
struct Link { // aka EdgeProperties
40 40
    double cost;
41 41

  
42 42
    Link() { };
43
    Link(double cost) : cost(cost) { };
43
    Link(double c) : cost(c) { };
44 44
};
45 45

  
46 46
// List typedefs
......
62 62
typedef map<Edge, size_t> StdEdgeIndexMap;
63 63
typedef boost::associative_property_map<StdEdgeIndexMap> EdgeIndexMap;
64 64

  
65

  
66 65
typedef std::vector<Vertex> VertexVec;
67 66
typedef std::vector<Vertex>::iterator VertexVecIter;
68 67

  
69 68
typedef std::map<Vertex, int> VertexMap;
70 69
typedef std::map<Vertex, int>::iterator VertexMapIter;
71 70

  
71
// TODO: this StringVec is currently un-used
72
typedef std::vector<std::string> StringVec;
73
typedef std::vector<std::string>::iterator StringVecIter;
74

  
75
typedef std::set<std::string> StringSet;
76
typedef std::set<std::string>::iterator StringSetIter;
72 77

  
73 78
typedef std::vector<double> CentralityVec;
74 79
typedef boost::iterator_property_map<CentralityVec::iterator, VertexIndexMap> CentralityMap;
custompackages/graph-parser/src/parser.cpp
20 20
        routers[s1] = v1;
21 21
        pos->second = v1;
22 22
        g[v1].id = s1;
23
        g[v1].name = s1;
23
        g[v1].label = s1;
24 24
    } else {
25 25
        v1 = pos->second;
26 26
    }
......
31 31
        routers[s2] = v2;
32 32
        pos->second = v2;
33 33
        g[v2].id = s2;
34
        g[v2].name = s2;
34
        g[v2].label = s2;
35 35
    } else {
36 36
        v2 = pos->second;
37 37
    }
custompackages/graph-parser/src/sub_component.cpp
6 6

  
7 7

  
8 8
SubComponent::SubComponent() {
9
    // do nothing
9 10
}
10 11

  
11
SubComponent::SubComponent(VertexVec aart_points, Graph asubGraph) : art_points(aart_points), subGraph(asubGraph) {
12
SubComponent::SubComponent(StringSet art_points, Graph sub_graph) : art_points_(art_points), sub_graph_(sub_graph) {
12 13
// SubComponent::SubComponent(VertexVec aart_points, Graph asubGraph) {
13 14
    // art_points = aart_points;
14 15
    // subGraph = asubGraph;
......
21 22
    //     cout << "    subGraph " << subGraph[*vi].name << endl;
22 23
    // }
23 24

  
24
    // Test if deep copy is performed for aart_points
25
    cout << "Test if deep copy is performed for art_points" << endl;
26
    cout << "&art_points " <<  &aart_points << endl;
27
    cout << "&this->art_points " << &this->art_points << endl;
28
    cout << "art_points[0] " <<  aart_points[0] << endl;
29
    cout << "this->art_points[0] " << this->art_points[0] << endl;
30 25

  
31
     // create Vertex -> Index Mapping
32
    v_index_map = VertexIndexMap(v_index_std_map);
33
    int i = 0;
34
    BGL_FORALL_VERTICES(vertex, this->subGraph, Graph) {
35
            boost::put(v_index_map, vertex, i);
36
            ++i;
37
    }
38

  
39
    // Deep copy for subGraph
40
    // TODO: optimize - is there anyway that we can avoid using deep copy
41

  
42
    // This is not working
43
    // copy_graph(asubGraph, this->subGraph, vertex_index_map(v_index_map));
44

  
45
    // this->subGraph = Graph(asubGraph);
46

  
47
    // Vertices in this->subGraph
48
    cout << "Vertices in this->subGraph | constructor" << endl;
49
    BGL_FORALL_VERTICES(vertex, this->subGraph, Graph) {
50
        cout << vertex << " " << this->subGraph[vertex].name << endl;
51
    }
52

  
53
    cout << "Vertices in asubGraph | constructor" << endl;
54
    BGL_FORALL_VERTICES(vertex, asubGraph, Graph) {
55
        cout << vertex << " " << asubGraph[vertex].name << endl;
56
    }
57
    init();
26
    // init();
58 27
}
59 28

  
60
void SubComponent::init() {
61
    // create list of normal vertices
62
    Viter vi, vi_end;
63
    boost::tie(vi, vi_end) = boost::vertices(subGraph);
64
    std::set_difference(vi, vi_end,
65
                        art_points.begin(), art_points.end(),
66
                        back_inserter(normal_vertices)
67
    );
68

  
69

  
70
    cout << "Vertices in this->subGraph | init()" << endl;
71
    BGL_FORALL_VERTICES(vertex, this->subGraph, Graph) {
72
        cout << vertex << " " << this->subGraph[vertex].name << endl;
73
    }
74

  
75
    cout << "Test normal_vertices | init()" << endl;
76
    for (vector<Vertex>::iterator vi = normal_vertices.begin(); vi != normal_vertices.end(); ++vi) {
77
        cout << *vi << " ";
78
        cout << subGraph[*vi].name << endl;
79
    }
80

  
81
    /* STEP 1
82
    ** Compute Link Weight
83
    ** ==> Link Weight is computed by the main Bi Connected Components.
84
    ** That main BCC will set the Link Weight value for each sub-component.
85
    */
86

  
87
    /* STEP 2
88
    ** Compute Traffic Matrix
89
    */
90
//    _initializeTrafficMatrix();
91
//    _computeTrafficMatrix();
92

  
93
    /* STEP 3
94
    ** Compute the Betweenness Centrality
95
    ** The calculation is executed by the main BCCs calling each sub-component
96
    */
97
    // Initialize variables for calculating BC
98
    _initializeBetweennessCentrality();
99
    findBetweennessCentrality();
29
StringSet SubComponent::art_points() const {
30
    return art_points_;
100 31
}
101 32

  
102
VertexVec SubComponent::get_art_points() {
103
    return art_points;
33
void SubComponent::set_art_points(StringSet& art_points) {
34
    art_points_ = art_points;
104 35
}
105 36

  
106 37
int SubComponent::num_vertices() {
107
    return boost::num_vertices(subGraph);
108
}
109

  
110
void SubComponent::_initialize_weight() {
111
    for (VertexVecIter vvi = art_points.begin(); vvi != art_points.end(); ++vvi) {
112
        setWeight(*vvi, -1);
113
    }
114
}
115

  
116
void SubComponent::setWeight(Vertex art_point, int value) {
117
    weightMap[art_point] = value;
118
}
119

  
120
int SubComponent::getWeight(Vertex art_point) {
121
    VertexMapIter vmi;
122

  
123
    vmi = weightMap.find(art_point);
124

  
125
    if (vmi != weightMap.end()) {
126
        return weightMap.at(art_point);
127
    }
128
    else {
129
        return 0;
130
    }
131
}
132

  
133
int SubComponent::getReversedWeight(Vertex art_point) {
134
    VertexMapIter vmi;
135

  
136
    vmi = weightMap.find(art_point);
137

  
138
    if (vmi != weightMap.end()) {
139
        return (boost::num_vertices(subGraph) - weightMap.at(art_point) - 1);
140
    }
141
    else {
142
        return 0;
143
    }
144
}
145

  
146
void SubComponent::printWeight() {
147
    for (VertexMapIter vmi = weightMap.begin(); vmi != weightMap.end(); ++vmi) {
148
        cout << subGraph[(*vmi).first].name << " = " << (*vmi).second << endl;
149
    }
150
}
151

  
152
void SubComponent::_find_vertices_with_unknown_weight(VertexVec& unknown_weight_vertices) {
153
    VertexMapIter wi;
154
    Vertex vertex;
155

  
156
    int current_weight;
157
    for (wi = weightMap.begin(); wi != weightMap.end(); ++wi) {
158
        vertex = (*wi).first;
159
        current_weight = (*wi).second;
160

  
161
        if (current_weight == -1) {
162
            unknown_weight_vertices.insert(unknown_weight_vertices.end(), vertex);
163
        }
164
    }
38
    return boost::num_vertices(sub_graph_);
165 39
}
166 40

  
167
void SubComponent::_initializeTrafficMatrix() {
168
    // generate_empty_traffic_matrix, with 1 every where, and 0 in the main diagonal
169
    int size = boost::num_vertices(subGraph);
170
    trafficMatrix = vector<vector<int> >(size);
171
    for (int j = 0; j < size; ++j) {
172
        trafficMatrix[j] = vector<int>(size, 1);
173
    }
41
void SubComponent::AddEdge(Router r1, Router r2, Link l) {
42
    cout << "add edge " << r1.label << " - " << r2.label << endl;
174 43

  
175
    // Reset the main diagonal to 0
176
    for (int j = 0; j < size; ++j) {
177
        trafficMatrix[j][j] = 0;
178
    }
179
}
44
    string s1 = r1.id;
45
    string s2 = r2.id;
46
    Vertex v1;
47
    Vertex v2;
180 48

  
181
void SubComponent::_setTrafficMatrix(Vertex v_1, Vertex v_2, int value) {
182
    int i_1 = _indexOfVertex(v_1);
183
    int i_2 = _indexOfVertex(v_2);
184
    trafficMatrix[i_1][i_2] = value;
185
    trafficMatrix[i_2][i_1] = value; // because Traffic Matrix is symmetric
186
}
187

  
188
int SubComponent::_indexOfVertex(Vertex v) {
189 49
    try {
190
        return boost::get(v_index_map, v);
50
        v1 = get_vertex_from_id(s1);
191 51
    }
192 52
    catch (exception& e) {
193
        // TODO handle exception here
194
        cout << "ERROR _indexOfVertex() " << e.what() << endl;
195
        return -1;
53
        v1 = boost::add_vertex(r1, sub_graph_);
54
        name_vertex_map_[s1] = v1;
196 55
    }
197
}
198

  
199
void SubComponent::_computeTrafficMatrix() {
200
    // Update the value when one vertex is a cut-point, another vertex is not a cut-point
201
    for (int j = 0; j < art_points.size(); ++j) {
202
        for (int k = 0; k < normal_vertices.size(); ++k) {
203
            int communication_intensity = getReversedWeight(art_points[j]) + 1;
204
            _setTrafficMatrix(art_points[j], normal_vertices[k], communication_intensity);
205
        }
206
    }
207

  
208
    // Update the value when both vertices are cut-points
209
    int size = art_points.size();
210
    if (size > 1) {
211
        for (int j = 0; j < size - 1; ++j) {
212
            for (int k = 1; k < size; ++k) {
213
                if (j == k) {
214
                    continue;
215
                }
216

  
217
                int communication_intensity = (
218
                        (getReversedWeight(art_points[j]) + 1) *
219
                        (getReversedWeight(art_points[k]) + 1)
220
                );
221

  
222
                _setTrafficMatrix(art_points[j], art_points[k], communication_intensity);
223
            }
224
        }
225
    }
226
}
227

  
228
int SubComponent::getTrafficMatrix(Vertex v_1, Vertex v_2) {
229
    int i_1 = _indexOfVertex(v_1);
230
    int i_2 = _indexOfVertex(v_2);
231 56
    try {
232
        return trafficMatrix[i_1][i_2];
57
        v2 = get_vertex_from_id(s2);
233 58
    }
234 59
    catch (exception& e) {
235
        cout << "ERROR: getTrafficMatrix: " << e.what() << endl;
60
        v2 = boost::add_vertex(r2, sub_graph_);
61
        name_vertex_map_[s2] = v2;
236 62
    }
237

  
63
    boost::add_edge(v1, v2, l, sub_graph_);
238 64
}
239 65

  
240
void SubComponent::_initializeBetweennessCentrality() {
241
    v_centrality_vec = CentralityVec(boost::num_vertices(subGraph), 0);
242
    v_centrality_map = CentralityMap(v_centrality_vec.begin(), v_index_map);
243
    cout << "Test v_index_map" << endl;
244
    BGL_FORALL_VERTICES(vertex, subGraph, Graph) {
245
        cout << subGraph[vertex].name << " " << boost::get(v_index_map, vertex) << endl;
246
    }
247

  
248
    cout << "Vertices in this->subGraph | init BC()" << endl;
249
    BGL_FORALL_VERTICES(vertex, this->subGraph, Graph) {
250
        cout << vertex << " " << this->subGraph[vertex].id << endl;
251
    }
252

  
253

  
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());
254 70
}
255 71

  
256
void SubComponent::findBetweennessCentrality() {
257
    cout << "****** find BC() *******" << endl;
258
    cout << "Test art_points" << endl;
259
    for (VertexVecIter vi = art_points.begin(); vi != art_points.end(); ++vi) {
260
        cout << *vi << " ";
261
        cout << subGraph[*vi].name << endl;
262
    }
263

  
264
    cout << "Vertices in this->subGraph | find BC()" << endl;
265
    BGL_FORALL_VERTICES(vertex, this->subGraph, Graph) {
266
        cout << vertex << " " << this->subGraph[vertex].id << endl;
72
const Vertex& SubComponent::get_vertex_from_id(string s) {
73
    if (vertex_existed(s)) {
74
        return name_vertex_map_[s];
267 75
    }
268

  
269
    cout << "Test normal_vertices 2" << endl;
270
    for (vector<Vertex>::iterator vi = normal_vertices.begin(); vi != normal_vertices.end(); ++vi) {
271
        cout << *vi << " " << endl;
272
        cout << subGraph[*vi].name << endl;
76
    else {
77
        throw std::runtime_error("Vertex not found\n");
273 78
    }
274
    cout << "BC abc " << endl;
275
    /* Test v_index_map */
276
    // BGL_FORALL_VERTICES(vertex, subGraph, Graph) {
277
    //     cout << subGraph[vertex].name << " " << boost::get(v_index_map, vertex) << endl;
278
    // }
279

  
280
    // /* Test v_centrality_map
281
    // **
282
    // */
283
    // cout << "v_centrality_map" << endl;
284
    // BGL_FORALL_VERTICES(vertex, subGraph, Graph) {
285
    //     cout << subGraph[vertex].name << endl;
286
    //     // double score = boost::get(v_centrality_map, vertex);
287
    //     // cout << vertex << " " << score << endl;
288
    // }
289

  
290
    // brandes_betweenness_centrality(subGraph, boost::centrality_map(v_centrality_map).vertex_index_map(v_index_map));
291
    cout << "BC done" << endl;
292 79
}
293 80

  
294
void SubComponent::printBetweennessCentrality() {
295
    cout << "Vertex betweenness" << endl;
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;
86
}
296 87

  
297
    Viter vi, vi_end;
298
    int i = 0;
299
    for (boost::tie(vi, vi_end) = boost::vertices(subGraph); vi != vi_end; ++vi) {
300
        cout << subGraph[*vi].id << "\t" << v_centrality_vec.at(i) << endl;
301
        ++i;
302
    }
88
Graph const& SubComponent::sub_graph() const {
89
    return sub_graph_;
303 90
}
91

  
custompackages/graph-parser/src/sub_component.h
11 11
#include <boost/graph/betweenness_centrality.hpp>
12 12
#include <boost/graph/copy.hpp>
13 13
#include "common.h"
14
#include "utility.h"
14 15

  
15 16
class SubComponent {
16
private:
17
    VertexVec art_points;
18
    VertexVec normal_vertices; // vertices that are not articulation points
19
    // std::vector<Vertex*> normal_vertices;
20
    // TODO: should this one be public?
21
    Graph subGraph;
22
    VertexMap weightMap;
23
    VertexMap weightReversedMap;
24

  
25
    StdVertexIndexMap v_index_std_map;
26
    VertexIndexMap v_index_map;
27
    vector<vector<int> > trafficMatrix;
28

  
29
    CentralityVec v_centrality_vec;
30
    CentralityMap v_centrality_map;
17
public:
18
    SubComponent();
19
    SubComponent(const StringSet art_points, const Graph sub_graph);
31 20

  
32
    // Traffic Matrix
21
    // Getter & Setter
22
    StringSet art_points() const;
23
    void set_art_points(StringSet& art_points);
33 24

  
34
    // Betweenness Centrality
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;
35 31

  
36
public:
37
    SubComponent();
38
    // SubComponent(VertexVec art_points, Graph subGraph);
39
    SubComponent(const VertexVec art_points, const Graph subGraph);
32
    // Output to console
33
    friend std::ostream& operator<<(std::ostream& os, const SubComponent& sc);
40 34

  
41 35
    void init();
42 36

  
43
    // Getter
44
    VertexVec get_art_points();
45
    int num_vertices();
46 37

  
47 38
    // calculate Link Weight
48 39
    void _initialize_weight();
......
63 54
    void _initializeBetweennessCentrality();
64 55
    void findBetweennessCentrality();
65 56
    void printBetweennessCentrality();
57

  
58
private:
59
    StringSet art_points_;
60
    StringVec normal_vertices; // vertices that are not articulation points
61
    // std::vector<Vertex*> normal_vertices;
62
    // TODO: should this one be public?
63
    std::map<std::string, Vertex> name_vertex_map_;
64
    Graph sub_graph_;
65
    VertexMap weightMap;
66
    VertexMap weightReversedMap;
67

  
68
    StdVertexIndexMap v_index_std_map;
69
    VertexIndexMap v_index_map;
70
    vector<vector<int> > trafficMatrix;
71

  
72
    CentralityVec v_centrality_vec;
73
    CentralityMap v_centrality_map;
74

  
75
    // Traffic Matrix
76

  
77
    // Betweenness Centrality
66 78
};
67 79

  
68 80

  
custompackages/graph-parser/src/utility.cpp
60 60
        return os;
61 61
    }
62 62

  
63
    std::ostream& operator<<(std::ostream& os, const std::set<std::string>& s) {
64
        /* can't make it work with a generic function
65
        ** std::ostream& opeartor<<(std::ostream& os, const Container<std::string>& s)
66
        */
67
        using namespace boost::spirit::karma;
68
        os << format("( " << (auto_ % "\n  ") << ")", s);
69
    }
70

  
71
}
72

  
73
namespace outopserror {
74
    template <typename T>
75
    std::ostream& operator<<(std::ostream& os, const std::set<T>& s) {
76
        /* can't make it work with a generic function
77
        ** std::ostream& opeartor<<(std::ostream& os, const Container<std::string>& s)
78
        */
79
        using namespace boost::spirit::karma;
80
        os << format("( " << (auto_ % "\n  ") << ")", s);
81
    }
63
    // std::ostream& operator<<(std::ostream& os, const std::set<std::string>& s) {
64
    //      can't make it work with a generic function
65
    //     ** std::ostream& opeartor<<(std::ostream& os, const Container<std::string>& s)
66

  
67
    //     using namespace boost::spirit::karma;
68
    //     os << format("(" << (auto_ % "\n  ") << ")", s);
69
    //     os << endl;
70
    // }
82 71
}
83 72

  
84 73
namespace graphext {
......
87 76
            r.insert(g[v].id);
88 77
        }
89 78
    }
90

  
91
    // template <typename Container>
92
    // void id_of_vertices(const Graph& g, const Container& container, std::set<std::string>& r) {
93
    void id_of_vertices(const Graph& g, const VertexVec& container, std::set<std::string>& r) {
94
        /*
95
        ** Find id for a vec
96
        */
97
        for (VertexVec::const_iterator ci = container.begin(); ci != container.end(); ++ci) {
98
            r.insert(g[*ci].id);
99
        }
100
    }
101 79
}
custompackages/graph-parser/src/utility.h
18 18

  
19 19
namespace outops {
20 20
    std::ostream& operator<<(std::ostream& os, const Graph& g);
21
    std::ostream& operator<<(std::ostream& os, const std::set<std::string>& s);
22
}
23 21

  
24
namespace outopserror {
25 22
    template <typename T>
26 23
    std::ostream& operator<<(std::ostream& os, const std::set<T>& s);
27 24
}
......
30 27
namespace graphext {
31 28
    void id_of_vertices(const Graph& g, std::set<std::string>& r);
32 29

  
33
    // template <typename Container>
34
    // void id_of_vertices(const Graph& g, const Container& container, std::set<std::string>& r);
35
    void id_of_vertices(const Graph& g, const VertexVec& container, std::set<std::string>& r);
30
    template <typename Container>
31
    void id_of_vertices(const Graph& g, const Container& container, std::set<std::string>& r);
36 32
}
33

  
34

  
35

  
36
#include "utility.tpp"
37

  
37 38
#endif //GRAPH_PARSER_UTILITY_H
39

  
custompackages/graph-parser/src/utility.tpp
1
namespace outops {
2
    template <typename T>
3
    std::ostream& operator<<(std::ostream& os, const std::set<T>& s) {
4
        using namespace boost::spirit::karma;
5
        os << format("(" << (auto_ % "\n  ") << ")", s);
6
        os << endl;
7
    }
8
}
9

  
10
namespace graphext {
11
    template <typename Container>
12
    void id_of_vertices(const Graph& g, const Container& container, std::set<std::string>& r) {
13
        /*
14
        ** Find id for a vec
15
        */
16
        for (typename Container::const_iterator ci = container.begin(); ci != container.end(); ++ci) {
17
            r.insert(g[*ci].id);
18
        }
19
    }
20
}
21

  

Also available in: Unified diff