graph_python_interface.hh 18.5 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
366
367
368
369
370
371
372
373
374
375
376
377
378
        Graph& g = *std::shared_ptr<Graph>(_g);
        OGraph& og = *std::shared_ptr<OGraph>(other._g);
        auto s = source(_e, g);
        auto t = target(_e, g);
        auto os = source(other._e, og);
        auto ot = target(other._e, og);
        if (not is_directed::apply<Graph>::type::value ||
            not is_directed::apply<OGraph>::type::value)
        {
            if (t < s)
                std::swap(s, t);
            if (ot < os)
                std::swap(os, ot);
        }
        return s < os && t < ot;
Tiago Peixoto's avatar
Tiago Peixoto committed
379
    }
380
381
382
383
384
385
    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
386

387
private:
388
    std::weak_ptr<Graph> _g;
389
    edge_descriptor _e;
390
391
392

    template <class OGraph>
    friend class PythonEdge;
393
394
};

395
396
397
398
399
400
401
402
403
404
// 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
405
406
407
408
409
410
411
412
        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
413
                >::type,
Tiago Peixoto's avatar
Tiago Peixoto committed
414
415
            boost::mpl::bool_<true>,
            boost::mpl::bool_<false> >::type type;
416
417
418
419
    };
};

template <class PropertyMap>
420
421
422
class PythonPropertyMap
{
public:
423
424
    PythonPropertyMap(const PropertyMap& pmap)
        : _pmap(pmap) {}
425

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

Tiago Peixoto's avatar
Tiago Peixoto committed
428
    typedef typename boost::mpl::if_<
429
430
431
432
        typename return_reference::apply<value_type>::type,
        value_type&,
        value_type>::type reference;

433
    template <class PythonDescriptor>
434
    reference get_value(const PythonDescriptor& key)
435
    {
436
437
        key.check_valid();
        return get(_pmap, key.get_descriptor());
438
439
    }

440
441
    // in this case, val should be a copy, not a reference. This is to avoid a
    // problem with vector-valued property maps
442
    template <class PythonDescriptor>
443
    void set_value(const PythonDescriptor& key, value_type val)
444
    {
445
446
447
        set_value_dispatch(key, val,
                           std::is_convertible<typename boost::property_traits<PropertyMap>::category,
                                               boost::writable_property_map_tag>());
448
449
    }

450
    template <class PythonDescriptor>
451
452
    void set_value_dispatch(const PythonDescriptor& key, const value_type& val,
                            std::true_type)
453
    {
454
455
        key.check_valid();
        put(_pmap, key.get_descriptor(), val);
456
457
    }

458
    template <class PythonDescriptor>
459
460
    void set_value_dispatch(const PythonDescriptor&, const value_type&,
                            std::false_type)
461
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
462
        throw ValueException("property is read-only");
463
464
    }

465
    size_t get_hash() const
466
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
467
        return std::hash<size_t>()(size_t(this));
468
469
    }

470
    std::string get_type() const
471
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
472
473
474
        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)
475
476
            return gcc_demangle(typeid(value_type).name());
        else
Tiago Peixoto's avatar
Tiago Peixoto committed
477
            return type_names[boost::mpl::find<value_types,
478
                                               value_type>::type::pos::value];
479
480
    }

481
    boost::any get_map() const
482
483
484
485
    {
        return _pmap;
    }

486
    boost::any get_dynamic_map() const
487
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
488
        return (boost::dynamic_property_map*)
489
490
491
492
            (new boost::detail::dynamic_property_map_adaptor<PropertyMap>
             (_pmap));
    }

493
    boost::python::object get_array(size_t size)
494
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
495
496
497
498
499
500
501
502
        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 >
503
            ::type>::type isnt_vector_map;
504
        return get_array_dispatch(size, isnt_vector_map());
505
506
    }

507
    boost::python::object get_array_dispatch(size_t size, boost::mpl::bool_<false>)
508
509
510
511
512
    {
        _pmap.reserve(size);
        return wrap_vector_not_owned(_pmap.get_storage());
    }

513
    boost::python::object get_array_dispatch(size_t, boost::mpl::bool_<true>)
514
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
515
        return boost::python::object();
516
517
    }

518
    bool is_writable() const
519
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
520
521
        return std::is_convertible<typename boost::property_traits<PropertyMap>::category,
                                   boost::writable_property_map_tag>::value;
522
523
    }

524
private:
525
    PropertyMap _pmap; // hold an internal copy, since it's cheap
526
527
528
};


529
530
531
532
533
534
535
536
//
// 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
537
                     boost::any pmap, boost::python::object& new_prop, bool& found) const
538
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
539
        size_t i = boost::mpl::find<value_types,ValueType>::type::pos::value;
540
541
        if (type_name == type_names[i])
        {
542
543
            typedef typename property_map_type::apply<ValueType, IndexMap>::type
                map_t;
544
545
546
547
            map_t prop;
            if (pmap.empty())
                prop = map_t(index);
            else
Tiago Peixoto's avatar
Tiago Peixoto committed
548
                prop = boost::any_cast<map_t>(pmap);
549

Tiago Peixoto's avatar
Tiago Peixoto committed
550
            new_prop = boost::python::object(PythonPropertyMap<map_t>(prop));
551
552
553
554
555
556
            found = true;
        }
    }
};

template <class IndexMap>
Tiago Peixoto's avatar
Tiago Peixoto committed
557
558
boost::python::object new_property(const string& type, IndexMap index_map,
                                   boost::any pmap)
559
{
Tiago Peixoto's avatar
Tiago Peixoto committed
560
    boost::python::object prop;
561
    bool found = false;
Tiago Peixoto's avatar
Tiago Peixoto committed
562
563
564
565
    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)));
566
    if (!found)
Tiago Peixoto's avatar
Tiago Peixoto committed
567
        throw ValueException("Invalid property type: " + type);
568
569
570
    return prop;
}

571
572
573
574
575
576
577
578
579
//
// Python IO streams (minimal access to c++ streams)
//

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

580
    void write(const std::string& s, size_t n)
581
582
583
584
    {
        _s.write(s.c_str(), long(n));
    }

585
    void flush()
586
587
588
589
590
591
592
593
594
595
596
597
598
    {
        _s.flush();
    }

private:
    std::ostream& _s;
};

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

599
    boost::python::object read(size_t n)
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
    {
        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;
};


622
623
624
} //graph_tool namespace

#endif