Statistics
| Branch: | Revision:

root / fiddle / boost-networkx-comparision / src / boost_graph.cpp @ 37200dce

History | View | Annotate | Download (12.4 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
        string source = v.second.get_child("source").get_value<std::string>();
133
        string target = v.second.get_child("target").get_value<std::string>();
134
        double cost = v.second.get_child("cost").get_value<double>();
135

    
136
        addLinkToGraph(source, target, cost, g, routers);
137
    }
138
}
139

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

    
145
    Vertex v1, v2;
146
    Edge e;
147

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

    
152
    BOOST_FOREACH(const boost::property_tree::ptree::value_type &v, pt.get_child("topology"))
153
    {
154
        string source = v.second.get_child("lastHopIP").get_value<std::string>();
155
        string target = v.second.get_child("destinationIP").get_value<std::string>();
156
        double cost = v.second.get_child("neighborLinkQuality").get_value<double>();
157

    
158

    
159
        addLinkToGraph(source, target, cost, g, routers);
160
    }
161

    
162
}
163

    
164
void printVector1(vector<vector<string>> contents) {
165
    vector<vector<string>>::iterator i;
166
    vector<string>::iterator j;
167

    
168
    int count = 0;
169
    for (i = contents.begin(); i != contents.end(); ++i) {
170
        for (j = (*i).begin(); j != (*i).end(); ++j) {
171
            cout << *j << endl;
172
        }
173
        cout << endl;
174
    }
175
}
176

    
177
void printVector2(vector<graphDataType> contents) {
178
    vector<graphDataType>::iterator i;
179
    int count = 0;
180
    for (i = contents.begin(); i != contents.end(); ++i) {
181
        unsigned long size = (*i).size();
182
        for (int j = 0; j < size; ++j) {
183
            cout << (*i)[j] << endl;
184
        }
185
        cout << endl;
186
    }
187
}
188

    
189

    
190
Vertex findRouter(string id, Graph g) {
191
    typedef pair<Viter, Viter> ViterPair;
192
    ViterPair vs = boost::vertices(g); // return the pointer at the beginning and at the end of the range.
193
    cout << &vs.first << "  ***  " << &vs.second << endl;
194
    Viter vit = vs.first;
195
    for (vit; vit != vs.second; ++vit) {
196
        cout << "+++ " << g[*vit].id << endl;
197
        cout << &vit << endl;
198
        cout << "Found " << id << endl;
199
        if (g[*vit].id == id) {
200

    
201
            return (*vit);
202
        }
203
    }
204
    cout << "Not Found " << id << endl;
205
    return NULL;
206
}
207

    
208
void createUndirectedGraph(vector<graphDataType> contents, Graph &g) {
209
    /*
210
     * Check the BGL Tutorial, pg. 64
211
    */
212
    Vertex v1, v2;
213
    Edge e;
214

    
215
    // NameVertexMap is to keep track of which router has already been added
216
    typedef std::map<std::string, Vertex> NameVertexMap;
217
    NameVertexMap routers;
218
    NameVertexMap::iterator pos;
219
    bool inserted;
220

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

    
232
        boost::tie(pos, inserted) = routers.insert(std::make_pair(s1, Vertex()));
233
        if (inserted) {
234
            v1 = boost::add_vertex(g);
235
            routers[s1] = v1;
236
            pos->second = v1;
237

    
238
            //Update the id and name
239
            g[v1].id = s1;
240
            g[v1].name = s1;
241
        } else {
242
            v1 = pos->second;
243
        }
244

    
245
        boost::tie(pos, inserted) = routers.insert(std::make_pair(s2, Vertex()));
246
        if (inserted) {
247
            v2 = boost::add_vertex(g);
248
            routers[s2] = v2;
249
            pos->second = v2;
250
            g[v2].id = s2;
251
            g[v2].name = s2;
252
        } else {
253
            v2 = pos->second;
254
        }
255

    
256
        // Add edge (aka. link) connecting 2 vertices
257
        boost::tie(e, inserted) = boost::add_edge(v1, v2, g);
258
        if (inserted) {
259
            g[e].cost = cost;
260
        }
261
    }
