gml.hh 16.3 KB
Newer Older
1
2
// graph-tool -- a general graph modification and manipulation thingy
//
Tiago Peixoto's avatar
Tiago Peixoto committed
3
// Copyright (C) 2006-2018 Tiago de Paula Peixoto <tiago@skewed.de>
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 3
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program. If not, see <http://www.gnu.org/licenses/>.

#ifndef GML_HH
#define GML_HH

21
22
23
24
25
26
27
28
#include <boost/config/warning_disable.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix_core.hpp>
#include <boost/spirit/include/phoenix_operator.hpp>
#include <boost/spirit/include/phoenix_fusion.hpp>
#include <boost/spirit/include/phoenix_stl.hpp>
#include <boost/fusion/include/adapt_struct.hpp>
#include <boost/variant/recursive_variant.hpp>
29
#include <boost/variant/get.hpp>
30
31
32
33
#include <boost/spirit/include/support_istream_iterator.hpp>
#include <boost/foreach.hpp>
#include <boost/type_traits.hpp>

34
35
36
37
38
39
40
41
42
43
#include <boost/algorithm/string/replace.hpp>

#include <boost/property_map/dynamic_property_map.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/bind/bind.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>

#include <boost/python.hpp>

44
45
46
47
48
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

Tiago Peixoto's avatar
Tiago Peixoto committed
49
#include <unordered_map>
50

51
52
#include "base64.hh"

53
54
55
56
57
58
59
60
61
62
namespace graph_tool{

using namespace std;
using namespace boost;

class gml_parse_error: public std::exception
{
public:
    gml_parse_error(const string& w): _what(w) {}
    ~gml_parse_error() throw() {}
63
    virtual const char* what() const throw() {return _what.c_str();}
64

65
66
67
68
private:
    std::string _what;
};

69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
struct to_dict_visitor: public boost::static_visitor<>
{
    to_dict_visitor(const std::string& key, boost::python::dict& dict)
        : key(key), dict(dict) {}

    template <class Val>
    void operator()(Val& val) const
    {
        const_cast<boost::python::dict&>(dict)[key] = val;
    }

    template <class Val>
    void operator()(std::unordered_map<std::string, Val>& val) const
    {
        boost::python::dict n_dict;
        for (auto& kv : val)
            boost::apply_visitor(to_dict_visitor(kv.first, n_dict), kv.second);
        const_cast<boost::python::dict&>(dict)[key] = n_dict;
    }

    const std::string& key;
    const boost::python::dict& dict;
};

template <class Desc>
struct prop_val_visitor: public boost::static_visitor<>
{
    prop_val_visitor(const std::string& name, dynamic_properties& dp, Desc v)
        : name(name), dp(dp), v(v) {}

    template <class Val>
    void operator()(Val& val) const
    {
        put(name, const_cast<dynamic_properties&>(dp), v, val);
    }

    template <class Val>
    void operator()(std::unordered_map<std::string, Val>& val) const
    {
        boost::python::dict dict;
        for (auto& kv : val)
            boost::apply_visitor(to_dict_visitor(kv.first, dict), kv.second);
        put(name, const_cast<dynamic_properties&>(dp), v,
            boost::python::object(dict));
    }

    const std::string& name;
    const dynamic_properties& dp;
    Desc v;
};

120
121
122
123
124

template <class Graph>
class gml_state
{
public:
125
    gml_state(Graph& g, dynamic_properties& dp,
126
127
128
              const std::unordered_set<std::string>& ignore_vp = std::unordered_set<std::string>(),
              const std::unordered_set<std::string>& ignore_ep = std::unordered_set<std::string>(),
              const std::unordered_set<std::string>& ignore_gp = std::unordered_set<std::string>())
129
130
        : _g(g), _dp(dp), _directed(false), _ignore_vp(ignore_vp),
          _ignore_ep(ignore_ep), _ignore_gp(ignore_gp) {}
131

132
133
134
135
    typedef boost::make_recursive_variant<std::string, int, double,
                                          std::unordered_map<std::string,
                                                             boost::recursive_variant_>>
        ::type val_t;
136

137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
    // key / value mechanics
    void push_key(const std::string& key)
    {
        _stack.push_back(make_pair(key, prop_list_t()));
    }

