Statistics
| Branch: | Revision:

root / fiddle / boost-networkx-comparision / src / boost_graph.cpp @ 1705a309

History | View | Annotate | Download (12.9 KB)

1
#include <fstream>
2
#include <iostream>
3
#include <boost/algorithm/string.hpp>
4
#include <boost/graph/graph_traits.hpp>
5
#include <boost/graph/undirected_graph.hpp>// A subclass to provide reasonable arguments to adjacency_list for a typical undirected graph
6
#include <boost/graph/betweenness_centrality.hpp>
7
#include <boost/property_tree/json_parser.hpp>
8
#include <boost/foreach.hpp>
9
#include <boost/tuple/tuple.hpp>
10

    
11
using namespace std;
12

    
13

    
14
struct Router {
15
    string id;
16
    string name;
17

    
18
    Router() { };
19

    
20
    Router(string id, string name) : id(id), name(name) { }
21
};
22

    
23
struct Link {
24
    double cost;
25

    
26
    Link() { };
27

    
28
    Link(double cost) : cost(cost) { };
29
};
30

    
31
typedef std::array<string, 3> graphDataType;
32
typedef boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS,
33
        Router, Link> Graph;
34
typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
35
typedef boost::graph_traits<Graph>::vertex_iterator Viter;
36

    
37
typedef boost::graph_traits<Graph>::edge_descriptor Edge;
38

    
39
vector<vector<string>> readFile1(string filePath) {
40
    ifstream inFile(filePath);
41

    
42
    // Reading to vector<string>
43
    vector<vector<string>> contents;
44
    vector<string> strs;
45
    for (string line; getline(inFile, line); /**/) {
46
        boost::split(strs, line, boost::is_any_of(" "));
47
        contents.push_back(strs);
48
    }
49
    inFile.close();
50

    
51
    return contents;
52
}
53

    
54
vector<graphDataType> readFile2(string filePath) {
55
    ifstream inFile(filePath);
56

    
57
    // Reading to vector<graphDataType>
58
    vector<graphDataType> contents;
59
    vector<string> strs;
60
    graphDataType graph_strs;
61
    for (string line; getline(inFile, line); /**/) {
62
        boost::split(strs, line, boost::is_any_of(" "));
63

    
64
        // Cast vector<string> to array<string, 3>
65
        // TODO: this is really crude way to do it.
66
        // TODO: how to copy some element of vector to array
67
        vector<string>::iterator i = strs.begin();
68
        for (int i = 0; i < strs.size(); ++i) {
69
            graph_strs[i] = strs[i];
70
        }
71
        contents.push_back(graph_strs);
72
    }
73
    inFile.close();
74

    
75
    return contents;
76

    
77
}
78

    
79
template <typename NameVertexMap>
80
void addLinkToGraph(string s1, string s2, double cost, Graph& g, NameVertexMap& routers) {
81
    // TODO: change routers --> routers_map
82

    
83
    Vertex v1, v2;
84
    Edge e;
85

    
86
    typename NameVertexMap::iterator pos;
87
    bool inserted;
88

    
89
    boost::tie(pos, inserted) = routers.insert(std::make_pair(s1, Vertex()));
90
    if (inserted) {
91
        v1 = boost::add_vertex(g);
92
        routers[s1] = v1;
93
        pos->second = v1;
94
        g[v1].id = s1;
95
        g[v1].name = s1;
96
    } else {
97
        v1 = pos->second;
98
    }
99

    
100
    boost::tie(pos, inserted) = routers.insert(std::make_pair(s2, Vertex()));
101
    if (inserted) {
102
        v2 = boost::add_vertex(g);
103
        routers[s2] = v2;
104
        pos->second = v2;
105
        g[v2].id = s2;
106
        g[v2].name = s2;
107
    } else {
108
        v2 = pos->second;
109
    }
110

    
111
    // Add edge (aka. link) connecting 2 vertices
112
    boost::tie(e, inserted) = boost::add_edge(v1, v2, g);
113
    if (inserted) {
114
        g[e].cost = cost;
115
    }
116
}
117

    
118
void readJson(string filePath, Graph& g) {
119
    vector<graphDataType> contents;
120
    boost::property_tree::ptree pt;
121
    boost::property_tree::read_json(filePath, pt);
122

    
123
    Vertex v1, v2;
124
    Edge e;
125

    
126
    // NameVertexMap is to keep track of which router has already been added
127
    typedef std::map<std::string, Vertex> NameVertexMap;
128
    NameVertexMap routers;
129

    
130
    BOOST_FOREACH(const boost::property_tree::ptree::value_type &v, pt.get_child("links"))
131
    {
132
        cout << "X" << endl;
133
        cout << v.second.get_value<std::string>() << " ";
134
        string source = v.second.get_child("source").get_value<std::string>();
135
        string target = v.second.get_child("target").get_value<std::string>();
136
        double cost = v.second.get_child("cost").get_value<double>();
137

    
138

    
139
        addLinkToGraph(source, target, cost, g, routers);
140
    }
141
}
142

    
143
void readComplexJson(string filePath, Graph &g) {
144
    vector<graphDataType> contents;
145
    boost::property_tree::ptree pt;
146
    boost::property_tree::read_json(filePath, pt);
147

    
148
    Vertex v1, v2;
149
    Edge e;
150

    
151
    // NameVertexMap is to keep track of which router has already been added
152
    typedef std::map<std::string, Vertex> NameVertexMap;
153
    NameVertexMap routers;
154

    
155
    BOOST_FOREACH(const boost::property_tree::ptree::value_type &v, pt.get_child("topology"))
156
    {
157
        cout << "X" << endl;
158
        cout << v.second.get_value<std::string>() << " ";
159
        string source = v.second.get_child("lastHopIP").get_value<std::string>();
160
        string target = v.second.get_child("destinationIP").get_value<std::string>();
161
        double cost = v.second.get_child("neighborLinkQuality").get_value<double>();
162

    
163

    
164
        addLinkToGraph(source, target, cost, g, routers);
165
    }
166

    
167
}
168

    
169
void printVector1(vector<vector<string>> contents) {
170
    vector<vector<string>>::iterator i;
171
    vector<string>::iterator j;
172

    
173
    int count = 0;
174
    for (i = contents.begin(); i != contents.end(); ++i) {
175
        for (j = (*i).begin(); j != (*i).end(); ++j) {
176
            cout << *j << endl;
177
        }
178
        cout << endl;
179
    }
180
}
181

    
182
void printVector2(vector<graphDataType> contents) {
183
    vector<graphDataType>::iterator i;
184
    int count = 0;
185
    for (i = contents.begin(); i != contents.end(); ++i) {
186
        unsigned long size = (*i).size();
187
//        cout << "size = " << size << endl;
188
//        cout << "&i = " << &i << endl;
189
        for (int j = 0; j < size; ++j) {
190
            cout << (*i)[j] << endl;
191
        }
192
        cout << endl;
193
    }
194
}
195

    
196

    
197
Vertex findRouter(string id, Graph g) {
198
    typedef pair<Viter, Viter> ViterPair;
199
    ViterPair vs = boost::vertices(g); // return the pointer at the beginning and at the end of the range.
200
    cout << &vs.first << "  ***  " << &vs.second << endl;
201
    Viter vit = vs.first;
202
    for (vit; vit != vs.second; ++vit) {
203
        cout << "+++ " << g[*vit].id << endl;
204
        cout << &vit << endl;
205
        cout << "Found " << id << endl;
206
        if (g[*vit].id == id) {
207

    
208
            return (*vit);
209
        }
210
    }
211
    cout << "Not Found " << id << endl;
212
    return NULL;
213
}
214

    
215
void createUndirectedGraph(vector<graphDataType> contents, Graph &g) {
216
    /*
217
     * Check the BGL Tutorial, pg. 64
218
    */
219
    Vertex v1, v2;
220
    Edge e;
221

    
222
    // NameVertexMap is to keep track of which router has already been added
223
    typedef std::map<std::string, Vertex> NameVertexMap;
224
    NameVertexMap routers;
225
    NameVertexMap::iterator pos;
226
    bool inserted;
227

    
228
    vector<graphDataType>::iterator iter;
229
    for (iter = contents.begin(); iter != contents.end(); ++iter) {
230
        // Get the id of 2 vertices (routers), and add them to graph
231
        if ((*iter).size() != 3) {
232
            cout << "XXX" << endl;
233
            continue;
234
        }
235
        string s1 = (*iter)[0];
236
        string s2 = (*iter)[1];
237
        float cost = std::stof((*iter)[2]);
238

    
239
        cout << s1 << " " << s2 << " " << cost << endl;
240

    
241
        boost::tie(pos, inserted) = routers.insert(std::make_pair(s1, Vertex()));
242
        if (inserted) {
243
//            cout << "Added vertex " << s1 << endl;
244
            v1 = boost::add_vertex(g);
245
            routers[s1] = v1;
246
            pos->second = v1;
247

    
248
            //Update the id and name
249
            g[v1].id = s1;
250
            g[v1].name = s1;
251
        } else {
252
//            cout << "Found vertex " << s1 << endl;
253
            v1 = pos->second;
254
        }
255

    
256
        boost::tie(pos, inserted) = routers.insert(std::make_pair(s2, Vertex()));
257
        if (inserted) {
258
//            cout << "Added vertex " << s2 << endl;
259
            v2 = boost::add_vertex(g);
260
            routers[s2] = v2;
261
            pos->second = v2;
262
            g[v2].id = s2;
263
            g[v2].name = s2;
264
        } else {
265
//            cout << "Found vertex " << s2 << endl;
266
            v2 = pos->second;
267
        }
268

    
269
        // Add edge (aka. link) connecting 2 vertices
270
        boost::tie(e, inserted) = boost::add_edge(v1, v2, g);
271
        if (inserted) {
272
            cout << "Added edge with weight " << cost << endl;
273
            g[e].cost = cost;
274
        }
275
    }
276
}
277

    
278
void printGraph(Graph g) {
279
    typename boost::graph_traits<Graph>::out_edge_iterator out_i, out_ie;
280
    Viter v_i, v_ie;
281

    
282
    Vertex v;
283
    Edge e;
284

    
285
    boost::tie(v_i, v_ie) = boost::vertices(g);
286
    for (v_i; v_i != v_ie; ++v_i) {
287
        v = *v_i;
288
        boost::tie(out_i, out_ie) = boost::out_edges(v, g);
289

    
290
        for (out_i; out_i != out_ie; ++out_i) {
291
            e = *out_i;
292
            Vertex src = boost::source(e, g);
293
            Vertex targ = boost::target(e, g);
294
            std::cout << "(" << g[src].id << ","
295
            << g[targ].id << ") ";
296
        }
297
        cout << endl;
298
    }
299
}
300

    
301
void writeBetweennessCentrality(Graph &g, std::vector<double> v_centrality_vec, string fileSuffix) {
302
    cout << "XXX Writing to File";
303
    string filePath = "../output/boost_" + fileSuffix + ".csv";
304
    ofstream outFile(filePath);
305

    
306
    // Reading to vector<graphDataType>
307
    Viter vi, ve;
308
    size_t i = 0;
309
    if (outFile.is_open()) {
310
        for(boost::tie(vi, ve) = boost::vertices(g); vi != ve; ++vi) {
311
            outFile << g[*vi].id << ", " << v_centrality_vec.at(i) << endl;
312
            ++i;
313
        }
314
    }
315
    outFile.close();
316

    
317
    cout << "XXX Writing to File 2";
318
}
319

    
320

    
321

    
322
void simpleBetweennessCentrality(Graph g, string fileSuffix) {
323
    // One way to create centrality_map
324
    //    boost::shared_array_property_map<double, boost::property_map<Graph, vertex_index_t>::const_type>
325
    //            centrality_map(num_vertices(g), get(boost::vertex_index, g));
326

    
327

    
328
    // Define VertexCentralityMap
329
//    typedef boost::property_map< Graph, boost::vertex_index_t>::type VertexIndexMap;
330
//    VertexIndexMap v_index = get(boost::vertex_index, g);
331
//    // Constructs a container with n elements. Each element is a copy of val.
332
//    std::vector< double > v_centrality_vec(boost::num_vertices(g), 0.0);
333
//    // Create the external property map
334
//    boost::iterator_property_map< std::vector< double >::iterator, VertexIndexMap >
335
//            v_centrality_map(v_centrality_vec.begin(), v_index);
336
//
337
//    brandes_betweenness_centrality( g, v_centrality_map);
338

    
339

    
340
    // Nov 20, 2015
341
    // http://stackoverflow.com/questions/15432104/how-to-create-a-propertymap-for-a-boost-graph-using-lists-as-vertex-container
342
    typedef std::map<Vertex, size_t> StdVertexIndexMap;
343
    StdVertexIndexMap idxMap;
344

    
345
    // 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.
346
    typedef boost::associative_property_map<StdVertexIndexMap> VertexIndexMap;
347
    VertexIndexMap v_index(idxMap);
348

    
349
    // Populate the indexMap
350
    Viter v_iter, v_iter_end;
351
    size_t i = 0;
352
    for (boost::tie(v_iter, v_iter_end) = boost::vertices(g); v_iter != v_iter_end; ++v_iter) {
353
        boost::put(v_index, *v_iter, i);
354
        ++i;
355
    }
356

    
357
    typedef std::vector<double> CentralityVec;
358
    CentralityVec v_centrality_vec(boost::num_vertices(g), 0);
359

    
360
    typedef boost::iterator_property_map< CentralityVec::iterator, VertexIndexMap > CentralityMap;
361
    CentralityMap v_centrality_map(v_centrality_vec.begin(), v_index);
362

    
363
    // http://stackoverflow.com/questions/30263594/adding-a-vertex-index-to-lists-graph-on-the-fly-for-betweenness-centrality
364
    // Use named-parameter
365
    brandes_betweenness_centrality( g, boost::centrality_map(v_centrality_map).vertex_index_map(v_index));
366
    relative_betweenness_centrality( g, v_centrality_map);
367

    
368
    // Nov 26, try out the normal call to centrality()
369
//    brandes_betweenness_centrality( g, boost::centrality_map(v_centrality_map));
370

    
371

    
372
    // Print result of v_centrality_map to console
373
    cout << "Vertex betweenness" << endl;
374
    i = 0;
375
    for(boost::tie(v_iter,v_iter_end) = boost::vertices(g); v_iter != v_iter_end; ++v_iter){
376
        cout << g[*v_iter].id << "\t" << v_centrality_vec.at(i) << endl;
377
        ++i;
378
    }
379

    
380
    // Write result of v_centrality_map to file.
381
    writeBetweennessCentrality(g, v_centrality_vec, fileSuffix);
382

    
383
}
384

    
385
void handleSimpleInput(string filePath) {
386
    // Read the input.edges
387
    vector<graphDataType> contents;
388
    contents = readFile2(filePath);
389
    printVector2(contents);
390
    Graph g;
391
    createUndirectedGraph(contents, g);
392
    cout << "Finish creating graph" << endl;
393

    
394
    simpleBetweennessCentrality(g, "edge_list");
395
}
396

    
397
void handleJsonInput(string filePath) {
398
    Graph g;
399
    readJson(filePath, g);
400
    printGraph(g);
401

    
402
    // Applying the betweenness centrality
403
    simpleBetweennessCentrality(g, "json_olsr");
404

    
405
    cout << "Done with Betweenness Centrality" << endl;
406
}
407

    
408
void handleComplexJsonInput(string filePath) {
409
    Graph g;
410
    readComplexJson(filePath, g);
411
    printGraph(g);
412

    
413
    // Applying the betweenness centrality
414
    simpleBetweennessCentrality(g, "json_topology");
415

    
416
    cout << "Done with Betweenness Centrality" << endl;
417
}
418

    
419

    
420
int main(int, char *[]) {
421
    string edgeFilePath = "../input/ninux_30_1.edges";
422
    handleSimpleInput(edgeFilePath);
423

    
424
    string jsonFilePath = "../input/olsr-netjson.json";
425
    handleJsonInput(jsonFilePath);
426

    
427
    string complexJsonFilePath = "../input/jsoninfo_topo.json";
428
    handleComplexJsonInput(complexJsonFilePath);
429

    
430
    return 0;
431
}