graph_python_interface.hh 17.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-2014 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
33
34
35
36
37
#include <functional>

namespace std
{
    template<>
    struct hash<boost::python::object>
    {
        size_t operator()(const boost::python::object& o) const
        {
            return boost::python::extract<size_t>(o.attr("__hash__")());
        }
    };
}

38
39
40
41
42
namespace boost
{
    size_t hash_value(const boost::python::object& o);
}

43
44
#include <boost/graph/graph_traits.hpp>
#include <boost/mpl/logical.hpp>
45
#include <boost/iterator/iterator_facade.hpp>
46

Tiago Peixoto's avatar
Tiago Peixoto committed
47
48
#include <type_traits>

49
50
#include "graph.hh"
#include "graph_filtering.hh"
51
#include "graph_selectors.hh"
52
#include "numpy_bind.hh"
53

54

55
// this file includes a simple python interface for the internally kept
56
57
58
59
// 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).
60

61
62
63
namespace graph_tool
{

64
65
// generic iterator adaptor which can be used to iterate vertices, edges,
// out_edges and in_edges through python
66
template <class Descriptor, class Iterator>
67
class PythonIterator
68
{
69
public:
70
71
72
    PythonIterator(const boost::python::object& g,
                   std::pair<Iterator,Iterator> e)
        : _wg(g), _g(g()), _e(e) {}
73
    Descriptor Next()
74
    {
75
        if (_e.first == _e.second)
Tiago Peixoto's avatar
Tiago Peixoto committed
76
            boost::python::objects::stop_iteration_error();
77
        Descriptor e(_wg, *_e.first);
78
79
        ++_e.first;
        return e;
80
81
    }
private:
82
    boost::python::object _wg;
Tiago Peixoto's avatar
Tiago Peixoto committed
83
    boost::python::object _g;
84
    std::pair<Iterator,Iterator> _e;
Tiago Peixoto's avatar
Tiago Peixoto committed
85
86
87
};


88
// forward declaration of PythonEdge
89
90
template <class Graph>
class PythonEdge;
91

92
// below are classes related to the PythonVertex type
93
class PythonVertex
94
95
{
public:
Tiago Peixoto's avatar
Tiago Peixoto committed
96
    PythonVertex(const boost::python::object& g, GraphInterface::vertex_t v):
97
        _g(g), _v(v), _valid(true)
98
    {}
99
100
101

    bool IsValid() const
    {
102
103
        if (_g().ptr() == Py_None)
            return false;
Tiago Peixoto's avatar
Tiago Peixoto committed
104
        GraphInterface& gi = boost::python::extract<GraphInterface&>(_g().attr("_Graph__graph"));
105
        return _valid &&
Tiago Peixoto's avatar
Tiago Peixoto committed
106
            (_v != boost::graph_traits<GraphInterface::multigraph_t>::null_vertex()) &&
107
            (_v < num_vertices(*gi._mg));
108
    }
109

110
    void SetValid(bool valid)
111
    {
112
113
        _valid = valid;
    }
114

115
116
117
    void CheckValid() const
    {
        if (!IsValid())
118
            throw ValueException("invalid vertex descriptor: " +
Tiago Peixoto's avatar
Tiago Peixoto committed
119
                                 boost::lexical_cast<string>(_v));
120
    }
121

Tiago Peixoto's avatar
Tiago Peixoto committed
122
    boost::python::object GetGraph() const
123
124
125
126
    {
        return _g();
    }

127
    GraphInterface::vertex_t GetDescriptor() const
128
129
130
131
    {
        return _v;
    }

132
133
134
135
    template <class DegSelector>
    struct get_degree
    {
        template<class Graph>
136
        void operator()(const Graph& g,
Tiago Peixoto's avatar
Tiago Peixoto committed
137
                        typename boost::graph_traits<Graph>::vertex_descriptor v,
138
139
                        size_t& deg) const
        {
140
            deg = DegSelector()(v, g);
141
142
143
        }
    };

144
    size_t GetInDegree() const
145
    {
146
        CheckValid();
Tiago Peixoto's avatar
Tiago Peixoto committed
147
        GraphInterface& gi = boost::python::extract<GraphInterface&>(_g().attr("_Graph__graph"));
148
        size_t in_deg;
Tiago Peixoto's avatar
Tiago Peixoto committed
149
150
151
        run_action<>()(gi, std::bind(get_degree<in_degreeS>(),
                                     std::placeholders::_1, _v,
                                     std::ref(in_deg)))();
152
        return in_deg;
153
    }
154

155
    size_t GetOutDegree() const
156
    {
157
        CheckValid();
Tiago Peixoto's avatar
Tiago Peixoto committed
158
        GraphInterface& gi = boost::python::extract<GraphInterface&>(_g().attr("_Graph__graph"));
159
        size_t out_deg;
Tiago Peixoto's avatar
Tiago Peixoto committed
160
161
162
        run_action<>()(gi, std::bind(get_degree<out_degreeS>(),
                                     std::placeholders::_1, _v,
                                     std::ref(out_deg)))();
163
        return out_deg;
Tiago Peixoto's avatar
Tiago Peixoto committed
164
165
    }

166
    // provide iterator support for out_edges
167

168
169
170
    struct get_out_edges
    {
        template<class Graph>
Tiago Peixoto's avatar
Tiago Peixoto committed
171
172
173
        void operator()(const Graph& g, const boost::python::object& pg,
                        typename boost::graph_traits<Graph>::vertex_descriptor v,
                        boost::python::object& iter) const
174
        {
Tiago Peixoto's avatar
Tiago Peixoto committed
175
            typedef typename boost::graph_traits<Graph>::out_edge_iterator
176
                out_edge_iterator;
Tiago Peixoto's avatar
Tiago Peixoto committed
177
            iter = boost::python::object(PythonIterator<PythonEdge<Graph>,
178
                                                 out_edge_iterator>
179
                                  (pg, out_edges(v, g)));
180
181
182
        }
    };

Tiago Peixoto's avatar
Tiago Peixoto committed
183
    boost::python::object OutEdges() const
Tiago Peixoto's avatar
Tiago Peixoto committed
184
    {
185
        CheckValid();
Tiago Peixoto's avatar
Tiago Peixoto committed
186
187
188
189
        GraphInterface& gi = boost::python::extract<GraphInterface&>(_g().attr("_Graph__graph"));
        boost::python::object iter;
        run_action<>()(gi, std::bind(get_out_edges(), std::placeholders::_1,
                                     std::ref(_g), _v, std::ref(iter)))();
190
        return iter;
191
    }
192

193
194
195
    struct get_in_edges
    {
        template<class Graph>
Tiago Peixoto's avatar
Tiago Peixoto committed
196
197
198
        void operator()(const Graph& g, const boost::python::object& pg,
                        typename boost::graph_traits<Graph>::vertex_descriptor v,
                        boost::python::object& iter) const
199
200
201
        {
            typedef typename in_edge_iteratorS<Graph>::type
                in_edge_iterator;
Tiago Peixoto's avatar
Tiago Peixoto committed
202
            iter = boost::python::object
203
                (PythonIterator<PythonEdge<Graph>,in_edge_iterator>
204
                 (pg, in_edge_iteratorS<Graph>::get_edges(v, g)));
205
206
207
        }
    };

Tiago Peixoto's avatar
Tiago Peixoto committed
208
    boost::python::object InEdges() const
209
    {
210
        CheckValid();
Tiago Peixoto's avatar
Tiago Peixoto committed
211
212
213
214
215
        GraphInterface& gi = boost::python::extract<GraphInterface&>(_g().attr("_Graph__graph"));
        boost::python::object iter;
        run_action<>()(gi, std::bind(get_in_edges(), placeholders::_1,
                                     std::ref(_g), _v,
                                     std::ref(iter)))();
216
        return iter;
Tiago Peixoto's avatar
Tiago Peixoto committed
217
    }
218

219
220
    std::string GetString() const
    {
221
        CheckValid();
Tiago Peixoto's avatar
Tiago Peixoto committed
222
        return boost::lexical_cast<std::string>(_v);
223
224
    }

225
    size_t GetHash() const
226
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
227
        return std::hash<size_t>()(_v);
228
229
    }

230
231
    size_t GetIndex() const
    {
232
        return _v;
233
234
    }

235
    bool operator==(const PythonVertex& other) const
236
    {
237
        return other._v == _v;
238
    }
239

240
    bool operator!=(const PythonVertex& other) const
241
    {
242
        return other._v != _v;
243
244
    }

245
private:
Tiago Peixoto's avatar
Tiago Peixoto committed
246
    boost::python::object _g;
247
    GraphInterface::vertex_t _v;
248
    bool _valid;
249
};
250

