Revision ee0dd796

View differences:

custompackages/graph-parser/CMakeLists.txt
5 5

  
6 6
set (PROJECT_SOURCE_DEFINITION_DIRECTORY ${PROJECT_SOURCE_DIR}/src)
7 7
#set (MAIN_FILE ${PROJECT_SOURCE_DEFINITION_DIRECTORY}/main.cpp)
8
 set (MAIN_FILE ${PROJECT_SOURCE_DEFINITION_DIRECTORY}/main.cpp src/parser.cpp src/parser.h src/common.h src/utility.cpp src/utility.h)
8
 set (MAIN_FILE ${PROJECT_SOURCE_DEFINITION_DIRECTORY}/main.cpp src/parser.cpp src/parser.h src/common.h src/utility.cpp src/utility.h src/centrality.cpp src/centrality.h src/sub_component.cpp src/sub_component.h src/bi_connected_components.cpp src/bi_connected_components.h)
9 9

  
10 10
set (CMAKE_RUNTIME_OUTPUT_DIRECTORY ${PROJECT_SOURCE_DIR}/bin)
11 11

  
custompackages/graph-parser/input/simple.edges
1
5 6 1
2
5 u 1
3
6 u 1
4
u 1 1
5
u 2 1
6
u 3 1
7
1 2 1
8
1 3 1
9
2 4 1
10
2 v 1
11
3 v 1
12
3 4 1
13
4 v 1
14
v 9 1
15
v 8 1
16
v 7 1
custompackages/graph-parser/src/Makefile
2 2
# Makefile for hello-boost-graph program
3 3
##############################################
4 4

  
5
BOOST_ROOT="/usr/local/boost/"
5
INCLUDES = -I/usr/local/boost/
6 6

  
7
main: main.o
8
	$(CXX) $(LDFLAGS) main.o -o ../bin/main
7
# define the C source files
8
SRCS = main.cpp bi_connected_components.cpp centrality.cpp parser.cpp sub_component.cpp utility.cpp
9 9

  
10
main.o: main.cpp
11
	$(CXX) $(CXXFLAGS) -I $(BOOST_ROOT) -std=c++11 -c main.cpp $(LIBS)
10

  
11
# define the C object files
12
#
13
# This uses Suffix Replacement within a macro:
14
#   $(name:string1=string2)
15
#         For each word in 'name' replace 'string1' with 'string2'
16
# Below we are replacing the suffix .c of all words in the macro SRCS
17
# with the .o suffix
18
#
19
OBJS = $(SRCS:.cpp=.o)
20

  
21
MAIN = main
22

  
23
# all: ../bin/$(MAIN)
24
# 	@echo  Simple compiler named main has been compiled
25

  
26
$(MAIN): $(OBJS)
27
	$(CXX) $(CFLAGS) $(INCLUDES) -o ../bin/$(MAIN) $(OBJS) $(LFLAGS) $(LIBS )
28

  
29
# this is a suffix replacement rule for building .o's from .c's
30
# it uses automatic variables $<: the name of the prerequisite of
31
# the rule(a .c file) and $@: the name of the target of the rule (a .o file)
32
# (see the gnu make manual section about automatic variables)
33
.cpp.o:
34
	$(CXX) $(CFLAGS) $(INCLUDES) -std=c++11 -c $<  -o $@
12 35

  
13 36
# remove object files and executable when user executes "make clean"
14 37
clean:
15
	rm *.o ./bin/main
38
	$(RM) *.o ../bin/$(MAIN)
