graph_io.cc 19.4 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) 2007  Tiago de Paula Peixoto <tiago@forked.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
#include "graph_filtering.hh"
Tiago Peixoto's avatar
Tiago Peixoto committed
19
20
#include "graph.hh"
#include "graph_properties.hh"
21
22
23
#include "graph_util.hh"

#include <iostream>
24
#include <boost/algorithm/string.hpp>
25
#include <boost/iostreams/categories.hpp>
26
27
28
#include <boost/iostreams/filtering_stream.hpp>
#include <boost/iostreams/filter/gzip.hpp>
#include <boost/iostreams/filter/bzip2.hpp>
29
#include <boost/iostreams/device/file_descriptor.hpp>
30
#include <boost/iostreams/device/file.hpp>
31
#include <boost/lambda/bind.hpp>
32
#include <boost/graph/graphml.hpp>
33
#include <boost/graph/graphviz.hpp>
34
35
#include <boost/python/extract.hpp>
#include <boost/lexical_cast.hpp>
Tiago Peixoto's avatar
Tiago Peixoto committed
36
37
38
39
40
41

using namespace std;
using namespace boost;
using namespace boost::lambda;
using namespace graph_tool;

42
43
44
45
46
47
48
49
50
51
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
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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
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
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
//
// String representation of individual data types. We have to take care
// specifically that no information is lost with floating point I/O.
//

namespace boost
{
template <>
string lexical_cast<string,uint8_t>(const uint8_t& val)
{

    // "chars" should be printed as numbers, since they can be non-printable
    return lexical_cast<std::string>(int(val));
}

template <>
uint8_t lexical_cast<uint8_t,string>(const string& val)
{

    // "chars" should be printed as numbers, since they can be non-printable
    return uint8_t(lexical_cast<int>(val));
}

// double and long double should be printed in hexadecimal format to preserve
// internal representation
template <>
string lexical_cast<string,double>(const double& val)
{
    char* str = 0;
    asprintf(&str, "%la", val);
    std::string ret = str;
    free(str);
    return ret;
}

template <>
double lexical_cast<double,string>(const string& val)
{
    double ret;
    int nc = sscanf(val.c_str(), "%la", &ret);
    if (nc != 1)
        throw bad_lexical_cast();
    return ret;
}

template <>
string lexical_cast<string,long double>(const long double& val)
{
    char* str = 0;
    asprintf(&str, "%La", val);
    std::string ret = str;
    free(str);
    return ret;
}

template <>
long double lexical_cast<long double,string>(const string& val)
{
    long double ret;
    int nc = sscanf(val.c_str(), "%La", &ret);
    if (nc != 1)
        throw bad_lexical_cast();
    return ret;
}

}

// vector io
namespace std
{
// string vectors need special attention, since separators must be properly
// escaped.
template <>
ostream& operator<<(ostream& out, const vector<string>& vec)
{
    for (size_t i = 0; i < vec.size(); ++i)
    {
        string s = vec[i];
        // escape separators
        boost::replace_all(s, "\\", "\\\\");
        boost::replace_all(s, ", ", ",\\ ");

        out << s;
        if (i < vec.size() - 1)
            out << ", ";
    }
    return out;
}

template <>
istream& operator>>(istream& in, vector<string>& vec)
{
    using namespace boost;
    using namespace boost::algorithm;
    using namespace boost::xpressive;

    vec.clear();
    string data;
    while (in.good())
    {
        string line;
        getline(in, line);
        data += line;
    }

    sregex re = sregex::compile(", ");
    sregex_token_iterator iter(data.begin(), data.end(), re, -1), end;
    for (; iter != end; ++iter)
    {
        vec.push_back(*iter);
        // un-escape separators
        boost::replace_all(vec.back(), ",\\ ", ", ");
        boost::replace_all(vec.back(), "\\\\", "\\");
    }
    return in;
}
}

//
// 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();
    return "";
}

template <>
python::object lexical_cast<python::object,string>(const string& ps)
{
    stringstream s(ps);
    python::object o;
    o = object_unpickler(IStream(s));
    return o;
}
}