    void push_value(const val_t& value)
    {
        if (_stack.empty())
            return;
        std::string k = _stack.back().first;
        _stack.pop_back();
        if (!_stack.empty())
            _stack.back().second[k] = value;
    }

    // actual parsing
    void finish_list()
    {
        if (_stack.empty())
            return;

        std::string &k = _stack.back().first;
        if (k == "node")
        {
            int id;
            if (_stack.back().second.find("id") == _stack.back().second.end())
                throw gml_parse_error("node does not have an id");
            try
            {
167
                id = boost::get<double>(_stack.back().second["id"]);
168
169
170
            }
            catch (bad_get)
            {
171
                throw gml_parse_error("invalid node id");
172
173
            }

174
175
            typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
            vertex_t v = get_vertex(id);
176
177

            // put properties
178
            for (auto& iter : _stack.back().second)
179
            {
180
                if (iter.first == "id")
181
                    continue;
182
                if (_ignore_vp.find(iter.first) != _ignore_vp.end())
183
                    continue;
184
185
                boost::apply_visitor(prop_val_visitor<vertex_t>(iter.first, _dp, v),
                                     iter.second);
186
187
188
189
190
191
192
193
194
195
196
197
            }
        }
        else if (k == "edge")
        {
            int source, target;
            if (_stack.back().second.find("source") ==
                _stack.back().second.end() ||
                _stack.back().second.find("target") ==
                _stack.back().second.end())
                throw gml_parse_error("edge does not have source and target ids");
            try
            {
198
199
                source = boost::get<double>(_stack.back().second["source"]);
                target = boost::get<double>(_stack.back().second["target"]);
200
201
202
203
204
205
206
207
208
209
            }
            catch (bad_get)
            {
                throw gml_parse_error("invalid source and target ids");
            }

            typename graph_traits<Graph>::vertex_descriptor s, t;
            s = get_vertex(source);
            t = get_vertex(target);

210
211
            typedef typename graph_traits<Graph>::edge_descriptor edge_t;
            edge_t e = add_edge(s, t, _g).first;
212
213

            // put properties
214
            for (auto& iter : _stack.back().second)
215
            {
216
                if (iter.first == "id" || iter.first == "source" || iter.first == "target")
217
                    continue;
218
                if (_ignore_ep.find(iter.first) != _ignore_ep.end())
219
                    continue;
220
221
                boost::apply_visitor(prop_val_visitor<edge_t>(iter.first, _dp, e),
                                     iter.second);
222
            }
223

224
225
226
227
        }
        else if (k == "graph")
        {
            // put properties
228
            for (auto& iter : _stack.back().second)
229
            {
230
231
232
                if (iter.first == "directed")
                    _directed = boost::get<double>(iter.second);
                if (_ignore_gp.find(iter.first) != _ignore_gp.end())
233
                    continue;
234
235
236
                boost::apply_visitor(prop_val_visitor<graph_property_tag>(iter.first, _dp,
                                                                          graph_property_tag()),
                                     iter.second);
237
            }
238

239
        }
240
241
242
243
        else
        {
            // Push nested lists down the stack
            if (_stack.size() < 2)
244
245
246
247
248
249
250
251
            {
                if (k != "comments")
                    throw gml_parse_error("invalid syntax: list '" + k + "' not within 'node', 'edge' or 'graph'");
            }
            else
            {
                _stack[_stack.size() - 2].second[k] = _stack.back().second;
            }
252
        }
253
254
255
256
257
258
259
260
261
262
        _stack.pop_back();
    }

    typename graph_traits<Graph>::vertex_descriptor get_vertex(size_t index)
    {
        if (_vmap.find(index) == _vmap.end())
            _vmap[index] = add_vertex(_g);
        return _vmap[index];
    }

263
264