custompackages/graph-parser/src/bi_connected_components.cpp
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
}
custompackages/graph-parser/src/bi_connected_components.h
1
//
2
// Created by quynh on 1/9/16.
3
//
4

  
5
#ifndef GRAPH_PARSER_BI_CONNECTED_COMPONENTS_H
6
#define GRAPH_PARSER_BI_CONNECTED_COMPONENTS_H
7

  
8
#include <boost/graph/biconnected_components.hpp>
9
#include <queue>
10
#include "common.h"
11
#include "parser.h"
12
#include "utility.h"
13
#include "sub_component.h"
14

  
15

  
16
typedef std::vector<edges_size_type> ComponentVec;
17
typedef boost::iterator_property_map<ComponentVec::iterator, EdgeIndexMap> ComponentMap;
18

  
19
typedef map<Vertex, vector<int> > ArtPointComponentStdMap;
20
typedef boost::associative_property_map<ArtPointComponentStdMap> ArtPointComponentMap;
21

  
22
typedef std::map<int, vector<Vertex> > ComponentArtPointStdMap;
23
typedef boost::associative_property_map<ComponentArtPointStdMap> ComponentArtPointMap;
24

  
25
typedef vector<vector<Vertex> > Bcc_t;
26
typedef vector<vector<Vertex> >::iterator BccIter_t;
27

  
28

  
29

  
30
typedef struct {
31
    int component_index;
32
    Vertex art_point;
33
    string type;
34
} QueueElem;
35

  
36
class BiConnectedComponents {
37
private:
38
    // EdgeIndexMap - boost will return the component id that each edge in the graph belongs to.
39
    StdEdgeIndexMap e_index_std_map;
40
    EdgeIndexMap e_index_map;
41

  
42
    // VertexIndexMap - since we use listS instead of vecS, this one maps each vertex to an id
43
    StdVertexIndexMap v_index_std_map;
44

  
45
    int num_of_bcc = -1;
46

  
47
    std::queue<QueueElem> Q;
48

  
49
public:
50
    typedef vector<SubComponent> Component_t;
51
    typedef vector<SubComponent>::iterator ComponentIter_t;
52

  
53
    Graph g;
54

  
55
    VertexIndexMap v_index_map;
56
    ComponentVec component_vec;
57
    ComponentMap component_map;
58

  
59
    vector<Vertex> art_points;
60

  
61
    Bcc_t bcc_vertices;
62
    Component_t BCCs;
63

  
64
    ArtPointComponentStdMap art_point_component_std_map;
65
    ArtPointComponentMap art_point_component_map;
66

  
67
    ComponentArtPointStdMap component_art_point_std_map;
68
    ComponentArtPointMap component_art_point_map;
69

  
70

  
71
    BiConnectedComponents(const Graph &g);
72
    void init();
73
    void findBiConnectedComponents();
74
    void createSubComponents();
75
    void print();
76

  
77
    int num_bcc();
78
    void verticesInBCC();
79
    void testVerticesInBCC();
80

  
81
    bool hasVertex(Vertex v, int comp_index);
82
    void processArtPoints();
83
    void testProcessArtPoints();
84

  
85
    VertexVec get_art_points_for_component(int comp_index);
86
    vector<int> get_components_for_art_point(Vertex vertex);
87

  
88
    VertexVec get_normal_vertices_for_component(int comp_index);
89

  
90
    int num_of_vertices_in_component(int comp_index);
91

  
92
    // Calculate link weight (component tree weight)
93
    void compute_weight();
94
    void _initialize_weight();
95
    void _initialize_queue();
96
    void _find_unknown_weight_wrt_art_point(Vertex art_point);
97
    void _find_unknown_weight_wrt_component(int comp_index);
98
    void _find_unknown_weight_for_component(int comp_index, VertexVec& unknown_weight_vertices);
99
    bool _verify_weight(int comp_index, Vertex art_point, int weight);
100
    void print_weight();
101

  
102
    // Calculate Betweenness Centrality
103
    void findBetweennessCentrality();
104
    void printBetweennessCentrality();
105

  
106
    // Function used in debugging
107
    void _print_art_points();
108
    void _test_set_difference();
109

  
110
};
111

  
112

  
113
#endif //GRAPH_PARSER_BI_CONNECTED_COMPONENTS_H
custompackages/graph-parser/src/centrality.cpp
24 24

  
25 25
    // Nov 20, 2015
26 26
    // http://stackoverflow.com/questions/15432104/how-to-create-a-propertymap-for-a-boost-graph-using-lists-as-vertex-container
27
    typedef std::map<Vertex, size_t> StdVertexIndexMap;
28
    StdVertexIndexMap idxMap;
29 27

  
30
    // This property map is an adaptor that converts any type that is a model of Unique Associative Container such as std::map into a mutable Lvalue Property Map.
31
    typedef boost::associative_property_map<StdVertexIndexMap> VertexIndexMap;
32
    VertexIndexMap v_index(idxMap);
28
    StdVertexIndexMap v_index_std_map;