251
// below are classes related to the PythonEdge type
252

253
254
class EdgeBase {}; // useful to unite all edge types

255
template <class Graph>
256
class PythonEdge : public EdgeBase
257
258
{
public:
Tiago Peixoto's avatar
Tiago Peixoto committed
259
260
    typedef typename boost::graph_traits<Graph>::edge_descriptor edge_descriptor;
    PythonEdge(const boost::python::object& g, edge_descriptor e)
261
        : _g(g), _e(e), _valid(true)
262
263
264
265
    {
    }

    bool IsValid() const
Tiago Peixoto's avatar
Tiago Peixoto committed
266
    {
267
268
        boost::python::object g = _g();
        if (g.ptr() == Py_None || !_valid)
269
            return false;
270
        GraphInterface& gi = boost::python::extract<GraphInterface&>(g.attr("_Graph__graph"));
271
        GraphInterface::edge_t e(_e);
272

273
274
275
276
277
278
279
280
281
282
        typename GraphInterface::multigraph_t::vertex_t s, t;
        s = source(e, *gi._mg);
        t = target(e, *gi._mg);

        bool valid = ((s != boost::graph_traits<GraphInterface::multigraph_t>::null_vertex()) &&
                      (s < num_vertices(*gi._mg)) &&
                      (t != boost::graph_traits<GraphInterface::multigraph_t>::null_vertex()) &&
                      (t < num_vertices(*gi._mg)) &&
                      gi.GetEdgeIndex()[e] <= gi.GetMaxEdgeIndex());

283
        return valid;
284
285
286
287
288
289
290
291
292
    }

    void SetValid(bool valid)
    {
        _valid = valid;
    }

    void CheckValid() const
    {
293
        if (!IsValid())
Tiago Peixoto's avatar
Tiago Peixoto committed
294
            throw ValueException("invalid edge descriptor");
Tiago Peixoto's avatar
Tiago Peixoto committed
295
296
    }

Tiago Peixoto's avatar
Tiago Peixoto committed
297
    boost::python::object GetGraph() const
298
299
300
301
    {
        return _g();
    }

302
    GraphInterface::edge_t GetDescriptor() const
303
304
305
306
    {
        return _e;
    }

307
308
309
    struct get_source
    {
        template<class GraphType>
Tiago Peixoto's avatar
Tiago Peixoto committed
310
311
        void operator()(const GraphType& g, const boost::python::object& pg,
                        const edge_descriptor& edge, boost::python::object& vertex)
312
313
            const
        {
Tiago Peixoto's avatar
Tiago Peixoto committed
314
315
            typedef typename boost::graph_traits<GraphType>::edge_descriptor edge_t;
            vertex = boost::python::object(PythonVertex(pg, source(edge_t(edge), g)));
316
317
        }
    };
318

Tiago Peixoto's avatar
Tiago Peixoto committed
319
    boost::python::object GetSource() const
Tiago Peixoto's avatar
Tiago Peixoto committed
320
    {
321
        CheckValid();
Tiago Peixoto's avatar
Tiago Peixoto committed
322
323
324
325
326
        GraphInterface& gi = boost::python::extract<GraphInterface&>(_g().attr("_Graph__graph"));
        boost::python::object v;
        run_action<>()(gi, std::bind(get_source(), std::placeholders::_1,
                                     std::ref(_g), std::ref(_e),
                                     std::ref(v)))();
327
        return v;
Tiago Peixoto's avatar
Tiago Peixoto committed
328
329
    }

330
331
332
    struct get_target
    {
        template<class GraphType>
Tiago Peixoto's avatar
Tiago Peixoto committed
333
334
        void operator()(const GraphType& g, const boost::python::object& pg,
                        const edge_descriptor& edge, boost::python::object& vertex)
335
            const
336
        {
Tiago Peixoto's avatar
Tiago Peixoto committed
337
338
            typedef typename boost::graph_traits<GraphType>::edge_descriptor edge_t;
            vertex = boost::python::object(PythonVertex(pg, target(edge_t(edge), g)));
339
340
        }
    };
341

Tiago Peixoto's avatar
Tiago Peixoto committed
342
    boost::python::object GetTarget() const
Tiago Peixoto's avatar
Tiago Peixoto committed
343
    {
344
        CheckValid();
Tiago Peixoto's avatar
Tiago Peixoto committed
345
346
347
348
        GraphInterface& gi = boost::python::extract<GraphInterface&>(_g().attr("_Graph__graph"));
        boost::python::object v;
        run_action<>()(gi, std::bind(get_target(), std::placeholders::_1,
                                     std::ref(_g), std::ref(_e), std::ref(v)))();
349
        return v;
Tiago Peixoto's avatar
Tiago Peixoto committed
350
351
    }

352
353
    std::string GetString() const
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
354
355
        PythonVertex src = boost::python::extract<PythonVertex>(GetSource());
        PythonVertex tgt = boost::python::extract<PythonVertex>(GetTarget());
356
        return "(" + src.GetString() + ", " + tgt.GetString() + ")";
357
358
    }