// 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;

    python_file_device(python::object file): _file(file) {}
    std::streamsize read(char* s, std::streamsize n)
    {
        python::object pbuf = _file.attr("read")(n);
        string buf = python::extract<string>(pbuf);
        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);
        python::object pbuf(buf);
        _file.attr("write")(pbuf);
        return n;
    }

    iostreams::stream_offset seek(iostreams::stream_offset off,
                                  std::ios_base::seekdir way)
    {
        _file.attr("seek")(off, int(way));
        return python::extract<iostreams::stream_offset>(_file.attr("tell")());
    }

private:
    python::object _file;
};
229

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

Tiago Peixoto's avatar
Tiago Peixoto committed
233
234
235
236
template <class IndexMap>
struct check_value_type
{
    typedef typename IndexMap::key_type key_t;
237
238
    check_value_type(IndexMap index_map, const key_t& key,
                     const boost::any& value, dynamic_property_map*& map)
239
        :_index_map(index_map), _key(key), _value(value), _map(map) {}
Tiago Peixoto's avatar
Tiago Peixoto committed
240
241
242
243

    template <class ValueType>
    void operator()(ValueType)
    {
244
245
246
247
        try
        {
            vector_property_map<ValueType, IndexMap> vector_map(_index_map);
            vector_map[_key] = any_cast<ValueType>(_value);
248
249
            _map = new boost::detail::dynamic_property_map_adaptor
                <vector_property_map<ValueType, IndexMap> >(vector_map);
250
251
        }
        catch (bad_any_cast) {}
Tiago Peixoto's avatar
Tiago Peixoto committed
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
    }
    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;

268
269
270
271
272
    create_dynamic_map(VertexIndexMap vertex_map, EdgeIndexMap edge_map)
        :_vertex_map(vertex_map), _edge_map(edge_map) {}
    auto_ptr<dynamic_property_map> operator()(const string& name,
                                              const boost::any& key,
                                              const boost::any& value)
Tiago Peixoto's avatar
Tiago Peixoto committed
273
    {
274
275
276
        dynamic_property_map* map;
        try
        {
277
278
279
280
            mpl::for_each<value_types>
                (check_value_type<VertexIndexMap>(_vertex_map,
                                                  any_cast<vertex_t>(key),
                                                  value, map));
281
282
283
        }
        catch (bad_any_cast)
        {
284
            try
285
            {
286
287
288
289
                mpl::for_each<value_types>
                    (check_value_type<EdgeIndexMap>(_edge_map,
                                                    any_cast<edge_t>(key),
                                                    value, map));
290
291
292
293
            }
            catch (bad_any_cast)
            {
                ConstantPropertyMap<size_t,graph_property_tag> graph_index(0);
294
295
296
297
298
                mpl::for_each<value_types>
                    (check_value_type<ConstantPropertyMap<size_t,
                                                          graph_property_tag> >
                     (graph_index, any_cast<graph_property_tag>(key),
                      value, map));
299
            }
300
301
        }
        return auto_ptr<dynamic_property_map>(map);
Tiago Peixoto's avatar
Tiago Peixoto committed
302
303
304
305
306
307
308
309
310
311
312
    }

    VertexIndexMap _vertex_map;
    EdgeIndexMap _edge_map;
};

// this graph wrapper will update the edge index map when edges are added

template <class Graph, class EdgeIndexMap>
struct GraphEdgeIndexWrap
{
313
314
    GraphEdgeIndexWrap(Graph &g, EdgeIndexMap edge_index_map)
        : _g(g), _edge_index_map(edge_index_map), _n_edges(0) {}
Tiago Peixoto's avatar
Tiago Peixoto committed
315
316
317
    Graph &_g;
    EdgeIndexMap _edge_index_map;
    size_t _n_edges;
318
319
320
321
322

    typedef typename Graph::vertex_property_type vertex_property_type;
    typedef typename Graph::edge_property_type edge_property_type;
    typedef typename Graph::graph_tag graph_tag;
    typedef typename Graph::graph_type graph_type;
Tiago Peixoto's avatar
Tiago Peixoto committed
323
324
325
};

template <class Graph, class EdgeIndexMap>
326
327
328
inline
typename graph_traits
    <GraphEdgeIndexWrap<Graph,EdgeIndexMap> >::vertex_descriptor
