graph_io.cc 21 KB
Newer Older
Tiago Peixoto's avatar
Tiago Peixoto committed
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>
Tiago Peixoto's avatar
Tiago Peixoto committed
4 5 6
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
Tiago Peixoto's avatar
Tiago Peixoto committed
7
// as published by the Free Software Foundation; either version 3
Tiago Peixoto's avatar
Tiago Peixoto committed
8 9 10 11 12 13 14 15
// 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
16 17
// along with this program. If not, see <http://www.gnu.org/licenses/>.

18 19
#include <boost/python/extract.hpp>

20
#include <iostream>
21
#include <boost/iostreams/categories.hpp>
22 23 24
#include <boost/iostreams/filtering_stream.hpp>
#include <boost/iostreams/filter/gzip.hpp>
#include <boost/iostreams/filter/bzip2.hpp>
25
#include <boost/iostreams/device/file_descriptor.hpp>
26
#include <boost/iostreams/device/file.hpp>
27 28
#include <boost/graph/graphml.hpp>
#include <boost/lexical_cast.hpp>
Tiago Peixoto's avatar
Tiago Peixoto committed
29
#include <boost/xpressive/xpressive.hpp>
Tiago Peixoto's avatar
Tiago Peixoto committed
30

31 32 33 34 35
#include "graph.hh"
#include "graph_filtering.hh"
#include "graph_properties.hh"
#include "graph_util.hh"

36
#include "graph_python_interface.hh"
Tiago Peixoto's avatar
Tiago Peixoto committed
37
#include "str_repr.hh"
38

Tiago Peixoto's avatar
Tiago Peixoto committed
39 40
#include "gml.hh"

Tiago Peixoto's avatar
Tiago Peixoto committed
41 42 43 44
using namespace std;
using namespace boost;
using namespace graph_tool;

45
// use correct smart pointer type for dynamic properties
46
#if (BOOST_VERSION / 100 % 1000 >= 44)
47 48 49 50 51
    #define DP_SMART_PTR boost::shared_ptr
#else
    #define DP_SMART_PTR std::auto_ptr
#endif

52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80
//
// Persistent IO of python::object types. All the magic is done in python,
// through the object_pickler and object_unplickler below
//

namespace graph_tool
{
python::object object_pickler;
python::object object_unpickler;
}

namespace boost
{
template <>
string lexical_cast<string,python::object>(const python::object & o)
{
    stringstream s;
    object_pickler(OStream(s), o);
    return s.str();
}

template <>
python::object lexical_cast<python::object,string>(const string& ps)
{
    stringstream s(ps);
    python::object o;
    o = object_unpickler(IStream(s));
    return o;
}
81 82 83 84 85 86 87 88 89

namespace python
{
std::ostringstream& operator<<(std::ostringstream& stream, const boost::python::object& o)
{
    stream << base64_encode(lexical_cast<string>(o));
    return stream;
}
}
90 91
}

92 93
#include <boost/graph/graphviz.hpp>

94 95
#include "graph_io_binary.hh"

96 97 98 99 100 101 102 103 104
// the following source & sink provide iostream access to python file-like
// objects

class python_file_device
{
public:
    typedef char                 char_type;
    typedef iostreams::seekable_device_tag  category;

Tiago Peixoto's avatar
Tiago Peixoto committed
105
    python_file_device(boost::python::object file): _file(file) {}
106 107
    std::streamsize read(char* s, std::streamsize n)
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
108 109
        boost::python::object pbuf = _file.attr("read")(n);
        string buf = boost::python::extract<string>(pbuf);
110 111 112 113 114 115 116 117
        for (size_t i = 0; i < buf.size(); ++i)
            s[i] = buf[i];
        return buf.size();
    }

    std::streamsize write(const char* s, std::streamsize n)
    {
        string buf(s, s+n);
118 119 120 121 122 123 124 125 126
#if (PY_MAJOR_VERSION >= 3)
        // in python 3 we need to construct a 'bytes' instance
        PyObject* bytes = PyBytes_FromStringAndSize(s, n);
        boost::python::handle<> x(bytes);
        boost::python::object pbuf(x);
#else
        boost::python::str pbuf(buf);
#endif
        _file.attr("write")(pbuf);
127 128 129 130 131 132 133
        return n;
    }

    iostreams::stream_offset seek(iostreams::stream_offset off,
                                  std::ios_base::seekdir way)
    {
        _file.attr("seek")(off, int(way));
Tiago Peixoto's avatar
Tiago Peixoto committed
134
        return boost::python::extract<iostreams::stream_offset>(_file.attr("tell")());
135 136 137
    }