29
    VertexIndexMap v_index_map(v_index_std_map);
33 30

  
34 31
    // Populate the indexMap
35
    Viter v_iter, v_iter_end;
32
    Viter vi, ve; // vertex_iterator, vertex_iterator_end
36 33
    size_t i = 0;
37
    for (boost::tie(v_iter, v_iter_end) = boost::vertices(g); v_iter != v_iter_end; ++v_iter) {
38
        boost::put(v_index, *v_iter, i);
34
    for (boost::tie(vi, ve) = boost::vertices(g); vi != ve; ++vi) {
35
        boost::put(v_index_map, *vi, i);
39 36
        ++i;
40 37
    }
41 38

  
......
43 40
    CentralityVec v_centrality_vec(boost::num_vertices(g), 0);
44 41

  
45 42
    typedef boost::iterator_property_map<CentralityVec::iterator, VertexIndexMap> CentralityMap;
46
    CentralityMap v_centrality_map(v_centrality_vec.begin(), v_index);
43
    CentralityMap v_centrality_map(v_centrality_vec.begin(), v_index_map);
47 44

  
48 45
    // Nov 26, try out the normal call to centrality().This version is not working.
49 46
//    brandes_betweenness_centrality( g, boost::centrality_map(v_centrality_map));
50 47

  
51 48
    // http://stackoverflow.com/questions/30263594/adding-a-vertex-index-to-lists-graph-on-the-fly-for-betweenness-centrality
52 49
    // Use named-parameter
53
    brandes_betweenness_centrality(g, boost::centrality_map(v_centrality_map).vertex_index_map(v_index));
50
    brandes_betweenness_centrality(g, boost::centrality_map(v_centrality_map).vertex_index_map(v_index_map));
54 51
    relative_betweenness_centrality(g, v_centrality_map);
55 52

  
56 53

  
57 54
    // Print result of v_centrality_map to console
58 55
    cout << "Vertex betweenness" << endl;
59 56
    i = 0;
60
    for (boost::tie(v_iter, v_iter_end) = boost::vertices(g); v_iter != v_iter_end; ++v_iter) {
61
        cout << g[*v_iter].id << "\t" << v_centrality_vec.at(i) << endl;
57
    for (boost::tie(vi, ve) = boost::vertices(g); vi != ve; ++vi) {
58
        cout << g[*vi].id << "\t" << v_centrality_vec.at(i) << endl;
62 59
        ++i;
63 60
    }
64 61

  
......
71 68
void writeBetweennessCentrality(const Graph &g, std::vector<double> v_centrality_vec, string fileSuffix) {
72 69
    cout << "XXX Writing to File";
73 70
    string filePath = "../output/boost_" + fileSuffix + ".csv";
74
    ofstream outFile(filePath);
71
    ofstream outFile(filePath.c_str());
75 72

  
76 73
    Viter vi, ve;
77 74
    size_t i = 0;
......
84 81
    outFile.close();
85 82

  
86 83
    cout << "XXX Writing to File 2";
87
}
84
}
custompackages/graph-parser/src/centrality.h
5 5
#ifndef GRAPH_PARSER_CENTRALITY_H
6 6
#define GRAPH_PARSER_CENTRALITY_H
7 7

  
8
#include <iostream>
9 8
#include <fstream>
10 9
#include <boost/graph/betweenness_centrality.hpp>
11 10
#include "common.h"
custompackages/graph-parser/src/common.h
5 5
#ifndef GRAPH_PARSER_COMMON_H
6 6
#define GRAPH_PARSER_COMMON_H
7 7

  
8
#include <iostream>
9
#include <cstdlib>
10
#include <exception>
11
#include <string>
12
#include <set>
13
#include <list>
14
#include <vector>
15

  
8 16
#include <boost/graph/adjacency_list.hpp>
17
#include <boost/graph/iteration_macros.hpp>
9 18

  
10 19
using namespace std;
11 20

  
12
struct Router {
21
class Router { // aka Vertex
22
public:
13 23
    string id;
14 24
    string name;
15 25

  
16 26
    Router() { };
27
    Router(string id, string name) : id(id), name(name) { };
17 28

  
18
    Router(string id, string name) : id(id), name(name) { }
29
    bool operator<(const Router& rhs)
30
    {
31
       return id < rhs.id;
32
    }
33
   bool operator==(const Router& rhs)
34
   {
35
       return id == rhs.id;
36
   }
19 37
};
20 38

  
21
struct Link {
39
struct Link { // aka Edge
22 40
    double cost;
23 41

  
24 42
    Link() { };
25

  
26 43
    Link(double cost) : cost(cost) { };
27 44
};
28 45

  
......
31 48
        Router, Link> Graph;
32 49
typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
33 50
typedef boost::graph_traits<Graph>::vertex_iterator Viter;
51
typedef std::pair<Viter, Viter> Vpair;
34 52

  
35 53
typedef boost::graph_traits<Graph>::edge_descriptor Edge;
54
typedef boost::graph_traits<Graph>::edge_iterator Eiter;
55
typedef std::pair<Eiter, Eiter> Epair;
56
typedef boost::graph_traits<Graph>::edges_size_type edges_size_type;
57

  
58
typedef map<Vertex, size_t> StdVertexIndexMap;
59
// This property map is an adaptor that converts any type that is a model of Unique Associative Container such as std::map into a mutable Lvalue Property Map.
60
typedef boost::associative_property_map<StdVertexIndexMap> VertexIndexMap;
61

  
62
typedef map<Edge, size_t> StdEdgeIndexMap;
63
typedef boost::associative_property_map<StdEdgeIndexMap> EdgeIndexMap;
64

  
65

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

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

  
72

  
73
typedef std::vector<double> CentralityVec;
74
typedef boost::iterator_property_map<CentralityVec::iterator, VertexIndexMap> CentralityMap;
36 75

  
37 76
#endif //GRAPH_PARSER_COMMON_H
38 77

  
custompackages/graph-parser/src/main.cpp
2 2
#include "parser.h"
3 3
#include "utility.h"
4 4
#include "centrality.h"
5
#include "bi_connected_components.h"
5 6

  
6 7

  
8
void handleSimpleGraph() {
9
    /* I don't understand the output. Why there are 8 vertices?
10
        Simple graph
11
        0
12
        1
13
        2
14
        3
15
        4
16
        5
17
        6
18
        7
19
        8
20
    */
21
    typedef boost::adjacency_list<> G;
22
    G a;
23
    {
24
        boost::graph_traits<G>::vertex_descriptor v, u, t;
25
        u = vertex(1, a);
26
        v = vertex(8, a);
27
        // t = vertex(5, a);
28
        add_edge(u, v, a);
29
        // add_edge(u, t, a);
30
    }
31

  
32
    std::set<typename boost::graph_traits<G>::vertex_descriptor> av;
33
    cout << "Simple graph" << endl;
34
    BGL_FORALL_VERTICES_T(v, a, G) {
35
        cout << v << endl;
36
    }
37
}
7 38
void handleSimpleInput(string filePath) {
8 39
    // Read the input.edges
9 40
    Graph g;
......
36 67
    cout << "Done with Betweenness Centrality" << endl;
37 68
}
38 69

  
70
void testHeuristic(string filePath) {
71
    Graph g;
72
    readEdgeFile(filePath, g);
73
    outops::operator<<(cout, g);
74
    BiConnectedComponents bcc(g);
75
    // bcc.compute_weight();
76
    // bcc.findBetweennessCentrality();
77
    // bcc.printBetweennessCentrality();
78
    // bcc.print_weight();
79
    // bcc.print();
80
    cout << "DONE" << endl;
81

  
39 82

  
40
int main(int, char *[]) {
41
    string edgeFilePath = "../input/ninux_30_1.edges";
42
    handleSimpleInput(edgeFilePath);
83
}
43 84

  
44
    string jsonFilePath = "../input/olsr-netjson.json";
45
    handleJsonInput(jsonFilePath);
85
int main(int, char *[]) {
86
//    string edgeFilePath = "../input/ninux_30_1.edges";
87
//    testHeuristic(edgeFilePath);
88
//    handleSimpleInput(edgeFilePath);
89
//
90
//    string jsonFilePath = "../input/olsr-netjson.json";
91
//    handleJsonInput(jsonFilePath);
92
//
93
//    string complexJsonFilePath = "../input/jsoninfo_topo.json";
94
//    handleComplexJsonInput(complexJsonFilePath);
46 95

  
47
    string complexJsonFilePath = "../input/jsoninfo_topo.json";
48
    handleComplexJsonInput(complexJsonFilePath);
49 96

  
97
    string simpleGraphFilePath = "../input/simple.edges";
98
    testHeuristic(simpleGraphFilePath);
50 99
    return 0;
51 100
}
custompackages/graph-parser/src/parser.cpp
48 48
    typedef std::map<std::string, Vertex> NameVertexMap;
49 49
    NameVertexMap routers;
50 50

  
51
    ifstream inFile(filePath);
51
    ifstream inFile(filePath.c_str());
52 52

  
53 53
    vector<string> strs;
54 54
    for (string line; getline(inFile, line); /**/) {
......
60 60
        if (strs.size() == 3) {
61 61
            string source = strs[0];
62 62
            string target = strs[1];
63
            double cost = stof(strs[2]);
63
            // TODO: use atof as a way around the error: ‘stof’ was not declared in this scope
64
            // double cost = stof(strs[2]);
65
            double cost = atof(strs[2].c_str());
64 66

  
65 67
            addLinkToGraph(source, target, cost, g, routers);
66 68

  
custompackages/graph-parser/src/parser.h
5 5
#ifndef GRAPH_PARSER_PARSER_H
6 6
#define GRAPH_PARSER_PARSER_H
7 7

  
8
#include <iostream>
9 8
#include <boost/algorithm/string.hpp>
10 9
#include <boost/property_tree/json_parser.hpp>
11 10
#include <boost/foreach.hpp>
custompackages/graph-parser/src/sub_component.cpp
1
//
2
// Created by quynh on 1/9/16.
3
//
4

  
5
#include "sub_component.h"
6

  
7

  
8
SubComponent::SubComponent() {
9
}
10

  
11
SubComponent::SubComponent(VertexVec aart_points, Graph asubGraph) : art_points(aart_points), subGraph(asubGraph) {
12
// SubComponent::SubComponent(VertexVec aart_points, Graph asubGraph) {
13
    // art_points = aart_points;
14
    // subGraph = asubGraph;
15
    // Deep copy for art_points
16
    // cout << "ABC " << endl;
17
    // for (VertexVecIter vi = aart_points.begin(); vi != aart_points.end(); ++vi) {
18
    //     Vertex v = Vertex(*vi);
19
    //     this->art_points.insert(this->art_points.end(), v);
20
    //     cout << "   asubGraph " << asubGraph[*vi].name << endl;
21
    //     cout << "    subGraph " << subGraph[*vi].name << endl;
22
    // }
23

  
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

  
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();
58
}
59

  
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();
100
}
101

  
102
VertexVec SubComponent::get_art_points() {
103
    return art_points;
104
}
105

  
106
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
    }
165
}
166

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

  
175
    // Reset the main diagonal to 0
176
    for (int j = 0; j < size; ++j) {
177
        trafficMatrix[j][j] = 0;
178
    }
179
}
180

  
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
    try {
190
        return boost::get(v_index_map, v);
191
    }
192
    catch (exception& e) {
193
        // TODO handle exception here
194
        cout << "ERROR _indexOfVertex() " << e.what() << endl;
195
        return -1;
196
    }
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
    try {
232
        return trafficMatrix[i_1][i_2];
233
    }
234
    catch (exception& e) {
235
        cout << "ERROR: getTrafficMatrix: " << e.what() << endl;
236
    }
237

  
238
}
239

  
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

  
254
}
255

  
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;
267
    }
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;
273
    }
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
}
293

  
294
void SubComponent::printBetweennessCentrality() {
295
    cout << "Vertex betweenness" << endl;
296

  
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
    }
