graph_python_interface.hh 16.8 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:
Tiago Peixoto's avatar
Tiago Peixoto committed
70
    PythonIterator(const boost::python::object& g, std::pair<Iterator,Iterator> e)
71
        : _g(g), _e(e) {}
72
    Descriptor Next()
73
    {
74
        if (_e.first == _e.second)
Tiago Peixoto's avatar
Tiago Peixoto committed
75
76
            boost::python::objects::stop_iteration_error();
        if (_g() == boost::python::object())
77
78
79
            throw GraphException("The corresponding graph object has been"
                                 " deleted during iteration!");
        Descriptor e(_g, *_e.first);
80
81
        ++_e.first;
        return e;
82
83
    }
private:
Tiago Peixoto's avatar
Tiago Peixoto committed
84
    boost::python::object _g;
85
    std::pair<Iterator,Iterator> _e;
Tiago Peixoto's avatar
Tiago Peixoto committed
86
87
88
};


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

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

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

113
    void SetValid(bool valid)
114
    {
115
116
        _valid = valid;
    }
117

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

Tiago Peixoto's avatar
Tiago Peixoto committed
125
    boost::python::object GetGraph() const
126
127
128
129
    {
        return _g();
    }

130
    GraphInterface::vertex_t GetDescriptor() const
131
132
133
134
    {
        return _v;
    }

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

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

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

169
    // provide iterator support for out_edges
170

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

Tiago Peixoto's avatar
Tiago Peixoto committed
186
    boost::python::object OutEdges() const
Tiago Peixoto's avatar
Tiago Peixoto committed
187
    {
188
        CheckValid();
Tiago Peixoto's avatar
Tiago Peixoto committed
189
190
191
192
        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)))();
193
        return iter;
194
    }
195

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

Tiago Peixoto's avatar
Tiago Peixoto committed
211
    boost::python::object InEdges() const
212
    {
213
        CheckValid();
Tiago Peixoto's avatar
Tiago Peixoto committed
214
215
216
217
218
        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)))();
219
        return iter;
Tiago Peixoto's avatar
Tiago Peixoto committed
220
    }
221

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

228
    size_t GetHash() const
229
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
230
        return std::hash<size_t>()(_v);
231
232
    }

233
234
    size_t GetIndex() const
    {
235
        CheckValid();
Tiago Peixoto's avatar
Tiago Peixoto committed
236
        GraphInterface& gi = boost::python::extract<GraphInterface&>(_g().attr("_Graph__graph"));
237
        return gi._vertex_index[_v];
238
239
    }

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

247
    bool operator!=(const PythonVertex& other) const
248
    {
249
250
        CheckValid();
        other.CheckValid();
251
        return other._v != _v;
252
253
    }

254
private:
Tiago Peixoto's avatar
Tiago Peixoto committed
255
    boost::python::object _g;
256
    GraphInterface::vertex_t _v;
257
    bool _valid;
258
};
259

260
// below are classes related to the PythonEdge type
261

262
263
class EdgeBase {}; // useful to unite all edge types

264
template <class Graph>
265
class PythonEdge : public EdgeBase
266
267
{
public:
Tiago Peixoto's avatar
Tiago Peixoto committed
268
269
    typedef typename boost::graph_traits<Graph>::edge_descriptor edge_descriptor;
    PythonEdge(const boost::python::object& g, edge_descriptor e)
270
        : _g(g), _e(e), _valid(true)
271
272
273
274
275
    {
        CheckValid();
    }

    bool IsValid() const
Tiago Peixoto's avatar
Tiago Peixoto committed
276
    {
277
        if (_g().ptr() == Py_None || !_valid)
278
            return false;
Tiago Peixoto's avatar
Tiago Peixoto committed
279
        GraphInterface& gi = boost::python::extract<GraphInterface&>(_g().attr("_Graph__graph"));
280
        GraphInterface::edge_t e(_e);
281
282
        bool valid = PythonVertex(_g, source(e, *gi._mg)).IsValid() &&
            PythonVertex(_g, target(e, *gi._mg)).IsValid();
283
284
285

        if (valid)
            valid = gi.GetEdgeIndex()[e] <= gi.GetMaxEdgeIndex();
286
        return valid;
287
288
289
290
291
292
293
294
295
    }

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

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

Tiago Peixoto's avatar
Tiago Peixoto committed
300
    boost::python::object GetGraph() const
301
302
303
304
    {
        return _g();
    }

305
    GraphInterface::edge_t GetDescriptor() const
306
307
308
309
    {
        return _e;
    }

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

Tiago Peixoto's avatar
Tiago Peixoto committed
322
    boost::python::object GetSource() const
Tiago Peixoto's avatar
Tiago Peixoto committed
323
    {
324
        CheckValid();
Tiago Peixoto's avatar
Tiago Peixoto committed
325
326
327
328
329
        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)))();
330
        return v;
Tiago Peixoto's avatar
Tiago Peixoto committed
331
332
    }

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