private:
Tiago Peixoto's avatar
Tiago Peixoto committed
138
    boost::python::object _file;
139
};
140

141 142 143 144 145 146
// Property Maps
// =============

struct get_python_property
{
    template <class ValueType, class IndexMap>
147
    void operator()(ValueType, IndexMap, dynamic_property_map& map,
Tiago Peixoto's avatar
Tiago Peixoto committed
148
                    boost::python::object& pmap) const
149
    {
150 151
        typedef typename property_map_type::apply<ValueType, IndexMap>::type
            map_t;
152 153
        try
        {
Tiago Peixoto's avatar
Tiago Peixoto committed
154
            pmap = boost::python::object
155 156
                (PythonPropertyMap<map_t>
                 (dynamic_cast
157
                  <boost::detail::dynamic_property_map_adaptor<map_t>&>(map)
158 159 160
                  .base()));
        } catch (bad_cast&) {}
    }
161 162 163 164 165 166 167 168 169 170 171 172 173 174 175

    template <class ValueType, class IndexMap>
    void operator()(ValueType, IndexMap, boost::any& map,
                    boost::python::object& pmap) const
    {
        typedef typename property_map_type::apply<ValueType, IndexMap>::type
            map_t;
        try
        {
            PythonPropertyMap<map_t> opmap(any_cast<map_t>(map));
            pmap = boost::python::object(opmap);
        }
        catch (bad_any_cast&) {}
    }

176 177 178
};

template <class IndexMap>
Tiago Peixoto's avatar
Tiago Peixoto committed
179
boost::python::object find_property_map(dynamic_property_map& map, IndexMap)
180
{
Tiago Peixoto's avatar
Tiago Peixoto committed
181 182 183 184
    boost::python::object pmap;
    boost::mpl::for_each<value_types>(std::bind(get_python_property(),
                                                std::placeholders::_1, IndexMap(), std::ref(map),
                                                std::ref(pmap)));
185 186 187
    return pmap;
}

188 189 190 191 192 193 194 195 196 197
template <class IndexMap>
boost::python::object find_property_map(boost::any& map, IndexMap)
{
    boost::python::object pmap;
    boost::mpl::for_each<value_types>(std::bind(get_python_property(),
                                                std::placeholders::_1, IndexMap(), std::ref(map),
                                                std::ref(pmap)));
    return pmap;
}

198
// this functor will check whether a value is of a specific type, create a
Tiago Peixoto's avatar
Tiago Peixoto committed
199
// corresponding vector_property_map and add the value to it
200

Tiago Peixoto's avatar
Tiago Peixoto committed
201 202 203 204
template <class IndexMap>
struct check_value_type
{
    typedef typename IndexMap::key_type key_t;
205 206
    check_value_type(IndexMap index_map, const key_t& key,
                     const boost::any& value, dynamic_property_map*& map)
207
        :_index_map(index_map), _key(key), _value(value), _map(map) {}
Tiago Peixoto's avatar
Tiago Peixoto committed
208 209 210 211

    template <class ValueType>
    void operator()(ValueType)
    {
212 213
        try
        {
214 215 216
            typedef typename property_map_type::apply<ValueType, IndexMap>::type
                map_t;
            map_t vector_map(_index_map);
217
            vector_map[_key] = any_cast<ValueType>(_value);
218 219
            _map = new boost::detail::dynamic_property_map_adaptor<map_t>
                (vector_map);
220
        }
221
        catch (bad_any_cast&) {}
Tiago Peixoto's avatar
Tiago Peixoto committed
222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237
    }
    IndexMap _index_map;
    const key_t& _key;
    const boost::any& _value;
    dynamic_property_map*& _map;
};

