graph_python_interface.hh 14 KB
Newer Older
1
2
// graph-tool -- a general graph modification and manipulation thingy
//
Tiago Peixoto's avatar
Tiago Peixoto committed
3
// Copyright (C) 2007  Tiago de Paula Peixoto <tiago@forked.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
#include <boost/lambda/bind.hpp>
22
23
#include <boost/graph/graph_traits.hpp>
#include <boost/mpl/logical.hpp>
24
#include <boost/functional/hash.hpp>
25
#include <boost/iterator/iterator_facade.hpp>
26

27
28
#include "graph.hh"
#include "graph_filtering.hh"
29
#include "graph_selectors.hh"
30
#include "numpy_bind.hh"
31

32
#include <boost/python.hpp>
33
#include <boost/python/type_id.hpp>
34

35
// this file includes a simple python interface for the internally kept
36
37
38
39
// 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).
40

41
42
43
44
namespace graph_tool
{
using namespace boost;

45
46
// generic iterator adaptor which can be used to iterate vertices, edges,
// out_edges and in_edges through python
47
template <class Descriptor, class Iterator>
48
class PythonIterator
49
{
50
public:
51
    PythonIterator(GraphInterface& gi, std::pair<Iterator,Iterator> e)
52
        : _gi(gi), _e(e) {}
53
    Descriptor Next()
54
    {
55
56
        if (_e.first == _e.second)
            python::objects::stop_iteration_error();
57
        Descriptor e(_gi, *_e.first);
58
59
        ++_e.first;
        return e;
60
61
    }
private:
62
    GraphInterface& _gi;
63
    std::pair<Iterator,Iterator> _e;
Tiago Peixoto's avatar
Tiago Peixoto committed
64
65
66
};


67
// forward declaration of PythonEdge
68
69
template <class Graph>
class PythonEdge;
70

71
// below are classes related to the PythonVertex type
72
class PythonVertex
73
74
{
public:
75
    PythonVertex(GraphInterface& gi, GraphInterface::vertex_t v):
76
77
78
79
80
81
82
83
84
85
86
        _gi(gi), _v(v), _valid(true)
    {
        CheckValid();
    }

    bool IsValid() const
    {
        return _valid &&
            (_v != graph_traits<GraphInterface::multigraph_t>::null_vertex()) &&
            (_v < num_vertices(_gi._mg));
    }
87

88
    void SetValid(bool valid)
89
    {
90
91
        _valid = valid;
    }
92

93
94
95
96
    void CheckValid() const
    {
        if (!IsValid())
            throw GraphException("invalid vertex descriptor");
97
    }
98

99
    GraphInterface::vertex_t GetDescriptor() const
100
101
102
103
    {
        return _v;
    }

104
105
106
107
    template <class DegSelector>
    struct get_degree
    {
        template<class Graph>
108
        void operator()(const Graph& g,
109
110
111
                        typename graph_traits<Graph>::vertex_descriptor v,
                        size_t& deg) const
        {
112
            deg = DegSelector()(v, g);
113
114
115
        }
    };

116
    size_t GetInDegree() const
117
    {
118
        CheckValid();
119
120
121
122
123
        size_t in_deg;
        run_action<>()(_gi,lambda::bind<void>(get_degree<in_degreeS>(),
                                              lambda::_1, _v,
                                              lambda::var(in_deg)))();
        return in_deg;
124
    }
125

126
    size_t GetOutDegree() const
127
    {
128
        CheckValid();
129
130
131
132
133
        size_t out_deg;
        run_action<>()(_gi,lambda::bind<void>(get_degree<out_degreeS>(),
                                              lambda::_1, _v,
                                              lambda::var(out_deg)))();
        return out_deg;
Tiago Peixoto's avatar
Tiago Peixoto committed
134
135
    }

136
    // provide iterator support for out_edges
137

138
139
140
    struct get_out_edges
    {
        template<class Graph>
141
        void operator()(const Graph& g, GraphInterface& gi,
142
143
144
145
146
147
148
                        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>
149
                                  (gi, out_edges(v, g)));
150
151
152
153
        }
    };