Tiago Peixoto's avatar
Tiago Peixoto committed
345
    boost::python::object GetTarget() const
Tiago Peixoto's avatar
Tiago Peixoto committed
346
    {
347
        CheckValid();
Tiago Peixoto's avatar
Tiago Peixoto committed
348
349
350
351
        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)))();
352
        return v;
Tiago Peixoto's avatar
Tiago Peixoto committed
353
354
    }

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

362
    size_t GetHash() const
Tiago Peixoto's avatar
Tiago Peixoto committed
363
    {
364
        CheckValid();
Tiago Peixoto's avatar
Tiago Peixoto committed
365
366
        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
367
368
    }

369
    bool operator==(const PythonEdge& other) const
Tiago Peixoto's avatar
Tiago Peixoto committed
370
    {
371
        CheckValid();
372
        other.CheckValid();
373
        return other._e == _e;
Tiago Peixoto's avatar
Tiago Peixoto committed
374
    }
375

376
    bool operator!=(const PythonEdge& other) const
377
    {
378
        CheckValid();
379
        other.CheckValid();
380
        return other._e != _e;
381
382
383
    }

private:
Tiago Peixoto's avatar
Tiago Peixoto committed
384
    boost::python::object _g;
385
    edge_descriptor _e;
386
    bool _valid;
387
388
};

389
390
391
392
393
394
395
396
397
398
// 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
399
400
401
402
403
404
405
406
        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
407
                >::type,
Tiago Peixoto's avatar
Tiago Peixoto committed
408
409
            boost::mpl::bool_<true>,
            boost::mpl::bool_<false> >::type type;
410
411
412
413
    };
};

template <class PropertyMap>
414
415
416
class PythonPropertyMap
{
public:
417
418
    PythonPropertyMap(const PropertyMap& pmap)
        : _pmap(pmap) {}
419

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

Tiago Peixoto's avatar
Tiago Peixoto committed
422
    typedef typename boost::mpl::if_<
423
424
425
426
        typename return_reference::apply<value_type>::type,
        value_type&,
        value_type>::type reference;

427
    template <class PythonDescriptor>
428
    reference GetValue(const PythonDescriptor& key)
429
    {
430
        key.CheckValid();
431
        return get(_pmap, key.GetDescriptor());
432
433
    }

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

444
445
    template <class PythonDescriptor>
    void set_value(const PythonDescriptor& key, const value_type& val,
Tiago Peixoto's avatar
Tiago Peixoto committed
446
                   std::true_type)
447
    {
448
449
        key.CheckValid();
        put(_pmap, key.GetDescriptor(), val);
450
451
    }

452
    template <class PythonDescriptor>
453
    void set_value(const PythonDescriptor& key, const value_type& val,
Tiago Peixoto's avatar
Tiago Peixoto committed
454
                   std::false_type)
455
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
456
        throw ValueException("property is read-only");
457
458
459
460
    }

    size_t GetHash() const
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
461
        return std::hash<size_t>()(size_t(this));
462
463
464
465
    }

    std::string GetType() const
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
466
467
468
        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)
469
470
            return gcc_demangle(typeid(value_type).name());
        else
Tiago Peixoto's avatar
Tiago Peixoto committed
471
            return type_names[boost::mpl::find<value_types,
472
                                        value_type>::type::pos::value];
473
474
    }

475
    boost::any GetMap() const
476
477
478
479
    {
        return _pmap;
    }

480
481
    boost::any GetDynamicMap() const
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
482
        return (boost::dynamic_property_map*)
483
484
485
486
            (new boost::detail::dynamic_property_map_adaptor<PropertyMap>
             (_pmap));
    }

Tiago Peixoto's avatar
Tiago Peixoto committed
487
    boost::python::object GetArray(size_t size)
488
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
489
490
491
492
493
494
495
496
        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 >
497
498
            ::type>::type isnt_vector_map;
        return get_array(_pmap, size, isnt_vector_map());
499
500
    }

Tiago Peixoto's avatar
Tiago Peixoto committed
501
    boost::python::object get_array(PropertyMap pmap, size_t size, boost::mpl::bool_<false>)
502
503
504
505
506
    {
        _pmap.reserve(size);
        return wrap_vector_not_owned(_pmap.get_storage());
    }

Tiago Peixoto's avatar
Tiago Peixoto committed
507
    boost::python::object get_array(PropertyMap pmap, size_t size, boost::mpl::bool_<true>)
508
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
509
        return boost::python::object();
510
511
    }

512
513
    bool IsWritable() const
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
514
515
        return std::is_convertible<typename boost::property_traits<PropertyMap>::category,
                                   boost::writable_property_map_tag>::value;
516
517
    }

518
private:
519
    PropertyMap _pmap; // hold an internal copy, since it's cheap
520
521
522
};


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

Tiago Peixoto's avatar
Tiago Peixoto committed
544
            new_prop = boost::python::object(PythonPropertyMap<map_t>(prop));
545
546
547
548
549
550
            found = true;
        }
    }
};

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

565
566
567
} //graph_tool namespace

#endif