// this functor will check wether a key is a vertex or edge descriptor, and
// generate the corresponding property map, depending on the value type

template <class VertexIndexMap, class EdgeIndexMap>
struct create_dynamic_map
{
    typedef typename VertexIndexMap::key_type vertex_t;
    typedef typename EdgeIndexMap::key_type edge_t;

238 239
    create_dynamic_map(VertexIndexMap vertex_map, EdgeIndexMap edge_map)
        :_vertex_map(vertex_map), _edge_map(edge_map) {}
240
    DP_SMART_PTR<dynamic_property_map> operator()(const string&,
241 242
                                                  const boost::any& key,
                                                  const boost::any& value)
Tiago Peixoto's avatar
Tiago Peixoto committed
243
    {
244 245 246
        dynamic_property_map* map;
        try
        {
Tiago Peixoto's avatar
Tiago Peixoto committed
247
            boost::mpl::for_each<value_types>
248 249 250
                (check_value_type<VertexIndexMap>(_vertex_map,
                                                  any_cast<vertex_t>(key),
                                                  value, map));
251
        }
252
        catch (bad_any_cast&)
253
        {
254
            try
255
            {
Tiago Peixoto's avatar
Tiago Peixoto committed
256
                boost::mpl::for_each<value_types>
257 258 259
                    (check_value_type<EdgeIndexMap>(_edge_map,
                                                    any_cast<edge_t>(key),
                                                    value, map));
260
            }
261
            catch (bad_any_cast&)
262 263
            {
                ConstantPropertyMap<size_t,graph_property_tag> graph_index(0);
Tiago Peixoto's avatar
Tiago Peixoto committed
264
                boost::mpl::for_each<value_types>
265 266 267 268
                    (check_value_type<ConstantPropertyMap<size_t,
                                                          graph_property_tag> >
                     (graph_index, any_cast<graph_property_tag>(key),
                      value, map));
269
            }
270
        }
271
        return DP_SMART_PTR<dynamic_property_map>(map);
Tiago Peixoto's avatar
Tiago Peixoto committed
272 273 274 275 276 277 278
    }

    VertexIndexMap _vertex_map;
    EdgeIndexMap _edge_map;
};

//==============================================================================
279
// read_from_file(file, pfile, format)
Tiago Peixoto's avatar
Tiago Peixoto committed
280 281
//==============================================================================

282 283 284
void build_stream(boost::iostreams::filtering_stream<boost::iostreams::input>& stream,
                  const string& file, boost::python::object& pfile,
                  std::ifstream& file_stream)
Tiago Peixoto's avatar
Tiago Peixoto committed
285
{
286 287 288 289
    stream.reset();
    if (file == "-")
        stream.push(std::cin);
    else
Tiago Peixoto's avatar
Tiago Peixoto committed
290
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
291
        if (pfile == boost::python::object())
292
        {
293 294
            file_stream.open(file.c_str(), std::ios_base::in |
                             std::ios_base::binary);
295 296
            file_stream.exceptions(ios_base::badbit | ios_base::failbit);
            if (boost::ends_with(file,".gz"))
297
                stream.push(boost::iostreams::gzip_decompressor());
298
            if (boost::ends_with(file,".bz2"))
299
                stream.push(boost::iostreams::bzip2_decompressor());
300 301
            stream.push(file_stream);
        }
302 303 304 305 306 307 308 309 310 311
        else
        {
            python_file_device src(pfile);
            stream.push(src);
        }
    }
    stream.exceptions(ios_base::badbit);
}


312 313 314 315 316 317
boost::python::tuple GraphInterface::read_from_file(string file,
                                                    boost::python::object pfile,
                                                    string format,
                                                    boost::python::list ignore_vp,
                                                    boost::python::list ignore_ep,
                                                    boost::python::list ignore_gp)