    bool is_directed()
265
266
267
    {
        return _directed;
    }
268

269
270
271
272
273

private:
    Graph& _g;
    dynamic_properties& _dp;
    bool _directed;
Tiago Peixoto's avatar
Tiago Peixoto committed
274
    std::unordered_map<int, typename graph_traits<Graph>::vertex_descriptor> _vmap;
275

276
    // the stack holds the keys, and its properties
Tiago Peixoto's avatar
Tiago Peixoto committed
277
    typedef std::unordered_map<std::string, val_t> prop_list_t;
278
    vector<pair<std::string,  prop_list_t> > _stack;
279

280
281
282
    const std::unordered_set<std::string>& _ignore_vp;
    const std::unordered_set<std::string>& _ignore_ep;
    const std::unordered_set<std::string>& _ignore_gp;
283
284
285
286
287
288
};


template <class Iterator, class Graph, class Skipper>
struct gml : spirit::qi::grammar<Iterator, void(), Skipper>
{
289
    gml(Graph& g, dynamic_properties& dp,
290
291
292
        const std::unordered_set<std::string>& ignore_vp = std::unordered_set<std::string>(),
        const std::unordered_set<std::string>& ignore_ep = std::unordered_set<std::string>(),
        const std::unordered_set<std::string>& ignore_gp = std::unordered_set<std::string>())
293
        : gml::base_type(start), _state(g, dp, ignore_vp, ignore_ep, ignore_gp)
294
295
296
297
    {
        using namespace spirit;
        using spirit::ascii::char_;

298
299
        unesc_str = spirit::lexeme['"' >> *(unesc_char | (spirit::qi::graph - "\"") |
                                            spirit::qi::space | "\\x" >> qi::hex) >> '"'];
300
301
302
        unesc_char.add("\\a", '\a')("\\b", '\b')("\\f", '\f')("\\n", '\n')
            ("\\r", '\r')("\\t", '\t')("\\v", '\v')("\\\\", '\\')
            ("\\\'", '\'')("\\\"", '\"');
303
        key_identifier %= spirit::lexeme[((+((spirit::qi::alnum | "_") | "-")) >> *spirit::qi::alnum)];
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
        key = key_identifier
            [boost::bind(&gml_state<Graph>::push_key, &_state, ::_1)];
        value_identifier %= (spirit::lexeme[spirit::qi::double_] | unesc_str);
        value %= value_identifier
            [boost::bind(&gml_state<Graph>::push_value, &_state, ::_1)];
        list_identifier = *(key >> (value | "[" >> list >> "]"));
        list = list_identifier
            [boost::bind(&gml_state<Graph>::finish_list, &_state)];
        start = list;
    }

    typedef boost::variant<std::string, double> val_t;

