graph_python_interface.hh 19.7 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-2015 Tiago de Paula Peixoto <tiago@skewed.de>
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
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
// along with this program. If not, see <http://www.gnu.org/licenses/>.
17

18
19
#ifndef PYTHON_INTERFACE_HH
#define PYTHON_INTERFACE_HH
20

21
22
23
#include <boost/python.hpp>
#include <boost/python/type_id.hpp>

Tiago Peixoto's avatar
Tiago Peixoto committed
24
25
26
27
28
29
30
31
32
#include <functional>

namespace std
{
    template<>
    struct hash<boost::python::object>
    {
        size_t operator()(const boost::python::object& o) const
        {
33
            return std::hash<int64_t>()(boost::python::extract<int64_t>(o.attr("__hash__")()));
Tiago Peixoto's avatar
Tiago Peixoto committed
34
35
36
37
        }
    };
}

38
39
#include <boost/graph/graph_traits.hpp>
#include <boost/mpl/logical.hpp>
40
#include <boost/iterator/iterator_facade.hpp>
41

Tiago Peixoto's avatar
Tiago Peixoto committed
42
43
#include <type_traits>

44
45
#include "graph.hh"
#include "graph_filtering.hh"
46
#include "graph_selectors.hh"
47
#include "numpy_bind.hh"
48

49

50
// this file includes a simple python interface for the internally kept
51
52
53
54
// graph. It defines a PythonVertex, PythonEdge and PythonIterator template
// classes, which contain the proper member functions for graph traversal. These
// types are then specialized for each version of the adapted graph (directed,
// undirected, filtered, reversed).
55