318
{
319
    if (format != "gt" && format != "dot" && format != "xml" && format != "gml")
Tiago Peixoto's avatar
Tiago Peixoto committed
320
        throw ValueException("error reading from file '" + file +
321 322 323 324 325 326 327
                             "': requested invalid format '" + format + "'");
    try
    {
        boost::iostreams::filtering_stream<boost::iostreams::input>
            stream;
        std::ifstream file_stream;
        build_stream(stream, file, pfile, file_stream);
328

329
        std::unordered_set<std::string> ivp, iep, igp;
330
        for (int i = 0; i < len(ignore_vp); ++i)
Tiago Peixoto's avatar
Tiago Peixoto committed
331
            ivp.insert(boost::python::extract<string>(ignore_vp[i]));
332
        for (int i = 0; i < len(ignore_ep); ++i)
Tiago Peixoto's avatar
Tiago Peixoto committed
333
            iep.insert(boost::python::extract<string>(ignore_ep[i]));
334
        for (int i = 0; i < len(ignore_gp); ++i)
Tiago Peixoto's avatar
Tiago Peixoto committed
335
            igp.insert(boost::python::extract<string>(ignore_gp[i]));
336

337 338 339
        create_dynamic_map<vertex_index_map_t,edge_index_map_t>
            map_creator(_vertex_index, _edge_index);
        dynamic_properties dp(map_creator);
340
        *_mg = multigraph_t();
341

342
        if (format == "dot")
343
            _directed = read_graphviz(stream, *_mg, dp, "vertex_name", true,
344
                                      ivp, iep, igp);
345
        else if (format == "xml")
346 347
            _directed = read_graphml(stream, *_mg, dp, true, true, true,
                                     ivp, iep, igp);
348
        else if (format == "gml")
349
            _directed = read_gml(stream, *_mg, dp, ivp, iep, igp);
350

351

Tiago Peixoto's avatar
Tiago Peixoto committed
352
        boost::python::dict vprops, eprops, gprops;
353
        if (format == "gt")
354
        {
355
            vector<pair<string, boost::any>> agprops, avprops, aeprops;
356
            stream.exceptions(ios_base::badbit | ios_base::failbit | ios_base::eofbit);
357 358 359 360 361 362 363 364 365 366 367
            _directed = read_graph(stream, *_mg, agprops, avprops, aeprops, igp,
                                   ivp, iep);
            for (auto& p : agprops)
                gprops[p.first] = find_property_map(p.second, _graph_index);
            for (auto& p : avprops)
                vprops[p.first] = find_property_map(p.second, _vertex_index);
            for (auto& p : aeprops)
                eprops[p.first] = find_property_map(p.second, _edge_index);
        }
        else
        {
368
            for(auto iter = dp.begin(); iter != dp.end(); ++iter)
369 370 371 372 373 374 375 376 377 378 379
            {
                if (iter->second->key() == typeid(vertex_t))
                    vprops[iter->first] = find_property_map(*iter->second,
                                                            _vertex_index);
                else if (iter->second->key() == typeid(edge_t))
                    eprops[iter->first] = find_property_map(*iter->second,
                                                            _edge_index);
                else
                    gprops[iter->first] = find_property_map(*iter->second,
                                                            _graph_index);
            }
380
        }
Tiago Peixoto's avatar
Tiago Peixoto committed
381
        return boost::python::make_tuple(vprops, eprops, gprops);
Tiago Peixoto's avatar
Tiago Peixoto committed
382 383 384
    }
    catch (ios_base::failure &e)
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
385
        throw IOException("error reading from file '" + file + "':" + e.what());
Tiago Peixoto's avatar
Tiago Peixoto committed
386
    }
387 388 389 390
    catch (parse_error &e)
    {
        throw IOException("error reading from file '" + file + "':" + e.what());
    }
391 392 393 394
    catch (gml_parse_error &e)
    {
        throw IOException("error reading from file '" + file + "':" + e.what());
    }
