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