    spirit::qi::rule<Iterator, std::string(), Skipper> unesc_str;
    spirit::qi::symbols<char const, char const> unesc_char;
    spirit::qi::rule<Iterator, std::string(), Skipper> key, key_identifier;
    spirit::qi::rule<Iterator, val_t(), Skipper> value, value_identifier;
    spirit::qi::rule<Iterator, void(), Skipper> list, list_identifier;
    spirit::qi::rule<Iterator, void(), Skipper> start;
323

324
325
326
327
328
    gml_state<Graph> _state;
};

template <class Iterator, class Graph, class Skipper>
bool parse_grammar(Iterator begin, Iterator end, Graph& g,
329
                   dynamic_properties& dp, Skipper skip,
330
331
332
                   const std::unordered_set<std::string>& ignore_vp = std::unordered_set<std::string>(),
                   const std::unordered_set<std::string>& ignore_ep = std::unordered_set<std::string>(),
                   const std::unordered_set<std::string>& ignore_gp = std::unordered_set<std::string>())
333
334
{
    using namespace spirit;
335
336
    gml<spirit::istream_iterator, Graph, Skipper> parser(g, dp, ignore_vp,
                                                         ignore_ep, ignore_gp);
337
338
339
340
341
342
343
344
    bool ok = qi::phrase_parse(begin, end, parser, skip);
    if (!ok)
        throw gml_parse_error("invalid syntax");
    return parser._state.is_directed();
}


template <class Graph>
345
bool read_gml(istream& in, Graph& g, dynamic_properties& dp,
346
347
348
              const std::unordered_set<std::string>& ignore_vp = std::unordered_set<std::string>(),
              const std::unordered_set<std::string>& ignore_ep = std::unordered_set<std::string>(),
              const std::unordered_set<std::string>& ignore_gp = std::unordered_set<std::string>())
349
350
351
352
353
354
355
356
357
{
    using namespace spirit;

    in >> std::noskipws;
    spirit::istream_iterator begin(in);
    spirit::istream_iterator end;

    bool directed =
        parse_grammar(begin, end, g, dp,
358
359
                      (ascii::space |'#' >> *(ascii::char_ - qi::eol) >> qi::eol),
                      ignore_vp, ignore_ep, ignore_gp);
360
361
362
363
364
365
366
367
368

    return directed;
}

struct get_str
{
    template <typename ValueType>
    void operator()(const boost::any& val, std::string& sval, ValueType) const
    {
369
        try
370
371
        {
            ValueType v = any_cast<ValueType>(val);
Tiago Peixoto's avatar
Tiago Peixoto committed
372
            if (std::is_same<ValueType, python::object>::value)
373
            {
374
                sval = base64_encode(lexical_cast<string>(v));
375
376
377
378
379
380
381
382
            }
            else
            {
                stringstream s;
                s << v;
                sval = s.str();
            }

Tiago Peixoto's avatar
Tiago Peixoto committed
383
            if (!std::is_scalar<ValueType>::value)
384
385
386
            {
                replace_all(sval, "\"", "\\\"");
                sval = "\"" + sval + "\"";
387
            }
388
        }
389
        catch (bad_any_cast&)
390
391
392
393
394
395
396
397
398
399
        {
        }
    }
};

template <typename ValueTypes, typename Descriptor>
std::string print_val(dynamic_property_map& pmap, const Descriptor& v)
{
    std::string val;
    boost::any oval = pmap.get(v);
Tiago Peixoto's avatar
Tiago Peixoto committed
400
401
    mpl::for_each<ValueTypes>(bind<void>(get_str(), boost::ref(oval),
                                         boost::ref(val), _1));
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
    return val;
}


template <typename Graph, typename VertexIndexMap>
void write_gml(std::ostream& out, const Graph& g, VertexIndexMap vertex_index,
               const dynamic_properties& dp)
{
    typedef typename graph_traits<Graph>::directed_category directed_category;
    typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
    typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;

    typedef mpl::vector<bool, uint8_t, int8_t, uint32_t, int32_t,
                        uint64_t, int64_t, float, double, long double,
                        std::vector<uint8_t>, std::vector<int32_t>,
                        std::vector<int64_t>, std::vector<double>,
                        std::vector<long double>, std::vector<std::string>,
                        std::string, python::object> value_types;

    BOOST_STATIC_CONSTANT(bool, graph_is_directed =
Tiago Peixoto's avatar
Tiago Peixoto committed
422
423
                          (std::is_convertible<directed_category*,
                                               directed_tag*>::value));
424
425
426
427
428
429

    out << "graph [" << endl;

    if (graph_is_directed)
        out << "   directed " << 1 << endl;

430
    for (auto& i : dp)
431
    {
432
        if (i.second->key() == typeid(graph_property_tag))
433
        {
434
            std::string val = print_val<value_types>(*i.second,
435
436
437
                                                     graph_property_tag());
            if (val.empty())
                continue;
438
            out << "   " << i.first << " " << val << endl;
439
440
441
        }
    }

442
    for (auto v : vertices_range(g))
443
444
    {
        out << "   node [" << endl;
445
        out << "      id " << get(vertex_index, v) << endl;
446

447
        for (auto& i : dp)
448
        {
449
            if (i.second->key() == typeid(vertex_descriptor))
450
            {
451
                std::string val = print_val<value_types>(*i.second, v);
452
453
                if (val.empty())
                    continue;
454
                out << "      " << i.first << " " << val << endl;
455
456
457
458
459
460
            }
        }
        out << "   ]" << endl;
    }

    typename graph_traits<Graph>::edges_size_type edge_count = 0;
461
    for (auto e : edges_range(g))
462
463
464
    {
        out << "   edge [" << endl;
        out << "      id " << edge_count++ << endl;
465
466
        out << "      source " << get(vertex_index, source(e, g)) << endl;
        out << "      target " << get(vertex_index, target(e, g)) << endl;
467

468
        for (auto& i : dp)
469
        {
470
            if (i.second->key() == typeid(edge_descriptor))
471
            {
472
                std::string val = print_val<value_types>(*i.second, e);
473
474
                if (val.empty())
                    continue;
475
                out << "      " << i.first << " " << val << endl;
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
            }
        }
        out << "   ]" << endl;
    }
    out << "]" << endl;
}


template <typename Graph>
void write_gml(std::ostream& out, const Graph& g, const dynamic_properties& dp)
{
    write_gml(out, g, get(vertex_index, g), dp);
}

} // namespace graph_tool
491
492

#endif // GML_HH