56
57
58
namespace graph_tool
{

59
60
// generic iterator adaptor which can be used to iterate vertices, edges,
// out_edges and in_edges through python
61
template <class Graph, class Descriptor, class Iterator>
62
class PythonIterator
63
{
64
public:
65
    PythonIterator(std::shared_ptr<Graph>& gp,
66
                   std::pair<Iterator,Iterator> e)
67
        : _g(gp), _e(e) {}
68
    Descriptor next()
69
    {
70
        if (_e.first == _e.second)
Tiago Peixoto's avatar
Tiago Peixoto committed
71
            boost::python::objects::stop_iteration_error();
72
        Descriptor e(_g, *_e.first);
73
74
        ++_e.first;
        return e;
75
76
    }
private:
77
    std::shared_ptr<Graph> _g;
78
    std::pair<Iterator,Iterator> _e;
Tiago Peixoto's avatar
Tiago Peixoto committed
79
80
81
};


82
// forward declaration of PythonEdge
83
84
template <class Graph>
class PythonEdge;
85

86
87
class VertexBase {}; // useful to unite all vertex

88
// below are classes related to the PythonVertex type
89
90
template <class Graph>
class PythonVertex : public VertexBase
91
92
{
public:
93
94
    PythonVertex(std::shared_ptr<Graph> g, GraphInterface::vertex_t v):
        _g(g), _v(v) {}
95

96
    bool is_valid() const
97
    {
98
99
100
        std::shared_ptr<Graph> gp(_g);
        Graph* g = gp.get();
        if (g == nullptr)
101
            return false;
102
103
        return ((_v != boost::graph_traits<Graph>::null_vertex()) &&
                (_v < num_vertices(*g)));
104
    }
105

106
    void check_valid() const
107
    {
108
        if (!is_valid())
109
            throw ValueException("invalid vertex descriptor: " +
Tiago Peixoto's avatar
Tiago Peixoto committed
110
                                 boost::lexical_cast<string>(_v));
111
    }
112

113
    GraphInterface::vertex_t get_descriptor() const
114
115
116
117
    {
        return _v;
    }

118
119
120
    template <class DegSelector>
    struct get_degree
    {
121
        void operator()(const Graph& g,
Tiago Peixoto's avatar
Tiago Peixoto committed
122
                        typename boost::graph_traits<Graph>::vertex_descriptor v,
123
124
                        size_t& deg) const
        {
125
            deg = DegSelector()(v, g);
126
        }
127

128
        template<class PMap>
129
130
        void operator()(const Graph& g,
                        typename boost::graph_traits<Graph>::vertex_descriptor v,
131
132
                        const boost::any& aweight, boost::python::object& deg,
                        bool& found, PMap) const
133
        {
134
135
136
137
138
139
140
            try
            {
                const PMap& weight = boost::any_cast<const PMap&>(aweight);
                deg = boost::python::object(DegSelector()(v, g, weight));
                found = true;
            }
            catch (boost::bad_any_cast&) {}
141
        }
142
143
    };

144
    size_t get_in_degree() const
145
    {
146
        check_valid();
147
148
        std::shared_ptr<Graph> gp(_g);
        Graph& g = *gp.get();
149
        size_t in_deg;
150
        get_degree<in_degreeS>()(g, _v, in_deg);
151
        return in_deg;
152
    }
153

154
    boost::python::object get_weighted_in_degree(boost::any pmap) const
155
    {
156
157
        std::shared_ptr<Graph> gp(_g);
        Graph& g = *gp.get();
158
        boost::python::object in_deg;
159
160
161
162
163
164
165
166
167
        bool found = false;
        boost::mpl::for_each<edge_scalar_properties>(std::bind(get_degree<in_degreeS>(),
                                                               std::ref(g), _v,
                                                               std::ref(pmap),
                                                               std::ref(in_deg),
                                                               std::ref(found),
                                                               std::placeholders::_1));
        if (!found)
            throw ValueException("edge weight property must be of scalar type");
168
169
170
        return in_deg;
    }

171
    size_t get_out_degree() const
172
    {
173
        check_valid();
174
175
        std::shared_ptr<Graph> gp(_g);
        Graph& g = *gp.get();
176
        size_t out_deg;
177
        get_degree<out_degreeS>()(g, _v, out_deg);
178
        return out_deg;
Tiago Peixoto's avatar
Tiago Peixoto committed
179
180
    }

181

182
    boost::python::object get_weighted_out_degree(boost::any pmap) const
183
    {
184
185
        std::shared_ptr<Graph> gp(_g);
        Graph& g = *gp.get();
186
        boost::python::object out_deg;
187
188
189
190
191
192
193
194
195
        bool found = false;
        boost::mpl::for_each<edge_scalar_properties>(std::bind(get_degree<out_degreeS>(),
                                                               std::ref(g), _v,
                                                               std::ref(pmap),
                                                               std::ref(out_deg),
                                                               std::ref(found),
                                                               std::placeholders::_1));
        if (!found)
            throw ValueException("edge weight property must be of scalar type");
196
197
198
        return out_deg;
    }

199
    // provide iterator support for out_edges
200
    boost::python::object out_edges() const
Tiago Peixoto's avatar
Tiago Peixoto committed
201
    {
202
        check_valid();
203
204
205
206
207
208
        std::shared_ptr<Graph> pg(_g);
        Graph& g = *pg;
        typedef typename boost::graph_traits<Graph>::out_edge_iterator
            out_edge_iterator;
        return boost::python::object(PythonIterator<Graph,PythonEdge<Graph>,
                                                    out_edge_iterator>
209
                                     (pg, boost::out_edges(_v, g)));
210
    }
211

212
    boost::python::object in_edges() const
213
    {
214
        check_valid();
215
216
217
218
219
220
221
        std::shared_ptr<Graph> pg(_g);
        Graph& g = *pg;
        typedef typename in_edge_iteratorS<Graph>::type
            in_edge_iterator;
        return boost::python::object(PythonIterator<Graph, PythonEdge<Graph>,
                                                    in_edge_iterator>
                                     (pg, in_edge_iteratorS<Graph>::get_edges(_v, g)));
Tiago Peixoto's avatar
Tiago Peixoto committed
222
    }
223

224
    std::string get_string() const
225
    {
226
        check_valid();
Tiago Peixoto's avatar
Tiago Peixoto committed
227
        return boost::lexical_cast<std::string>(_v);
228
229
    }

230
    size_t get_hash() const
231
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
232
        return std::hash<size_t>()(_v);
233
234
    }

235
    size_t get_index() const
236
    {
237
        return _v;
238
239
    }

240
    size_t get_graph_ptr() const
241
242
243
244
245
    {
        std::shared_ptr<Graph> pg(_g);
        return size_t(pg.get());
    }

246
    std::string get_graph_type() const
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
    {
        using boost::python::detail::gcc_demangle;
        return gcc_demangle(typeid(Graph).name());
    }