359
    size_t GetHash() const
Tiago Peixoto's avatar
Tiago Peixoto committed
360
    {
361
        CheckValid();
Tiago Peixoto's avatar
Tiago Peixoto committed
362
363
        GraphInterface& gi = boost::python::extract<GraphInterface&>(_g().attr("_Graph__graph"));
        return std::hash<size_t>()(gi._edge_index[_e]);
Tiago Peixoto's avatar
Tiago Peixoto committed
364
365
    }

366
    bool operator==(const PythonEdge& other) const
Tiago Peixoto's avatar
Tiago Peixoto committed
367
    {
368
        return other._e == _e;
Tiago Peixoto's avatar
Tiago Peixoto committed
369
    }
370

371
    bool operator!=(const PythonEdge& other) const
372
    {
373
        return other._e != _e;
374
375
376
    }

private:
Tiago Peixoto's avatar
Tiago Peixoto committed
377
    boost::python::object _g;
378
    edge_descriptor _e;
379
    bool _valid;
380
381
};

382
383
384
385
386
387
388
389
390
391
// 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
392
393
394
395
396
397
398
399
        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
400
                >::type,
Tiago Peixoto's avatar
Tiago Peixoto committed
401
402
            boost::mpl::bool_<true>,
            boost::mpl::bool_<false> >::type type;
