graph_python_interface.hh 16.6 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
} //graph_tool namespace

#endif