Tiago Peixoto's avatar
Tiago Peixoto committed
395 396
};

397 398 399 400 401 402
template <class IndexMap>
string graphviz_insert_index(dynamic_properties& dp, IndexMap index_map,
                             bool insert = true)
{
    typedef GraphInterface::vertex_t vertex_t;
    bool found = false;
403
    for(auto iter = dp.begin(); iter != dp.end(); ++iter)
404 405 406 407 408 409 410 411 412 413 414
        if (iter->first == "vertex_name" &&
            iter->second->key() == typeid(vertex_t))
            found = true;
    if (!found && insert)
        dp.property("vertex_id", index_map);
    if (found)
        return "vertex_name";
    else
        return "vertex_id";
}

415 416
// writes a graph to a file

417
struct do_write_to_file
Tiago Peixoto's avatar
Tiago Peixoto committed
418 419
{
    template <class Graph, class IndexMap>
420
    void operator()(ostream& stream, Graph& g, IndexMap index_map,
421
                    dynamic_properties& dp, const string& format) const
Tiago Peixoto's avatar
Tiago Peixoto committed
422
    {
423
        if (format == "dot")
424
        {
425
            string name = graphviz_insert_index(dp, index_map, false);
426
            write_graphviz(stream, g, dp, name);
427
        }
428
        else if (format == "xml")
429
        {
430
            write_graphml(stream, g, index_map, dp, true);
431
        }
432 433 434 435
        else if (format == "gml")
        {
            write_gml(stream, g, index_map, dp);
        }
Tiago Peixoto's avatar
Tiago Peixoto committed
436 437 438
    }
};

439
struct do_write_to_binary_file
440 441 442 443 444 445 446 447 448 449 450
{
    template <class Graph, class IndexMap>
    void operator()(ostream& stream, Graph& g, IndexMap index_map, size_t N,
                    bool directed, vector<pair<string, boost::any >> & gprops,
                    vector<pair<string, boost::any >> & vprops,
                    vector<pair<string, boost::any >> & eprops) const
    {
        write_graph(g, index_map, N, directed, gprops, vprops, eprops, stream);
    }
};

Tiago Peixoto's avatar
Tiago Peixoto committed
451 452 453
struct generate_index
{
    template <class Graph, class IndexMap>
454
    void operator()(Graph& g, IndexMap index_map) const
Tiago Peixoto's avatar
Tiago Peixoto committed
455
    {
456 457
        size_t n = 0;
        typename graph_traits<Graph>::vertex_iterator v, v_end;
458
        for( tie(v, v_end) = vertices(g); v != v_end; ++v)
459
            index_map[*v] = n++;
Tiago Peixoto's avatar
Tiago Peixoto committed
460 461 462
    }
};

463 464
void GraphInterface::write_to_file(string file, boost::python::object pfile,
                                   string format, boost::python::list props)
