graph_python_interface.hh 15.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-2013 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
24
25
26
27
28
29
#include <boost/python.hpp>
#include <boost/python/type_id.hpp>

namespace boost
{
    size_t hash_value(const boost::python::object& o);
}


30
31
#include <boost/graph/graph_traits.hpp>
#include <boost/mpl/logical.hpp>
32
#include <boost/functional/hash.hpp>
33
#include <boost/iterator/iterator_facade.hpp>
34

35
36
#include "graph.hh"
#include "graph_filtering.hh"
37
#include "graph_selectors.hh"
38
#include "numpy_bind.hh"
39

40

41
// this file includes a simple python interface for the internally kept
42
43
44
45
// 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).
46

47
48
49
50
namespace graph_tool
{
using namespace boost;

51
52
// generic iterator adaptor which can be used to iterate vertices, edges,
// out_edges and in_edges through python
53
template <class Descriptor, class Iterator>
54
class PythonIterator
55
{
56
public:
57
58
    PythonIterator(const python::object& g, std::pair<Iterator,Iterator> e)
        : _g(g), _e(e) {}
59
    Descriptor Next()
60
    {
61
62
        if (_e.first == _e.second)
            python::objects::stop_iteration_error();
63
64
65
66
        if (_g() == python::object())
            throw GraphException("The corresponding graph object has been"
                                 " deleted during iteration!");
        Descriptor e(_g, *_e.first);
67
68
        ++_e.first;
        return e;
69
70
    }
private:
71
    python::object _g;
72
    std::pair<Iterator,Iterator> _e;
Tiago Peixoto's avatar
Tiago Peixoto committed
73
74
75
};


76
// forward declaration of PythonEdge
77
78
template <class Graph>
class PythonEdge;
79

80
// below are classes related to the PythonVertex type
81
class PythonVertex
82
83
{
public:
84
85
    PythonVertex(const python::object& g, GraphInterface::vertex_t v):
        _g(g), _v(v), _valid(true)
86
87
88
89
90
91
    {
        CheckValid();
    }

    bool IsValid() const
    {
92
93
        if (_g().ptr() == Py_None)
            return false;
94
        GraphInterface& gi = python::extract<GraphInterface&>(_g().attr("_Graph__graph"));
95
96
        return _valid &&
            (_v != graph_traits<GraphInterface::multigraph_t>::null_vertex()) &&
97
            (_v < num_vertices(*gi._mg));
98
    }
99

100
    void SetValid(bool valid)
101
    {
102
103
        _valid = valid;
    }
104

105
106
107
    void CheckValid() const
    {
        if (!IsValid())
108
109
            throw ValueException("invalid vertex descriptor: " +
                                 lexical_cast<string>(_v));
110
    }
111

112
113
114
115
116
    python::object GetGraph() const
    {
        return _g();
    }

117
    GraphInterface::vertex_t GetDescriptor() const
118
119
120
121
    {
        return _v;
    }

122
123
124
125
    template <class DegSelector>
    struct get_degree
    {
        template<class Graph>
126
        void operator()(const Graph& g,
127
128
129
                        typename graph_traits<Graph>::vertex_descriptor v,
                        size_t& deg) const
        {
130
            deg = DegSelector()(v, g);
131
132
133
        }
    };

134
    size_t GetInDegree() const
135
    {
136
        CheckValid();
137
        GraphInterface& gi = python::extract<GraphInterface&>(_g().attr("_Graph__graph"));
138
        size_t in_deg;
139
140
141
        run_action<>()(gi, bind<void>(get_degree<in_degreeS>(),
                                      _1, _v,
                                      ref(in_deg)))();
142
        return in_deg;
143
    }
144

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

155
    // provide iterator support for out_edges
156

157
158
159
    struct get_out_edges
    {
        template<class Graph>
160
        void operator()(const Graph& g, const python::object& pg,
161
162
163
164
165
166
167
                        typename graph_traits<Graph>::vertex_descriptor v,
                        python::object& iter) const
        {
            typedef typename graph_traits<Graph>::out_edge_iterator
                out_edge_iterator;
            iter = python::object(PythonIterator<PythonEdge<Graph>,
                                                 out_edge_iterator>
168
                                  (pg, out_edges(v, g)));
169
170
171
        }
    };

172
    python::object OutEdges() const
Tiago Peixoto's avatar
Tiago Peixoto committed
173
    {
174
        CheckValid();
175
        GraphInterface& gi = python::extract<GraphInterface&>(_g().attr("_Graph__graph"));
176
        python::object iter;
177
178
        run_action<>()(gi, bind<void>(get_out_edges(), _1,
                                      ref(_g), _v, ref(iter)))();
179
        return iter;
180
    }
181

182
183
184
    struct get_in_edges
    {
        template<class Graph>
185
        void operator()(const Graph& g, const python::object& pg,
186
187
188
189
190
191
192
                        typename graph_traits<Graph>::vertex_descriptor v,
                        python::object& iter) const
        {
            typedef typename in_edge_iteratorS<Graph>::type
                in_edge_iterator;
            iter = python::object
                (PythonIterator<PythonEdge<Graph>,in_edge_iterator>
193
                 (pg, in_edge_iteratorS<Graph>::get_edges(v, g)));
194
195
196
        }
    };

197
    python::object InEdges() const
198
    {
199
        CheckValid();
200
        GraphInterface& gi = python::extract<GraphInterface&>(_g().attr("_Graph__graph"));
201
        python::object iter;
202
203
        run_action<>()(gi, bind<void>(get_in_edges(), _1, ref(_g), _v,
                                      ref(iter)))();
204
        return iter;
Tiago Peixoto's avatar
Tiago Peixoto committed
205
    }
206

207
208
    std::string GetString() const
    {
209
        CheckValid();
210
211
212
        return lexical_cast<std::string>(_v);
    }

213
    size_t GetHash() const
214
    {
215
        return hash<size_t>()(_v);
216
217
    }

218
219
    size_t GetIndex() const
    {
220
        CheckValid();
221
        GraphInterface& gi = python::extract<GraphInterface&>(_g().attr("_Graph__graph"));
222
        return gi._vertex_index[_v];
223
224
    }

225
    bool operator==(const PythonVertex& other) const
226
    {
227
228
        CheckValid();
        other.CheckValid();
229
        return other._v == _v;
230
    }
231

232
    bool operator!=(const PythonVertex& other) const
233
    {
234
235
        CheckValid();
        other.CheckValid();
236
        return other._v != _v;
237
238
    }

239
private:
240
    python::object _g;
241
    GraphInterface::vertex_t _v;
242
    bool _valid;
243
};
244

245
// below are classes related to the PythonEdge type
246

247
248
class EdgeBase {}; // useful to unite all edge types

249
template <class Graph>
250
class PythonEdge : public EdgeBase
251
252
{
public:
Tiago Peixoto's avatar
Tiago Peixoto committed
253
    typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
254
255
    PythonEdge(const python::object& g, edge_descriptor e)
        : _g(g), _e(e), _valid(true)
256
257
258
259
260
    {
        CheckValid();
    }

    bool IsValid() const
Tiago Peixoto's avatar
Tiago Peixoto committed
261
    {
262
        if (_g().ptr() == Py_None || !_valid)
263
            return false;
264
        GraphInterface& gi = python::extract<GraphInterface&>(_g().attr("_Graph__graph"));
265
        GraphInterface::edge_t e(_e);
266
267
        bool valid = PythonVertex(_g, source(e, *gi._mg)).IsValid() &&
            PythonVertex(_g, target(e, *gi._mg)).IsValid();
268
269
270

        if (valid)
            valid = gi.GetEdgeIndex()[e] <= gi.GetMaxEdgeIndex();
271
        return valid;
272
273
274
275
276
277
278
279
280
    }

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

    void CheckValid() const
    {
281
        if (!IsValid())
Tiago Peixoto's avatar
Tiago Peixoto committed
282
            throw ValueException("invalid edge descriptor");
Tiago Peixoto's avatar
Tiago Peixoto committed
283
284
    }

285
286
287
288
289
    python::object GetGraph() const
    {
        return _g();
    }

290
    GraphInterface::edge_t GetDescriptor() const
291
292
293
294
    {
        return _e;
    }

295
296
297
    struct get_source
    {
        template<class GraphType>
298
        void operator()(const GraphType& g, const python::object& pg,
299
300
301
                        const edge_descriptor& edge, python::object& vertex)
            const
        {
302
303
            typedef typename graph_traits<GraphType>::edge_descriptor edge_t;
            vertex = python::object(PythonVertex(pg, source(edge_t(edge), g)));
304
305
        }
    };
306

307
    python::object GetSource() const
Tiago Peixoto's avatar
Tiago Peixoto committed
308
    {
309
        CheckValid();
310
        GraphInterface& gi = python::extract<GraphInterface&>(_g().attr("_Graph__graph"));
311
        python::object v;
312
313
        run_action<>()(gi, bind<void>(get_source(), _1, ref(_g), ref(_e),
                                      ref(v)))();
314
        return v;
Tiago Peixoto's avatar
Tiago Peixoto committed
315
316
    }

317
318
319
    struct get_target
    {
        template<class GraphType>
320
321
322
        void operator()(const GraphType& g, const python::object& pg,
                        const edge_descriptor& edge, python::object& vertex)
            const
323
        {
324
325
            typedef typename graph_traits<GraphType>::edge_descriptor edge_t;
            vertex = python::object(PythonVertex(pg, target(edge_t(edge), g)));
326
327
        }
    };
328

329
    python::object GetTarget() const
Tiago Peixoto's avatar
Tiago Peixoto committed
330
    {
331
        CheckValid();
332
        GraphInterface& gi = python::extract<GraphInterface&>(_g().attr("_Graph__graph"));
333
        python::object v;
334
335
        run_action<>()(gi, bind<void>(get_target(), _1, ref(_g), ref(_e),
                                      ref(v)))();
336
        return v;
Tiago Peixoto's avatar
Tiago Peixoto committed
337
338
    }

339
340
    std::string GetString() const
    {
341
342
        PythonVertex src = python::extract<PythonVertex>(GetSource());
        PythonVertex tgt = python::extract<PythonVertex>(GetTarget());
343
        return "(" + src.GetString() + ", " + tgt.GetString() + ")";
344
345
    }

346
    size_t GetHash() const
Tiago Peixoto's avatar
Tiago Peixoto committed
347
    {
348
        CheckValid();
349
        GraphInterface& gi = python::extract<GraphInterface&>(_g().attr("_Graph__graph"));
350
        return hash<size_t>()(gi._edge_index[_e]);
Tiago Peixoto's avatar
Tiago Peixoto committed
351
352
    }

353
    bool operator==(const PythonEdge& other) const
Tiago Peixoto's avatar
Tiago Peixoto committed
354
    {
355
        CheckValid();
356
        other.CheckValid();
357
        return other._e == _e;
Tiago Peixoto's avatar
Tiago Peixoto committed
358
    }
359

360
    bool operator!=(const PythonEdge& other) const
361
    {
362
        CheckValid();
363
        other.CheckValid();
364
        return other._e != _e;
365
366
367
    }

private:
368
    python::object _g;
369
    edge_descriptor _e;
370
    bool _valid;
371
372
};

373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
// 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