403
404
405
406
    };
};

template <class PropertyMap>
407
408
409
class PythonPropertyMap
{
public:
410
411
    PythonPropertyMap(const PropertyMap& pmap)
        : _pmap(pmap) {}
412

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

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

420
    template <class PythonDescriptor>
421
    reference GetValue(const PythonDescriptor& key)
422
    {
423
        key.CheckValid();
424
        return get(_pmap, key.GetDescriptor());
425
426
    }

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

437
438
    template <class PythonDescriptor>
    void set_value(const PythonDescriptor& key, const value_type& val,
Tiago Peixoto's avatar
Tiago Peixoto committed
439
                   std::true_type)
440
    {
441
442
        key.CheckValid();
        put(_pmap, key.GetDescriptor(), val);
443
444
    }

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

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

    std::string GetType() const
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
459
460
461
        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)
462
463
            return gcc_demangle(typeid(value_type).name());
        else
Tiago Peixoto's avatar
Tiago Peixoto committed
464
            return type_names[boost::mpl::find<value_types,
465
                                        value_type>::type::pos::value];
466
467
    }

468
    boost::any GetMap() const
469
470
471
472
    {
        return _pmap;
    }

473
474
    boost::any GetDynamicMap() const
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
475
        return (boost::dynamic_property_map*)