    template <class OGraph>
    bool operator==(const PythonVertex<OGraph>& other) const { return _v == other._v; }
    template <class OGraph>
    bool operator!=(const PythonVertex<OGraph>& other) const { return _v != other._v; }
    template <class OGraph>
    bool operator<(const PythonVertex<OGraph>& other) const { return _v < other._v; }
    template <class OGraph>
    bool operator<=(const PythonVertex<OGraph>& other) const { return _v <= other._v; }
    template <class OGraph>
    bool operator>(const PythonVertex<OGraph>& other) const { return _v > other._v; }
    template <class OGraph>
    bool operator>=(const PythonVertex<OGraph>& other) const { return _v >= other._v; }

265
private:
266
    std::weak_ptr<Graph> _g;
267
    GraphInterface::vertex_t _v;
268
};
269

270
// below are classes related to the PythonEdge type
271

272
273
class EdgeBase {}; // useful to unite all edge types

274
template <class Graph>
275
class PythonEdge : public EdgeBase
276
277
{
public:
Tiago Peixoto's avatar
Tiago Peixoto committed
278
    typedef typename boost::graph_traits<Graph>::edge_descriptor edge_descriptor;
279
280
    PythonEdge(std::shared_ptr<Graph> g, edge_descriptor e)
        : _g(g), _e(e) {}
281

282
    bool is_valid() const
Tiago Peixoto's avatar
Tiago Peixoto committed
283
    {
284
285
286
        std::shared_ptr<Graph> gp(_g);
        Graph* g = gp.get();
        if (g == nullptr)
287
            return false;
288

289
290
        auto s = source(_e, *g);
        auto t = target(_e, *g);
291

292
293
294
295
        return ((s != boost::graph_traits<Graph>::null_vertex()) &&
                (s < num_vertices(*g)) &&
                (t != boost::graph_traits<Graph>::null_vertex()) &&
                (t < num_vertices(*g)));
296
297
    }

298
    void check_valid() const
299
    {
300
        if (!is_valid())
Tiago Peixoto's avatar
Tiago Peixoto committed
301
            throw ValueException("invalid edge descriptor");
Tiago Peixoto's avatar
Tiago Peixoto committed
302
303
    }

304
    GraphInterface::edge_t get_descriptor() const
305
306
307
308
    {
        return _e;
    }

309
    PythonVertex<Graph> get_source() const
310
    {
311
        check_valid();
312
313
314
315
        std::shared_ptr<Graph> pg(_g);
        Graph& g = *pg;
        return PythonVertex<Graph>(pg, source(_e, g));
    }
316

317
    PythonVertex<Graph> get_target() const
Tiago Peixoto's avatar
Tiago Peixoto committed
318
    {
319
        check_valid();
320
321
322
        std::shared_ptr<Graph> pg(_g);
        Graph& g = *pg;
        return PythonVertex<Graph>(pg, target(_e, g));
Tiago Peixoto's avatar
Tiago Peixoto committed
323
324
    }

325
    std::string get_string() const
326
    {
327
        check_valid();
328
329
330
331
332
333
        Graph& g = *std::shared_ptr<Graph>(_g);
        auto s = source(_e, g);
        auto t = target(_e, g);
        return "(" + boost::lexical_cast<std::string>(s) + ", "
            + boost::lexical_cast<std::string>(t) + ")";
    }
334

335
    size_t get_hash() const
Tiago Peixoto's avatar
Tiago Peixoto committed
336
    {
337
        check_valid();
338
339
340
        Graph& g = *std::shared_ptr<Graph>(_g);
        auto eindex = get(boost::edge_index_t(), g);
        return std::hash<size_t>()(eindex[_e]);
Tiago Peixoto's avatar
Tiago Peixoto committed
341
342
    }

343
    size_t get_graph_ptr() const
344
    {
345
346
        std::shared_ptr<Graph> pg(_g);
        return site_t(pg.get());
347
348
    }

349
    std::string get_graph_type() const
350
351
352
353
354
355
356
357
358
359
360
    {
        using boost::python::detail::gcc_demangle;
        return gcc_demangle(typeid(Graph).name());
    }

    template <class OGraph>
    bool operator==(const PythonEdge<OGraph>& other) const { return _e == other._e; }
    template <class OGraph>
    bool operator!=(const PythonEdge<OGraph>& other) const { return !(*this == other); }
    template <class OGraph>
    bool operator<(const PythonEdge<OGraph>& other)  const
Tiago Peixoto's avatar
Tiago Peixoto committed
361
    {
362
363
        check_valid();
        other.check_valid();
364
365
        Graph& g = *std::shared_ptr<Graph>(_g);
        OGraph& og = *std::shared_ptr<OGraph>(other._g);
366
367
368
        auto eindex = get(boost::edge_index_t(), g);
        auto eindex2 = get(boost::edge_index_t(), og);
        return eindex[_e] < eindex2[other._e];
Tiago Peixoto's avatar
Tiago Peixoto committed
369
    }
370
371
372
373
374
375
    template <class OGraph>
    bool operator<=(const PythonEdge<OGraph>& other) const {return *this < other || *this == other;}
    template <class OGraph>
    bool operator>(const PythonEdge<OGraph>& other) const {return !(*this < other || *this == other);}
    template <class OGraph>
    bool operator>=(const PythonEdge<OGraph>& other) const {return *this > other || *this == other;}
Tiago Peixoto's avatar
Tiago Peixoto committed
376

377
private:
378
    std::weak_ptr<Graph> _g;
379
    edge_descriptor _e;
380
381
382

    template <class OGraph>
    friend class PythonEdge;
383
384
};