        typedef typename mpl::if_<
            typename mpl::and_<
                is_class<ValueType>,
                typename mpl::and_<
                    typename mpl::not_<is_same<ValueType,
                                               string> >::type,
                    typename mpl::not_<is_same<ValueType,
                                               python::object> >::type>::type
                >::type,
            mpl::bool_<true>,
            mpl::bool_<false> >::type type;
    };
};

template <class PropertyMap>
398
399
400
class PythonPropertyMap
{
public:
401
402
    PythonPropertyMap(const PropertyMap& pmap)
        : _pmap(pmap) {}
403

404
405
406
407
408
409
410
    typedef typename property_traits<PropertyMap>::value_type value_type;

    typedef typename mpl::if_<
        typename return_reference::apply<value_type>::type,
        value_type&,
        value_type>::type reference;

411
    template <class PythonDescriptor>
412
    reference GetValue(const PythonDescriptor& key)
413
    {
414
        key.CheckValid();
415
        return get(_pmap, key.GetDescriptor());
416
417
    }

418
419
    // in this case, val should be a copy, not a reference. This is to avoid a
    // problem with vector-valued property maps
420
    template <class PythonDescriptor>
421
    void SetValue(const PythonDescriptor& key, value_type val)
422
    {
423
424
425
426
        set_value(key, val,
                  is_convertible<
                  typename property_traits<PropertyMap>::category,
                  writable_property_map_tag>());
427
428
    }

429
430
431
    template <class PythonDescriptor>
    void set_value(const PythonDescriptor& key, const value_type& val,
                   true_type)
432
    {
433
434
        key.CheckValid();
        put(_pmap, key.GetDescriptor(), val);
435
436
    }

437
    template <class PythonDescriptor>
438
439
    void set_value(const PythonDescriptor& key, const value_type& val,
                   false_type)
440
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
441
        throw ValueException("property is read-only");
442
443
444
445
    }

    size_t GetHash() const
    {
446
        return hash<size_t>()(size_t(this));
447
448
449
450
    }

    std::string GetType() const
    {
451
452
453
454
455
456
457
        using python::detail::gcc_demangle;
        if (is_same<typename mpl::find<value_types,value_type>::type,
                    typename mpl::end<value_types>::type>::value)
            return gcc_demangle(typeid(value_type).name());
        else
            return type_names[mpl::find<value_types,
                                        value_type>::type::pos::value];
458
459
    }