262
}
263

    
264
void printGraph(Graph g) {
265
    typename boost::graph_traits<Graph>::out_edge_iterator out_i, out_ie;
266
    Viter v_i, v_ie;
267

    
268
    Vertex v;
269
    Edge e;
270

    
271
    boost::tie(v_i, v_ie) = boost::vertices(g);
272
    for (v_i; v_i != v_ie; ++v_i) {
273
        v = *v_i;
274
        boost::tie(out_i, out_ie) = boost::out_edges(v, g);
275

    
276
        for (out_i; out_i != out_ie; ++out_i) {
277
            e = *out_i;
278
            Vertex src = boost::source(e, g);
279
            Vertex targ = boost::target(e, g);
280
            std::cout << "(" << g[src].id << ","
281
            << g[targ].id << ") ";
282
        }
283
        cout << endl;
284
    }
285
}
286

    
287
void writeBetweennessCentrality(Graph &g, std::vector<double> v_centrality_vec, string fileSuffix) {
288
    string filePath = "../output/boost_" + fileSuffix + ".csv";
289
    cout << "Writing to File " << filePath << endl;
290
    ofstream outFile(filePath);
291

    
292
    // Reading to vector<graphDataType>
293
    Viter vi, ve;
294
    size_t i = 0;
295
    if (outFile.is_open()) {
296
        for(boost::tie(vi, ve) = boost::vertices(g); vi != ve; ++vi) {
297
            outFile << g[*vi].id << ", " << v_centrality_vec.at(i) << endl;
298
            ++i;
299
        }
300
    }
301
    outFile.close();
302
}
303

    
304
template<typename Graph, typename CentralityVec>
305
void printCentrality(Graph g, CentralityVec v_centrality_vec) {
306
    size_t i = 0;
307

    
308
    typename Graph::vertex_iterator v_iter, v_iter_end;
309

    
310
    for(boost::tie(v_iter,v_iter_end) = boost::vertices(g); v_iter != v_iter_end; ++v_iter){
311
        cout << g[*v_iter].id << "\t" << v_centrality_vec.at(i) << endl;
312
        ++i;
313
    }
314
}
315

    
316
void simpleBetweennessCentrality(Graph g, string fileSuffix) {
317
    // One way to create centrality_map
318
    //    boost::shared_array_property_map<double, boost::property_map<Graph, vertex_index_t>::const_type>
319
    //            centrality_map(num_vertices(g), get(boost::vertex_index, g));
320

    
321

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

    
333

    
334
    // Nov 20, 2015
335
    // http://stackoverflow.com/questions/15432104/how-to-create-a-propertymap-for-a-boost-graph-using-lists-as-vertex-container
336
    typedef std::map<Vertex, size_t> StdVertexIndexMap;
337
    StdVertexIndexMap idxMap;
338

    
339
    // 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.
340
    typedef boost::associative_property_map<StdVertexIndexMap> VertexIndexMap;
341
    VertexIndexMap v_index(idxMap);
342

    
343
    // Populate the indexMap
344
    Viter v_iter, v_iter_end;
345
    size_t i = 0;
346
    for (boost::tie(v_iter, v_iter_end) = boost::vertices(g); v_iter != v_iter_end; ++v_iter) {
347
        boost::put(v_index, *v_iter, i);
348
        ++i;
349
    }
350

    
351
    typedef std::vector<double> CentralityVec;
352
    CentralityVec v_centrality_vec(boost::num_vertices(g), 0);
353

    
354
    typedef boost::iterator_property_map< CentralityVec::iterator, VertexIndexMap > CentralityMap;
355
    CentralityMap v_centrality_map(v_centrality_vec.begin(), v_index);
356

    
357
    // http://stackoverflow.com/questions/30263594/adding-a-vertex-index-to-lists-graph-on-the-fly-for-betweenness-centrality
358
    // Use named-parameter
359
    brandes_betweenness_centrality( g, boost::centrality_map(v_centrality_map).vertex_index_map(v_index));
360

    
361
    // ATTENTION: calling the relative_betweenness_centrality in the normal way
362
    // DO NOT USE the named-parameter
363
    relative_betweenness_centrality( g, v_centrality_map);
364

    
365

    
366
    // Print result of v_centrality_map to console
367
    // Uncomment to see the result in the console.
368
    // printCentrality(g, v_centrality_vec);
369

    
370
    // Write result of v_centrality_map to file.
371
    writeBetweennessCentrality(g, v_centrality_vec, fileSuffix);
372
}
373

    
374
void handleSimpleInput(string filePath) {
375
    // Read the input.edges
376
    vector<graphDataType> contents;
377
    contents = readFile2(filePath);
378
    // printVector2(contents);
379
    Graph g;
380
    createUndirectedGraph(contents, g);
381

    
382
    simpleBetweennessCentrality(g, "edge_list");
383
}
384

    
385
void handleJsonInput(string filePath) {
386
    Graph g;
387
    readJson(filePath, g);
388
    // printGraph(g);
389

    
390
    // Applying the betweenness centrality
391
    simpleBetweennessCentrality(g, "json_olsr");
392
}
393

    
394
void handleComplexJsonInput(string filePath) {
395
    Graph g;
396
    readComplexJson(filePath, g);
397
    // printGraph(g);
398

    
399
    // Applying the betweenness centrality
400
    simpleBetweennessCentrality(g, "json_topology");
401
}
402

    
403

    
404
int main(int, char *[]) {
405
    string edgeFilePath = "../input/ninux_30_1.edges";
406
    handleSimpleInput(edgeFilePath);
407

    
408
    string jsonFilePath = "../input/olsr-netjson.json";
409
    handleJsonInput(jsonFilePath);
410

    
411
    string complexJsonFilePath = "../input/jsoninfo_topo.json";
412
    handleComplexJsonInput(complexJsonFilePath);
413

    
414
    return 0;
415
}