graph_python_interface.hh 13.4 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

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

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

40
41
42
43
namespace graph_tool
{
using namespace boost;

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


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

70
// below are classes related to the PythonVertex type
71
class PythonVertex
72
73
{
public:
74
    PythonVertex(const GraphInterface& gi, GraphInterface::vertex_t v):
75
76
77
78
79
80
81
82
83
84
85
        _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));
    }
86

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

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

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

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

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

125
    size_t GetOutDegree() const
126
    {
127
        CheckValid();
128
129
130
131
132
        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
133
134
    }

135
    // provide iterator support for out_edges
136

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

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

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

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

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

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

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

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

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

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

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

    bool IsValid() const
Tiago Peixoto's avatar
Tiago Peixoto committed
234
    {
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
        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
251
252
    }

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

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

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

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

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

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

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

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

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

private:
329
    const GraphInterface& _gi;
330
    edge_descriptor _e;
331
    bool _valid;
332
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
// 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>
359
360
361
class PythonPropertyMap
{
public:
362
363
    PythonPropertyMap(const PropertyMap& pmap)
        : _pmap(pmap) {}
364

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

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

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

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

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

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

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

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

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

431
private:
432
    PropertyMap _pmap; // hold an internal copy, since it's cheap
433
434
435
};


436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
//
// 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])
        {
            typedef vector_property_map<ValueType, IndexMap> map_t;
            map_t prop(index);
            new_prop = python::object(PythonPropertyMap<map_t>(prop));
            found = true;
        }
    }
};

template <class IndexMap>
python::object new_property(const string& type, boost::any imap)
{
    IndexMap index_map;
    try
    {
        index_map = any_cast<IndexMap>(imap);
    }
    catch (bad_any_cast&)
    {
        throw GraphException("Invalid index map");
    }
    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;
}

481
482
483
} //graph_tool namespace

#endif