460
    boost::any GetMap() const
461
462
463
464
    {
        return _pmap;
    }

465
466
467
468
469
470
471
    boost::any GetDynamicMap() const
    {
        return (dynamic_property_map*)
            (new boost::detail::dynamic_property_map_adaptor<PropertyMap>
             (_pmap));
    }

472
473
474
    python::object GetArray(size_t size)
    {
        typedef typename mpl::or_<
475
476
477
478
479
480
481
482
483
              typename mpl::or_<
                   is_same<PropertyMap,
                           GraphInterface::vertex_index_map_t>,
                   is_same<PropertyMap,
                           GraphInterface::edge_index_map_t> >::type,
              typename mpl::not_<
                  typename mpl::has_key<numpy_types, value_type>::type >
            ::type>::type isnt_vector_map;
        return get_array(_pmap, size, isnt_vector_map());
484
485
486
487
488
489
490
491
492
493
494
495
496
    }

    python::object get_array(PropertyMap pmap, size_t size, mpl::bool_<false>)
    {
        _pmap.reserve(size);
        return wrap_vector_not_owned(_pmap.get_storage());
    }

    python::object get_array(PropertyMap pmap, size_t size, mpl::bool_<true>)
    {
        return python::object();
    }

497
498
    bool IsWritable() const
    {
499
500
        return is_convertible<typename property_traits<PropertyMap>::category,
                              writable_property_map_tag>::value;
501
502
    }