    python::object
154
    OutEdges() const
Tiago Peixoto's avatar
Tiago Peixoto committed
155
    {
156
        CheckValid();
157
158
159
160
161
        python::object iter;
        run_action<>()(_gi, lambda::bind<void>(get_out_edges(), lambda::_1,
                                               lambda::var(_gi), _v,
                                               lambda::var(iter)))();
        return iter;
162
    }
163

164
165
166
    struct get_in_edges
    {
        template<class Graph>
167
        void operator()(const Graph& g, GraphInterface& gi,
168
169
170
171
172
173
174
                        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>
175
                 (gi, in_edge_iteratorS<Graph>::get_edges(v, g)));
176
177
178
179
        }
    };

    python::object
180
    InEdges() const
181
    {
182
        CheckValid();
183
        python::object iter;
184
        run_action<>()(_gi, lambda::bind<void>(get_in_edges(), lambda::_1,
185
186
187
                                               lambda::var(_gi), _v,
                                               lambda::var(iter)))();
        return iter;
Tiago Peixoto's avatar
Tiago Peixoto committed
188
    }
189

190
191
    std::string GetString() const
    {
192
        CheckValid();
193
194
195
        return lexical_cast<std::string>(_v);
    }

196
    size_t GetHash() const
197
    {
198
        return hash<size_t>()(_gi._vertex_index[_v]);
199
200
    }

201
    bool operator==(const PythonVertex& other) const
202
    {
203
204
        CheckValid();
        other.CheckValid();
205
        return other._v == _v;
206
    }
207

208
    bool operator!=(const PythonVertex& other) const
209
    {
210
211
        CheckValid();
        other.CheckValid();
212
        return other._v != _v;
213
214
    }

215
private:
216
    GraphInterface& _gi;
217
    GraphInterface::vertex_t _v;
218
    bool _valid;
219
};
220

221
// below are classes related to the PythonEdge type
222

223
224
225
226
template <class Graph>
class PythonEdge
{
public:
Tiago Peixoto's avatar
Tiago Peixoto committed
227
    typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
228
    PythonEdge(GraphInterface& gi, edge_descriptor e)
229
230
231
232
233
234
        : _gi(gi), _e(e), _valid(true)
    {
        CheckValid();
    }

    bool IsValid() const
Tiago Peixoto's avatar
Tiago Peixoto committed
235
    {
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
        return _valid &&
            (_gi._vertex_index[target(_e, _gi._mg)] < num_vertices(_gi._mg)) &&
            (_gi._vertex_index[source(_e, _gi._mg)] < num_vertices(_gi._mg)) &&
            (target(_e, _gi._mg) != graph_traits<Graph>::null_vertex()) &&
            (source(_e, _gi._mg) != graph_traits<Graph>::null_vertex());
    }

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

    void CheckValid() const
    {
        if (!_valid)
            throw GraphException("invalid edge descriptor");
Tiago Peixoto's avatar
Tiago Peixoto committed
252
253
    }

254
    GraphInterface::edge_t GetDescriptor() const
255
256
257
258
    {
        return _e;
    }

259
260
261
    struct get_source
    {
        template<class GraphType>
262
        void operator()(const GraphType& g, GraphInterface& gi,
263
264
265
                        const edge_descriptor& edge, python::object& vertex)
            const
        {
266
            vertex = python::object(PythonVertex(gi, source(edge, g)));
267
268
        }
    };
269

270
    python::object GetSource() const
Tiago Peixoto's avatar
Tiago Peixoto committed
271
    {
272
        CheckValid();
273
        python::object v;
274
        run_action<>()(_gi, lambda::bind<void>(get_source(), lambda::_1,
275
                                               lambda::var(_gi),
276
                                               lambda::var(_e),
277
278
                                               lambda::var(v)))();
        return v;
Tiago Peixoto's avatar
Tiago Peixoto committed
279
280
    }

281
282
283
    struct get_target
    {
        template<class GraphType>
284
        void operator()(const GraphType& g, GraphInterface& gi,
285
                        const edge_descriptor& edge,
286
287
                        python::object& vertex) const
        {
288
            vertex = python::object(PythonVertex(gi, target(edge, g)));
289
290
        }
    };
291

292
    python::object GetTarget() const
Tiago Peixoto's avatar
Tiago Peixoto committed
293
    {
294
        CheckValid();
295
        python::object v;
296
        run_action<>()(_gi, lambda::bind<void>(get_target(), lambda::_1,
297
298
299
                                               lambda::var(_gi),
                                               lambda::var(_e),
                                               lambda::var(v)))();
300
        return v;
Tiago Peixoto's avatar
Tiago Peixoto committed
301
302
    }

303
304
    std::string GetString() const
    {
305
306
307
        CheckValid();
        PythonVertex src = python::extract<PythonVertex>(GetSource());
        PythonVertex tgt = python::extract<PythonVertex>(GetTarget());
308
        return "(" + src.GetString() + "," + tgt.GetString() + ")";
309
310
    }

311
    size_t GetHash() const
Tiago Peixoto's avatar
Tiago Peixoto committed
312
    {
313
314
        CheckValid();
        return hash<size_t>()(_gi._edge_index[_e]);
Tiago Peixoto's avatar
Tiago Peixoto committed
315
316
    }

317
    bool operator==(const PythonEdge& other) const
Tiago Peixoto's avatar
Tiago Peixoto committed
318
    {
319
        CheckValid();
320
        return other._e == _e;
Tiago Peixoto's avatar
Tiago Peixoto committed
321
    }
322

323
    bool operator!=(const PythonEdge& other) const
324
    {
325
        CheckValid();
326
        return other._e != _e;
327
328
329
    }

private:
330
    GraphInterface& _gi;
331
    edge_descriptor _e;
332
    bool _valid;
333
334
};

