graph_python_interface.hh 11.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) 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
32
#include <boost/python.hpp>

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

39
40
41
42
namespace graph_tool
{
using namespace boost;

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


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

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

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

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

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

102
103
104
105
106
107
108
109
110
111
112
113
    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);
        }
    };

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

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

134
    // provide iterator support for out_edges
135

136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
    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
152
    OutEdges() const
Tiago Peixoto's avatar
Tiago Peixoto committed
153
    {
154
        CheckValid();
155
156
157
158
159
        python::object iter;
        run_action<>()(_gi, lambda::bind<void>(get_out_edges(), lambda::_1,
                                               lambda::var(_gi), _v,
                                               lambda::var(iter)))();
        return iter;
160
    }
161

162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
    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
178
    InEdges() const
179
    {
180
        CheckValid();
181
        python::object iter;
182
        run_action<>()(_gi, lambda::bind<void>(get_in_edges(), lambda::_1,
183
184
185
                                               lambda::var(_gi), _v,
                                               lambda::var(iter)))();
        return iter;
Tiago Peixoto's avatar
Tiago Peixoto committed
186
    }
187

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

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

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

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

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

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

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

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

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

257
258
259
260
261
262
263
264
265
266
    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)));
        }
    };
267

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

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

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

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

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

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

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

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

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

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

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

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

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

    size_t GetHash() const
    {
        return hash<std::string>()(_name + this->GetType());
    }

    std::string GetType() const
    {
409
        return type_names[mpl::find<value_types,value_type>::type::pos::value];
410
411
412
413
    }

private:
    const std::string& _name;
414
    PropertyMap& _pmap;
415
416
417
};


418
419
420
} //graph_tool namespace

#endif