503
private:
504
    PropertyMap _pmap; // hold an internal copy, since it's cheap
505
506
507
};


508
509
510
511
512
513
514
515
//
// Create new properties
//

struct new_property_map
{
    template <class ValueType, class IndexMap>
    void operator()(ValueType, IndexMap index, const string& type_name,
516
                     boost::any pmap, python::object& new_prop, bool& found) const
517
518
519
520
    {
        size_t i = mpl::find<value_types,ValueType>::type::pos::value;
        if (type_name == type_names[i])
        {
521
522
            typedef typename property_map_type::apply<ValueType, IndexMap>::type
                map_t;
523
524
525
526
527
528
            map_t prop;
            if (pmap.empty())
                prop = map_t(index);
            else
                prop = any_cast<map_t>(pmap);

529
530
531
532
533
534
535
            new_prop = python::object(PythonPropertyMap<map_t>(prop));
            found = true;
        }
    }
};

template <class IndexMap>
536
537
python::object new_property(const string& type, IndexMap index_map,
                            boost::any pmap)
538
539
540
{
    python::object prop;
    bool found = false;
541
    mpl::for_each<value_types>(bind<void>(new_property_map(), _1, index_map,
542
                                          ref(type), pmap, ref(prop), ref(found)));
543
    if (!found)
Tiago Peixoto's avatar
Tiago Peixoto committed
544
        throw ValueException("Invalid property type: " + type);
545
546
547
    return prop;
}

548
549
550
} //graph_tool namespace

#endif