385
386
387
388
389
390
391
392
393
394
// metafunction to determine wether or not to return copies or internal
// references to property types
struct return_reference
{
    template <class ValueType>
    struct apply
    {
        // return actual references only for non-string and non-python::object
        // classes

Tiago Peixoto's avatar
Tiago Peixoto committed
395
396
397
398
399
400
401
402
        typedef typename boost::mpl::if_<
            typename boost::mpl::and_<
                std::is_class<ValueType>,
                typename boost::mpl::and_<
                    typename boost::mpl::not_<std::is_same<ValueType,
                                                           string> >::type,
                    typename boost::mpl::not_<std::is_same<ValueType,
                                                           boost::python::object> >::type>::type
403
                >::type,
Tiago Peixoto's avatar
Tiago Peixoto committed
404
405
            boost::mpl::bool_<true>,
            boost::mpl::bool_<false> >::type type;
406
407
408
409
    };
};

template <class PropertyMap>
410
411
412
class PythonPropertyMap
{
public:
413
414
    PythonPropertyMap(const PropertyMap& pmap)
        : _pmap(pmap) {}
415

Tiago Peixoto's avatar
Tiago Peixoto committed
416
    typedef typename boost::property_traits<PropertyMap>::value_type value_type;
417

Tiago Peixoto's avatar
Tiago Peixoto committed
418
    typedef typename boost::mpl::if_<
419
420
421
422
        typename return_reference::apply<value_type>::type,
        value_type&,
        value_type>::type reference;

423
    template <class PythonDescriptor>
424
    reference get_value(const PythonDescriptor& key)
425
    {
426
427
        key.check_valid();
        return get(_pmap, key.get_descriptor());
428
429
    }

430
431
    // in this case, val should be a copy, not a reference. This is to avoid a
    // problem with vector-valued property maps
432
    template <class PythonDescriptor>
433
    void set_value(const PythonDescriptor& key, value_type val)
434
    {
435
436
437
        set_value_dispatch(key, val,
                           std::is_convertible<typename boost::property_traits<PropertyMap>::category,
                                               boost::writable_property_map_tag>());
438
439
    }

440
    template <class PythonDescriptor>
441
442
    void set_value_dispatch(const PythonDescriptor& key, const value_type& val,
                            std::true_type)
443
    {
444
445
        key.check_valid();
        put(_pmap, key.get_descriptor(), val);
446
447
    }

448
    template <class PythonDescriptor>
449
450
    void set_value_dispatch(const PythonDescriptor&, const value_type&,
                            std::false_type)
451
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
452
        throw ValueException("property is read-only");
453
454
    }