303
}
custompackages/graph-parser/src/sub_component.h
1
//
2
// Created by quynh on 1/9/16.
3
//
4

  
5
// Problem with deep copy
6
// http://stackoverflow.com/questions/6955578/subtraction-and-intersection-of-two-vectors-of-pointers-in-c
7

  
8
#ifndef GRAPH_PARSER_SUB_COMPONENT_H
9
#define GRAPH_PARSER_SUB_COMPONENT_H
10

  
11
#include <boost/graph/betweenness_centrality.hpp>
12
#include <boost/graph/copy.hpp>
13
#include "common.h"
14

  
15
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;
31

  
32
    // Traffic Matrix
33

  
34
    // Betweenness Centrality
35

  
36
public:
37
    SubComponent();
38
    // SubComponent(VertexVec art_points, Graph subGraph);
39
    SubComponent(const VertexVec art_points, const Graph subGraph);
40

  
41
    void init();
42

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

  
47
    // calculate Link Weight
48
    void _initialize_weight();
49
    void setWeight(Vertex art_point, int value);
50
    int getWeight(Vertex art_point);
51
    int getReversedWeight(Vertex art_point);
52
    void printWeight();
53
    void _find_vertices_with_unknown_weight(VertexVec& unknown_weight_vertices);
54

  
55
    // Traffic Matrix