335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
// 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>
360
361
362
class PythonPropertyMap
{
public:
363
364
    PythonPropertyMap(const PropertyMap& pmap)
        : _pmap(pmap) {}
365

366
367
368
369
370
371
372
    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;

373
    template <class PythonDescriptor>
374
    reference GetValue(const PythonDescriptor& key)
375
    {
376
        key.CheckValid();
377
        return get(_pmap, key.GetDescriptor());
378
379
    }

380
381
    template <class PythonDescriptor>
    void SetValue(const PythonDescriptor& key, const value_type& val)
382
    {
383
384
385
386
        set_value(key, val,
                  is_convertible<
                  typename property_traits<PropertyMap>::category,
                  writable_property_map_tag>());
387
388
    }

389
390
391
    template <class PythonDescriptor>
    void set_value(const PythonDescriptor& key, const value_type& val,
                   true_type)
392
    {
393
394
        key.CheckValid();
        put(_pmap, key.GetDescriptor(), val);
395
396
    }

397
    template <class PythonDescriptor>
398
399
    void set_value(const PythonDescriptor& key, const value_type& val,
                   false_type)
400
    {
401
        throw GraphException("property is read-only");
402
403
404
405
    }

    size_t GetHash() const
    {
406
        return hash<size_t>()(size_t(this));
407
408
409
410
    }

    std::string GetType() const
    {
411
412
413
414
415
416
417
        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];
418
419
    }

420
    boost::any GetMap() const
421
422
423
424
    {
        return _pmap;
    }

425
426
427
428
429
430
431
    boost::any GetDynamicMap() const
    {
        return (dynamic_property_map*)
            (new boost::detail::dynamic_property_map_adaptor<PropertyMap>
             (_pmap));
    }

432
433
434
    python::object GetArray(size_t size)
    {
        typedef typename mpl::or_<
435
436
437
438
439
440
441
442
443
              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());
444
445
446
447
448
449
450
451
452
453
454
455
456
    }

    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();
    }

457
private:
458
    PropertyMap _pmap; // hold an internal copy, since it's cheap
459
460
461
};


462
463
464
465
466
467
468
469
470
471
472
473
474
//
// Create new properties
//

struct new_property_map
{
    template <class ValueType, class IndexMap>
    void operator()(ValueType, IndexMap index, const string& type_name,
                    python::object& new_prop, bool& found) const
    {
        size_t i = mpl::find<value_types,ValueType>::type::pos::value;
        if (type_name == type_names[i])
        {
475
476
            typedef typename property_map_type::apply<ValueType, IndexMap>::type
                map_t;
477
478
479
480
481
482
483
484
            map_t prop(index);
            new_prop = python::object(PythonPropertyMap<map_t>(prop));
            found = true;
        }
    }
};

template <class IndexMap>
485
python::object new_property(const string& type, IndexMap index_map)
486
487
488
489
490
491
492
493
494
495
496
497
498
{
    python::object prop;
    bool found = false;
    mpl::for_each<value_types>(lambda::bind<void>(new_property_map(),
                                                  lambda::_1, index_map,
                                                  lambda::var(type),
                                                  lambda::var(prop),
                                                  lambda::var(found)));
    if (!found)
        throw GraphException("Invalid property type " + type);
    return prop;
}

499
500
501
} //graph_tool namespace

#endif