455
    size_t get_hash() const
456
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
457
        return std::hash<size_t>()(size_t(this));
458
459
    }

460
    std::string get_type() const
461
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
462
463
464
        using boost::python::detail::gcc_demangle;
        if (std::is_same<typename boost::mpl::find<value_types,value_type>::type,
                         typename boost::mpl::end<value_types>::type>::value)
465
466
            return gcc_demangle(typeid(value_type).name());
        else
Tiago Peixoto's avatar
Tiago Peixoto committed
467
            return type_names[boost::mpl::find<value_types,
468
                                               value_type>::type::pos::value];
469
470
    }

471
    boost::any get_map() const
472
473
474
475
    {
        return _pmap;
    }

476
    boost::any get_dynamic_map() const
477
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
478
        return (boost::dynamic_property_map*)
479
480
481
482
            (new boost::detail::dynamic_property_map_adaptor<PropertyMap>
             (_pmap));
    }

483
    boost::python::object get_array(size_t size)
484
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
485
486
487
488
489
490
491
492
        typedef typename boost::mpl::or_<
            typename boost::mpl::or_<
                std::is_same<PropertyMap,
                             GraphInterface::vertex_index_map_t>,
                std::is_same<PropertyMap,
                             GraphInterface::edge_index_map_t> >::type,
            typename boost::mpl::not_<
                typename boost::mpl::has_key<numpy_types, value_type>::type >
493
            ::type>::type isnt_vector_map;
494
        return get_array_dispatch(size, isnt_vector_map());
495
496
    }

497
    boost::python::object get_array_dispatch(size_t size, boost::mpl::bool_<false>)
498
    {
499
        _pmap.resize(size);
500
501
502
        return wrap_vector_not_owned(_pmap.get_storage());
    }

503
    boost::python::object get_array_dispatch(size_t, boost::mpl::bool_<true>)
504
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
505
        return boost::python::object();
506
507
    }

508
    bool is_writable() const
509
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
510
511
        return std::is_convertible<typename boost::property_traits<PropertyMap>::category,
                                   boost::writable_property_map_tag>::value;
512
513
    }