56
    int getTrafficMatrix(Vertex v_1, Vertex v_2);
57
    void _initializeTrafficMatrix();
58
    int _indexOfVertex(Vertex v);
59
    void _setTrafficMatrix(Vertex v_1, Vertex v_2, int value);
60
    void _computeTrafficMatrix();
61

  
62
    // Betweenness Centrality
63
    void _initializeBetweennessCentrality();
64
    void findBetweennessCentrality();
65
    void printBetweennessCentrality();
66
};
67

  
68

  
69
#endif //GRAPH_PARSER_SUB_COMPONENT_H
custompackages/graph-parser/src/utility.cpp
3 3
//
4 4

  
5 5
#include "utility.h"
6

  
6
using namespace boost;
7 7

  
8 8
void printGraph(Graph &g) {
9 9
    typename boost::graph_traits<Graph>::out_edge_iterator out_i, out_ie;
......
26 26
        }
27 27
        cout << endl;
28 28
    }
29
}
30

  
31
namespace outops {
32
    std::ostream& operator<<(std::ostream& os, const Graph& g)
33
    {
34

  
35
        os <<   "Graph has: \n"
36
                "---------- " << boost::num_vertices(g) << " vertices\n"
37
                "---------- " << boost::num_edges(g) << " edges\n";
38

  
39
        std::set<std::string> verticesSet;
40
        BGL_FORALL_VERTICES_T(v, g, Graph) verticesSet.insert(g[v].id);
41

  
42
        std::vector<std::string> edgesVec;
43
        std::vector<double> costsVec;
44
        BGL_FORALL_EDGES_T(e, g, Graph) {
45
            std::string s = "(" + g[e.m_source].id + ", " + g[e.m_target].id + ") - " + std::to_string(g[e].cost);
46
            edgesVec.push_back(s);
47
            costsVec.push_back(g[e].cost);
48
        }
49

  
50
        using namespace boost::spirit::karma;
51
        os <<   "Vertices:\n"
52
                "  ";
53
        os << format("(" << auto_ % ", " << ") ", verticesSet);
54
        os << "\n";
55

  
56
        os <<   "Edges:\n";
57
        os << format("  " << (auto_ % "\n  ") << eol, edgesVec);
58
        os << "\n";
59

  
60
        return os;
61
    }
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
    }
82
}
83

  
84
namespace graphext {
85
    void id_of_vertices(const Graph& g, std::set<std::string>& r) {
86
        BGL_FORALL_VERTICES_T(v, g, Graph) {
87
            r.insert(g[v].id);
88
        }
89
    }
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
    }
29 101
}
custompackages/graph-parser/src/utility.h
8 8
#include <iostream>
9 9
#include <boost/graph/graph_traits.hpp>
10 10
#include <boost/graph/undirected_graph.hpp>
11
#include <boost/spirit/include/karma.hpp>
12
#include <boost/graph/iteration_macros.hpp>
11 13
#include "common.h"
12 14

  
13 15

  
16

  
14 17
void printGraph(Graph &g);
15 18

  
19
namespace outops {
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

  
24
namespace outopserror {
25
    template <typename T>
26
    std::ostream& operator<<(std::ostream& os, const std::set<T>& s);
27
}
28

  
29
// non-member functions operating on Graph datatype.
30
namespace graphext {
31
    void id_of_vertices(const Graph& g, std::set<std::string>& r);
32

  
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);
36
}
16 37
#endif //GRAPH_PARSER_UTILITY_H

Also available in: Unified diff