Tiago Peixoto's avatar
Tiago Peixoto committed
465
{
466
    if (format != "gt" && format != "xml" && format != "dot" && format != "gml")
Tiago Peixoto's avatar
Tiago Peixoto committed
467
        throw ValueException("error writing to file '" + file +
468
                             "': requested invalid format '" + format + "'");
Tiago Peixoto's avatar
Tiago Peixoto committed
469 470
    try
    {
471 472 473 474 475 476
        boost::iostreams::filtering_stream<boost::iostreams::output> stream;
        std::ofstream file_stream;
        if (file == "-")
            stream.push(std::cout);
        else
        {
Tiago Peixoto's avatar
Tiago Peixoto committed
477
            if (pfile == boost::python::object())
478 479 480 481 482 483 484 485 486 487 488 489 490 491 492
            {
                file_stream.open(file.c_str(), std::ios_base::out |
                                 std::ios_base::binary);
                file_stream.exceptions(ios_base::badbit | ios_base::failbit);
                if (boost::ends_with(file,".gz"))
                    stream.push(boost::iostreams::gzip_compressor());
                if (boost::ends_with(file,".bz2"))
                    stream.push(boost::iostreams::bzip2_compressor());
                stream.push(file_stream);
            }
            else
            {
                python_file_device sink(pfile);
                stream.push(sink);
            }
493 494 495
        }
        stream.exceptions(ios_base::badbit | ios_base::failbit);

496
        if (format == "gt")
497
        {
498 499 500
            typedef property_map_types::apply<value_types,
                                              GraphInterface::graph_index_map_t>::type
                graph_properties;
501

502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517
            vector<pair<string, boost::any>> agprops, avprops, aeprops;
            for (int i = 0; i < python::len(props); ++i)
            {
                string name = python::extract<string>(props[i][0])();
                boost::any p = python::extract<boost::any>(props[i][1].attr("get_map")())();
                if (belongs<graph_properties>()(p))
                    agprops.push_back(make_pair(name, p));
                if (belongs<vertex_properties>()(p))
                    avprops.push_back(make_pair(name, p));
                if (belongs<edge_properties>()(p))
                    aeprops.push_back(make_pair(name, p));
            }

            bool directed = _directed;
            _directed = true;

518
            if (is_vertex_filter_active())
519 520 521 522 523 524
            {
                // vertex indexes must be between the [0, HardNumVertices(g)] range
                vector_property_map<size_t> index_map(_vertex_index);
                run_action<>()(*this, std::bind(generate_index(),
                                                std::placeholders::_1,
                                                index_map))();
525
                run_action<>()(*this, std::bind(do_write_to_binary_file(),
526 527 528
                                                std::ref(stream),
                                                std::placeholders::_1,
                                                index_map,
529
                                                get_num_vertices(),
530 531 532 533 534
                                                directed,
                                                std::ref(agprops),
                                                std::ref(avprops),
                                                std::ref(aeprops)))();
            }
535
            else
536
            {
537
                run_action<>()(*this, std::bind(do_write_to_binary_file(),
538 539 540
                                                std::ref(stream),
                                                std::placeholders::_1,
                                                _vertex_index,
541
                                                get_num_vertices(),
542 543 544 545 546 547 548
                                                directed,
                                                std::ref(agprops),
                                                std::ref(avprops),
                                                std::ref(aeprops)))();
            }

            _directed = directed;
549 550 551
        }
        else
        {
552 553 554 555 556 557 558 559 560 561 562
            dynamic_properties dp;
            for (int i = 0; i < len(props); ++i)
            {
                dynamic_property_map* pmap =
                    any_cast<dynamic_property_map*>
                    (boost::python::extract<boost::any>
                     (props[i][1].attr("get_dynamic_map")()));
                dp.insert(boost::python::extract<string>(props[i][0]),
                          DP_SMART_PTR<dynamic_property_map>(pmap));
            }

563
            if (is_vertex_filter_active())
564 565 566 567 568 569 570 571
            {
                // vertex indexes must be between the [0, HardNumVertices(g)] range
                vector_property_map<size_t> index_map(_vertex_index);
                run_action<>()(*this, boost::bind<void>(generate_index(),
                                                        _1, index_map))();
                if (format == "dot")
                    graphviz_insert_index(dp, index_map);

572 573 574 575 576
                run_action<>()
                    (*this, boost::bind<void>(do_write_to_file(),
                                              boost::ref(stream), _1,
                                              index_map, boost::ref(dp),
                                              format))();
577
            }
578
            else
579 580 581 582
            {
                if (format == "dot")
                    graphviz_insert_index(dp, _vertex_index);

583 584 585 586 587
                run_action<>()
                    (*this, boost::bind<void>(do_write_to_file(),
                                              boost::ref(stream), _1,
                                              _vertex_index,  boost::ref(dp),
                                              format))();
588
            }
589 590
        }
        stream.reset();
Tiago Peixoto's avatar
Tiago Peixoto committed
591 592 593
    }
    catch (ios_base::failure &e)
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
594
        throw IOException("error writing to file '" + file + "':" + e.what());
Tiago Peixoto's avatar
Tiago Peixoto committed
595 596
    }
}