Statistics
| Branch: | Revision:

root / custompackages / graph-parser / src / main.cpp @ af008982

History | View | Annotate | Download (10.7 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 printVector1(vector<vector<string>> contents) {
144
    vector<vector<string>>::iterator i;
145
    vector<string>::iterator j;
146

    
147
    int count = 0;
148
    for (i = contents.begin(); i != contents.end(); ++i) {
149
        for (j = (*i).begin(); j != (*i).end(); ++j) {
150
            cout << *j << endl;
151
        }
152
        cout << endl;
153
    }
154
}
155

    
156
void printVector2(vector<graphDataType> contents) {
157
    vector<graphDataType>::iterator i;
158
    int count = 0;
159
    for (i = contents.begin(); i != contents.end(); ++i) {
160
        unsigned long size = (*i).size();
161
//        cout << "size = " << size << endl;
162
//        cout << "&i = " << &i << endl;
163
        for (int j = 0; j < size; ++j) {
164
            cout << (*i)[j] << endl;
165
        }
166
        cout << endl;
167
    }
168
}
169

    
170

    
171
Vertex findRouter(string id, Graph g) {
172
    typedef pair<Viter, Viter> ViterPair;
173
    ViterPair vs = boost::vertices(g); // return the pointer at the beginning and at the end of the range.
174
    cout << &vs.first << "  ***  " << &vs.second << endl;
175
    Viter vit = vs.first;
176
    for (vit; vit != vs.second; ++vit) {
177
        cout << "+++ " << g[*vit].id << endl;
178
        cout << &vit << endl;
179
        cout << "Found " << id << endl;
180
        if (g[*vit].id == id) {
181

    
182
            return (*vit);
183
        }
184
    }
185
    cout << "Not Found " << id << endl;
186
    return NULL;
187
}
188

    
189
void createUndirectedGraph(vector<graphDataType> contents, Graph &g) {
190
    /*
191
     * Check the BGL Tutorial, pg. 64
192
    */
193
    Vertex v1, v2;
194
    Edge e;
195

    
196
    // NameVertexMap is to keep track of which router has already been added
197
    typedef std::map<std::string, Vertex> NameVertexMap;
198
    NameVertexMap routers;
199
    NameVertexMap::iterator pos;
200
    bool inserted;
201

    
202
    vector<graphDataType>::iterator iter;
203
    for (iter = contents.begin(); iter != contents.end(); ++iter) {
204
        // Get the id of 2 vertices (routers), and add them to graph
205
        if ((*iter).size() != 3) {
206
            cout << "XXX" << endl;
207
            continue;
208
        }
209
        string s1 = (*iter)[0];
210
        string s2 = (*iter)[1];
211
        float cost = std::stof((*iter)[2]);
212

    
213
        cout << s1 << " " << s2 << " " << cost << endl;
214

    
215
        boost::tie(pos, inserted) = routers.insert(std::make_pair(s1, Vertex()));
216
        if (inserted) {
217
//            cout << "Added vertex " << s1 << endl;
218
            v1 = boost::add_vertex(g);
219
            routers[s1] = v1;
220
            pos->second = v1;
221

    
222
            //Update the id and name
223
            g[v1].id = s1;
224
            g[v1].name = s1;
225
        } else {
226
//            cout << "Found vertex " << s1 << endl;
227
            v1 = pos->second;
228
        }
229

    
230
        boost::tie(pos, inserted) = routers.insert(std::make_pair(s2, Vertex()));
231
        if (inserted) {
232
//            cout << "Added vertex " << s2 << endl;
233
            v2 = boost::add_vertex(g);
234
            routers[s2] = v2;
235
            pos->second = v2;
236
            g[v2].id = s2;
237
            g[v2].name = s2;
238
        } else {
239
//            cout << "Found vertex " << s2 << endl;
240
            v2 = pos->second;
241
        }
242

    
243
        // Add edge (aka. link) connecting 2 vertices
244
        boost::tie(e, inserted) = boost::add_edge(v1, v2, g);
245
        if (inserted) {
246
            cout << "Added edge with weight " << cost << endl;
247
            g[e].cost = cost;
248
        }
249
    }
250
}
251

    
252
void printGraph(Graph g) {
253
    typename boost::graph_traits<Graph>::out_edge_iterator out_i, out_ie;
254
    Viter v_i, v_ie;
255

    
256
    Vertex v;
257
    Edge e;
258

    
259
    boost::tie(v_i, v_ie) = boost::vertices(g);
260
    for (v_i; v_i != v_ie; ++v_i) {
261
        v = *v_i;
262
        boost::tie(out_i, out_ie) = boost::out_edges(v, g);
263

    
264
        for (out_i; out_i != out_ie; ++out_i) {
265
            e = *out_i;
266
            Vertex src = boost::source(e, g);
267
            Vertex targ = boost::target(e, g);
268
            std::cout << "(" << g[src].id << ","
269
            << g[targ].id << ") ";
270
        }
271
        cout << endl;
272
    }
273
}
274

    
275
void handleSimpleInput(string filePath) {
276
    // Read the input.edges
277
    vector<graphDataType> contents;
278
    contents = readFile2(filePath);
279
    printVector2(contents);
280
    Graph g;
281
    createUndirectedGraph(contents, g);
282
    cout << "Finish creating graph" << endl;
283
    printGraph(g);
284
}
285

    
286

    
287
void simpleBetweennessCentrality(Graph g) {
288
    // One way to create centrality_map
289
    //    boost::shared_array_property_map<double, boost::property_map<Graph, vertex_index_t>::const_type>
290
    //            centrality_map(num_vertices(g), get(boost::vertex_index, g));
291

    
292

    
293
    // Define VertexCentralityMap
294
//    typedef boost::property_map< Graph, boost::vertex_index_t>::type VertexIndexMap;
295
//    VertexIndexMap v_index = get(boost::vertex_index, g);
296
//    // Constructs a container with n elements. Each element is a copy of val.
297
//    std::vector< double > v_centrality_vec(boost::num_vertices(g), 0.0);
298
//    // Create the external property map
299
//    boost::iterator_property_map< std::vector< double >::iterator, VertexIndexMap >
300
//            v_centrality_map(v_centrality_vec.begin(), v_index);
301
//
302
//    brandes_betweenness_centrality( g, v_centrality_map);
303

    
304

    
305
    // Nov 20, 2015
306
    // http://stackoverflow.com/questions/15432104/how-to-create-a-propertymap-for-a-boost-graph-using-lists-as-vertex-container
307
    typedef std::map<Vertex, size_t> StdVertexIndexMap;
308
    StdVertexIndexMap idxMap;
309

    
310
    // 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.
311
    typedef boost::associative_property_map<StdVertexIndexMap> VertexIndexMap;
312
    VertexIndexMap v_index(idxMap);
313

    
314
    // Populate the indexMap
315
    Viter v_iter, v_iter_end;
316
    size_t i = 0;
317
    for (boost::tie(v_iter, v_iter_end) = boost::vertices(g); v_iter != v_iter_end; ++v_iter) {
318
        boost::put(v_index, *v_iter, i);
319
        ++i;
320
    }
321

    
322
    std::vector<double> v_centrality_vec(boost::num_vertices(g), 0);
323
    boost::iterator_property_map< std::vector< double >::iterator, VertexIndexMap >
324
            v_centrality_map(v_centrality_vec.begin(), v_index);
325

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

    
331
    // Print result of v_centrality_map
332

    
333
    cout << "Vertex betweenness" << endl;
334
    i = 0;
335
    for(boost::tie(v_iter,v_iter_end) = boost::vertices(g); v_iter != v_iter_end; ++v_iter){
336
        cout << g[*v_iter].id << "\t" << v_centrality_vec.at(i) << endl;
337
        ++i;
338
    }
339

    
340
}
341

    
342
void handleJsonInput(string filePath) {
343
    Graph g;
344
    readJson(filePath, g);
345
    printGraph(g);
346

    
347
    // Applying the betweenness centrality
348
    simpleBetweennessCentrality(g);
349

    
350
    cout << "Done with Betweenness Centrality" << endl;
351
}
352

    
353
int main(int, char *[]) {
354
    string edgeFilePath = "../input/ninux_30_1.edges";
355
    //handleSimpleInput(edgeFilePath);
356

    
357
    string jsonFilePath = "../input/olsr-netjson.json";
358
    handleJsonInput(jsonFilePath);
359
    return 0;
360
}