476
477
478
479
            (new boost::detail::dynamic_property_map_adaptor<PropertyMap>
             (_pmap));
    }

Tiago Peixoto's avatar
Tiago Peixoto committed
480
    boost::python::object GetArray(size_t size)
481
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
482
483
484
485
486
487
488
489
        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 >
490
491
            ::type>::type isnt_vector_map;
        return get_array(_pmap, size, isnt_vector_map());
492
493
    }

Tiago Peixoto's avatar
Tiago Peixoto committed
494
    boost::python::object get_array(PropertyMap pmap, size_t size, boost::mpl::bool_<false>)
495
496
497
498
499
    {
        _pmap.reserve(size);
        return wrap_vector_not_owned(_pmap.get_storage());
    }

Tiago Peixoto's avatar
Tiago Peixoto committed
500
    boost::python::object get_array(PropertyMap pmap, size_t size, boost::mpl::bool_<true>)
501
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
502
        return boost::python::object();
503
504
    }

505
506
    bool IsWritable() const
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
507
508
        return std::is_convertible<typename boost::property_traits<PropertyMap>::category,
                                   boost::writable_property_map_tag>::value;
509
510
    }

511
private:
512
    PropertyMap _pmap; // hold an internal copy, since it's cheap
513
514
515
};


516
517
518
519
520
521
522
523
//
// 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
524
                     boost::any pmap, boost::python::object& new_prop, bool& found) const
525
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
526
        size_t i = boost::mpl::find<value_types,ValueType>::type::pos::value;
527
528
        if (type_name == type_names[i])
        {
529
530
            typedef typename property_map_type::apply<ValueType, IndexMap>::type
                map_t;
531
532
533
534
            map_t prop;
            if (pmap.empty())
                prop = map_t(index);
            else
Tiago Peixoto's avatar
Tiago Peixoto committed
535
                prop = boost::any_cast<map_t>(pmap);
536

Tiago Peixoto's avatar
Tiago Peixoto committed
537
            new_prop = boost::python::object(PythonPropertyMap<map_t>(prop));
538
539
540
541
542
543
            found = true;
        }
    }
};

template <class IndexMap>
Tiago Peixoto's avatar
Tiago Peixoto committed
544
545
boost::python::object new_property(const string& type, IndexMap index_map,
                                   boost::any pmap)
546
{
Tiago Peixoto's avatar
Tiago Peixoto committed
547
    boost::python::object prop;
548
    bool found = false;
Tiago Peixoto's avatar
Tiago Peixoto committed
549
550
551
552
    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)));
553
    if (!found)
Tiago Peixoto's avatar
Tiago Peixoto committed
554
        throw ValueException("Invalid property type: " + type);
555
556
557
    return prop;
}

558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
//
// Python IO streams (minimal access to c++ streams)
//

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

    void Write(const std::string& s, size_t n)
    {
        _s.write(s.c_str(), long(n));
    }

    void Flush()
    {
        _s.flush();
    }

private:
    std::ostream& _s;
};

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

    boost::python::object Read(size_t n)
    {
        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;
};


609
610
611
} //graph_tool namespace

#endif