Tiago Peixoto's avatar
Tiago Peixoto committed
329
330
331
332
333
334
add_vertex(GraphEdgeIndexWrap<Graph,EdgeIndexMap>& g)
{
    return add_vertex(g._g);
}

template <class Graph, class EdgeIndexMap>
335
336
337
338
339
340
341
inline
pair<typename graph_traits
     <GraphEdgeIndexWrap<Graph,EdgeIndexMap> >::edge_descriptor,bool>
add_edge(typename graph_traits
         <GraphEdgeIndexWrap<Graph,EdgeIndexMap> >::vertex_descriptor u,
         typename graph_traits
         <GraphEdgeIndexWrap<Graph,EdgeIndexMap> >::vertex_descriptor v,
342
         GraphEdgeIndexWrap<Graph,EdgeIndexMap>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
343
{
344
345
346
347
    Graph& orig = g._g;
    pair<typename graph_traits
         <GraphEdgeIndexWrap<Graph,EdgeIndexMap> >::edge_descriptor,
         bool> retval = add_edge(u,v,orig);
Tiago Peixoto's avatar
Tiago Peixoto committed
348
    if (retval.second)
349
        g._edge_index_map[retval.first] = g._n_edges;
Tiago Peixoto's avatar
Tiago Peixoto committed
350
351
352
353
354
355
    ++g._n_edges;
    return retval;
}

namespace boost {
template <class Graph, class EdgeIndexMap>
356
357
class graph_traits<GraphEdgeIndexWrap<Graph,EdgeIndexMap> >
    : public graph_traits<Graph> {};
Tiago Peixoto's avatar
Tiago Peixoto committed
358
359
360
361
}

// this graph wraps an UndirectedAdaptor, but overrides the underlying
// edge_descriptor type with the original type. This will make the edge property
362
// maps compatible with the original graph, but will break some things which
Tiago Peixoto's avatar
Tiago Peixoto committed
363
364
365
366
367
368
369
370
371
372
// are not relevant here

template <class Graph>
struct FakeUndirGraph: public UndirectedAdaptor<Graph>
{
    FakeUndirGraph(const Graph &g): UndirectedAdaptor<Graph>(g) {}
    FakeUndirGraph(UndirectedAdaptor<Graph> &g): UndirectedAdaptor<Graph>(g) {}
};

template <class Graph>
373
374
struct FakeEdgeIterator:
    public graph_traits<UndirectedAdaptor<Graph> >::edge_iterator
Tiago Peixoto's avatar
Tiago Peixoto committed
375
{
376
377
378
379
    typedef typename graph_traits<FakeUndirGraph<Graph> >::edge_descriptor
        edge_descriptor;
    typedef typename graph_traits<UndirectedAdaptor<Graph> >::edge_iterator
        edge_iterator;
Tiago Peixoto's avatar
Tiago Peixoto committed
380
381
382
383
    FakeEdgeIterator(){}
    FakeEdgeIterator(edge_iterator e): edge_iterator(e) {}
    edge_descriptor operator*() const
    {
384
        return edge_descriptor(*edge_iterator(*this));
385
    }
Tiago Peixoto's avatar
Tiago Peixoto committed
386
387
388
389
390

};

namespace boost {
template <class Graph>
391
392
struct graph_traits<FakeUndirGraph<Graph> >
    : public graph_traits<UndirectedAdaptor<Graph> >
Tiago Peixoto's avatar
Tiago Peixoto committed
393
394
395
396
397
398
399
400
{
    typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
    typedef FakeEdgeIterator<Graph> edge_iterator;
};
}


//==============================================================================
401
// ReadFromFile(file, pfile, format)
Tiago Peixoto's avatar
Tiago Peixoto committed
402
403
//==============================================================================

404
405
406
void build_stream
    (boost::iostreams::filtering_stream<boost::iostreams::input>& stream,
     const string& file,  python::object& pfile, std::ifstream& file_stream)
Tiago Peixoto's avatar
Tiago Peixoto committed
407
{
408
409
410
411
    stream.reset();
    if (file == "-")
        stream.push(std::cin);
    else
Tiago Peixoto's avatar
Tiago Peixoto committed
412
    {
413
        if (pfile == python::object())
414
        {
415
416
            file_stream.open(file.c_str(), std::ios_base::in |
                             std::ios_base::binary);
417
418
            file_stream.exceptions(ios_base::badbit | ios_base::failbit);
            if (boost::ends_with(file,".gz"))
419
                stream.push(boost::iostreams::gzip_decompressor());
420
            if (boost::ends_with(file,".bz2"))
421
                stream.push(boost::iostreams::bzip2_decompressor());
422
423
            stream.push(file_stream);
        }
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
        else
        {
            python_file_device src(pfile);
            stream.push(src);
        }
    }
    stream.exceptions(ios_base::badbit);
}


void GraphInterface::ReadFromFile(string file, python::object pfile,
                                  string format)
{
    bool graphviz = false;
    if (format == "dot")
        graphviz = true;
    else if (format != "xml")
        throw GraphException("error reading from file '" + file +
                             "': requested invalid format '" + format + "'");
    try
    {
        boost::iostreams::filtering_stream<boost::iostreams::input>
            stream;
        std::ifstream file_stream;
        build_stream(stream, file, pfile, file_stream);
449
450
451
452

        _properties = dynamic_properties();
        _mg.clear();

453
454
455
        dynamic_properties_copy
            dp(create_dynamic_map<vertex_index_map_t, edge_index_map_t>
               (_vertex_index, _edge_index));
456
        GraphEdgeIndexWrap<multigraph_t,edge_index_map_t> wg(_mg, _edge_index);
457
458
        _directed = true;
        try
459
460
        {
            if (graphviz)
461
                read_graphviz(stream, wg, dp, "vertex_name");
462
            else
463
                read_graphml(stream, wg, dp);
464
        }
465
        catch (const undirected_graph_error&)
466
        {
467
468
469
470
471
472
473
474
            _directed = false;
            file_stream.close();
            if (pfile != python::object())
            {
                python_file_device src(pfile);
                src.seek(0, std::ios_base::beg);
            }
            build_stream(stream, file, pfile, file_stream);
475
476
            FakeUndirGraph<GraphEdgeIndexWrap<multigraph_t,edge_index_map_t> >
                ug(wg);
477
            if (graphviz)
478
                read_graphviz(stream, ug, dp, "vertex_name");
479
            else
480
                read_graphml(stream, ug, dp);
481
        }
482

483
        _properties = dp;
Tiago Peixoto's avatar
Tiago Peixoto committed
484
485
486
    }
    catch (ios_base::failure &e)
    {
487
488
        throw GraphException("error reading from file '" + file + "':" +
                             e.what());
Tiago Peixoto's avatar
Tiago Peixoto committed
489
490
491
492
    }

};

493
494
// writes a graph to a file

Tiago Peixoto's avatar
Tiago Peixoto committed
495
496
497
struct write_to_file
{
    template <class Graph, class IndexMap>
498
    void operator()(ostream& stream, Graph* g, IndexMap index_map,
499
                    dynamic_properties& dp, bool graphviz) const
Tiago Peixoto's avatar
Tiago Peixoto committed
500
    {
501
502
        typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;

503
504
505
506
507
        if (graphviz)
        {
            string name;
            try
            {
508
                find_property_map(dp, "vertex_name", typeid(vertex_t));
509
                name = "vertex_name";
510
            }
Tiago Peixoto's avatar
Tiago Peixoto committed
511
            catch (PropertyNotFound)
512
            {
513
                name = "vertex_id";
514
            }
515
            write_graphviz(stream, *g, dp, name);
516
517
518
        }
        else
        {
519
            write_graphml(stream, *g, index_map, dp, true);
520
        }
Tiago Peixoto's avatar
Tiago Peixoto committed
521
522
523
524
525
526
527

    }
};

struct write_to_file_fake_undir: public write_to_file
{
    template <class Graph, class IndexMap>
528
    void operator()(ostream& stream, Graph* g, IndexMap index_map,
529
                    dynamic_properties& dp, bool graphviz) const
Tiago Peixoto's avatar
Tiago Peixoto committed
530
    {
531
        typedef typename Graph::original_graph_t graph_t;
532
533
        FakeUndirGraph<graph_t> ug(*g);
        write_to_file(*this)(stream, &ug, index_map, dp, graphviz);
Tiago Peixoto's avatar
Tiago Peixoto committed
534
535
536
537
538
539
    }
};

struct generate_index
{
    template <class Graph, class IndexMap>
540
    void operator()(Graph* g, IndexMap index_map) const
Tiago Peixoto's avatar
Tiago Peixoto committed
541
    {
542
543
        size_t n = 0;
        typename graph_traits<Graph>::vertex_iterator v, v_end;
544
        for( tie(v, v_end) = vertices(*g); v != v_end; ++v)
545
            index_map[*v] = n++;
Tiago Peixoto's avatar
Tiago Peixoto committed
546
547
548
    }
};

549
550
void GraphInterface::WriteToFile(string file, python::object pfile,
                                 string format)
Tiago Peixoto's avatar
Tiago Peixoto committed
551
{
Tiago Peixoto's avatar
Tiago Peixoto committed
552
553
    bool graphviz = false;
    if (format == "dot")
554
        graphviz = true;
Tiago Peixoto's avatar
Tiago Peixoto committed
555
    else if (format != "xml")
556
557
        throw GraphException("error writing to file '" + file +
                             "': requested invalid format '" + format + "'");
Tiago Peixoto's avatar
Tiago Peixoto committed
558
559
    try
    {
560
561
562
563
564
565
        boost::iostreams::filtering_stream<boost::iostreams::output> stream;
        std::ofstream file_stream;
        if (file == "-")
            stream.push(std::cout);
        else
        {
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
            if (pfile == python::object())
            {
                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);
            }
582
583
584
585
586
587
588
589
        }
        stream.exceptions(ios_base::badbit | ios_base::failbit);

        dynamic_properties_copy dp = _properties;

        if (IsVertexFilterActive())
        {
            // vertex indexes must be between the [0, HardNumVertices(g)] range
590
            typedef tr1::unordered_map<vertex_t, size_t>  map_t;
591
592
            map_t vertex_to_index;
            associative_property_map<map_t> index_map(vertex_to_index);
593
            run_action<>()(*this, bind<void>(generate_index(), _1,
594
                                             index_map))();
595
596
            if (graphviz)
            {
597
598
                try
                {
599
                    find_property_map(dp, "vertex_name", typeid(vertex_t));
600
                }
Tiago Peixoto's avatar
Tiago Peixoto committed
601
                catch (PropertyNotFound)
602
603
604
                {
                    dp.property("vertex_id", index_map);
                }
605
606
607
            }
            if (GetDirected())
            {
608
609
610
                run_action<detail::always_directed>()
                    (*this,bind<void>(write_to_file(), var(stream), _1,
                                      index_map, var(dp), graphviz))();
611
612
613
            }
            else
            {
614
615
616
                run_action<detail::never_directed>()
                    (*this,bind<void>(write_to_file_fake_undir(), var(stream),
                                      _1, index_map, var(dp), graphviz))();
617
618
619
620
621
622
            }
        }
        else
        {
            if (graphviz)
            {
623
624
                try
                {
625
                    find_property_map(dp, "vertex_name", typeid(vertex_t));
626
                }
Tiago Peixoto's avatar
Tiago Peixoto committed
627
                catch (PropertyNotFound)
628
629
630
                {
                    dp.property("vertex_id", _vertex_index);
                }
631
632
633
634
            }

            if (GetDirected())
            {
635
636
637
638
                run_action<detail::always_directed>()
                    (*this,bind<void>(write_to_file(), var(stream),
                                      _1, _vertex_index, var(dp),
                                      graphviz))();
639
640
641
            }
            else
            {
642
643
644
645
                run_action<detail::never_directed>()
                    (*this,bind<void>(write_to_file_fake_undir(), var(stream),
                                      _1, _vertex_index, var(dp),
                                      graphviz))();
646
647
648
            }
        }
        stream.reset();
Tiago Peixoto's avatar
Tiago Peixoto committed
649
650
651
    }
    catch (ios_base::failure &e)
    {
652
653
        throw GraphException("error writing to file '" + file + "':" +
                             e.what());
Tiago Peixoto's avatar
Tiago Peixoto committed
654
655
    }
}