514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
    void reserve(size_t size)
    {
        typename boost::mpl::or_<
            std::is_same<PropertyMap,
                         GraphInterface::vertex_index_map_t>,
            std::is_same<PropertyMap,
                         GraphInterface::edge_index_map_t> >::type is_index;
        reserve_dispatch(size, is_index);
    }

    void reserve_dispatch(size_t size, boost::mpl::bool_<false>)
    {
        _pmap.reserve(size);
    }

    void reserve_dispatch(size_t, boost::mpl::bool_<true>)
    {
    }

    void resize(size_t size)
    {
        typename boost::mpl::or_<
            std::is_same<PropertyMap,
                         GraphInterface::vertex_index_map_t>,
            std::is_same<PropertyMap,
                         GraphInterface::edge_index_map_t> >::type is_index;
        resize_dispatch(size, is_index);
    }

    void resize_dispatch(size_t size, boost::mpl::bool_<false>)
    {
        _pmap.resize(size);
    }

    void resize_dispatch(size_t, boost::mpl::bool_<true>)
    {
    }

    void shrink_to_fit()
    {
        typename boost::mpl::or_<
            std::is_same<PropertyMap,
                         GraphInterface::vertex_index_map_t>,
            std::is_same<PropertyMap,
                         GraphInterface::edge_index_map_t> >::type is_index;
        shrink_to_fit_dispatch(is_index);
    }

    void shrink_to_fit_dispatch(boost::mpl::bool_<false>)
    {
        _pmap.shrink_to_fit();
    }

    void shrink_to_fit_dispatch(boost::mpl::bool_<true>)
    {
    }

571
private:
572
    PropertyMap _pmap; // hold an internal copy, since it's cheap
573
574
575
};


576
577
578
579
580
581
582
583
//
// Create new properties
//

struct new_property_map
{
    template <class ValueType, class IndexMap>
    void operator()(ValueType, IndexMap index, const string& type_name,
Tiago Peixoto's avatar
Tiago Peixoto committed
584
                     boost::any pmap, boost::python::object& new_prop, bool& found) const
585
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
586
        size_t i = boost::mpl::find<value_types,ValueType>::type::pos::value;
587
588
        if (type_name == type_names[i])
        {
589
590
            typedef typename property_map_type::apply<ValueType, IndexMap>::type
                map_t;
591
592
593
594
            map_t prop;
            if (pmap.empty())
                prop = map_t(index);
            else
Tiago Peixoto's avatar
Tiago Peixoto committed
595
                prop = boost::any_cast<map_t>(pmap);
596

Tiago Peixoto's avatar
Tiago Peixoto committed
597
            new_prop = boost::python::object(PythonPropertyMap<map_t>(prop));
598
599
600
601
602
603
            found = true;
        }
    }
};

template <class IndexMap>
Tiago Peixoto's avatar
Tiago Peixoto committed
604
605
boost::python::object new_property(const string& type, IndexMap index_map,
                                   boost::any pmap)
606
{
Tiago Peixoto's avatar
Tiago Peixoto committed
607
    boost::python::object prop;
608
    bool found = false;
Tiago Peixoto's avatar
Tiago Peixoto committed
609
610
611
612
    boost::mpl::for_each<value_types>(std::bind(new_property_map(),
                                                std::placeholders::_1, index_map,
                                                std::ref(type), pmap, std::ref(prop),
                                                std::ref(found)));
613
    if (!found)
Tiago Peixoto's avatar
Tiago Peixoto committed
614
        throw ValueException("Invalid property type: " + type);
615
616
617
    return prop;
}

618
619
620
621
622
623
624
625
626
//
// Python IO streams (minimal access to c++ streams)
//

class OStream
{
public:
    OStream(std::ostream& s): _s(s) {}

627
    void write(const std::string& s, size_t n)
628
629
630
631
    {
        _s.write(s.c_str(), long(n));
    }

632
    void flush()
633
634
635
636
637
638
639
640
641
642
643
644
645
    {
        _s.flush();
    }

private:
    std::ostream& _s;
};

class IStream
{
public:
    IStream(std::istream& s): _s(s) {}

646
    boost::python::object read(size_t n)
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
    {
        std::string buf;
        buf.resize(n);
        _s.read(&buf[0], n);
        buf.resize(_s.gcount());

#if (PY_MAJOR_VERSION >= 3)
        // in python 3 we need to construct a 'bytes' instance
        PyObject* bytes = PyBytes_FromStringAndSize(&buf[0], buf.size());
        boost::python::handle<> x(bytes);
        boost::python::object pbuf(x);
#else
        boost::python::str pbuf(buf);
#endif
        return pbuf;
    }

private:
    std::istream& _s;
};


669
670
671
} //graph_tool namespace

#endif