graph_python_filtering.hh 21.4 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// graph-tool -- a general graph modification and manipulation thingy
//
// Copyright (C) 2006  Tiago de Paula Peixoto <tiago@forked.de>
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// 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
// along with this program; if not, write to the Free Software
// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.

#ifndef PYTHON_FILTERING_HH
#define PYTHON_FILTERING_HH

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/graph/reverse_graph.hpp>
#include <boost/mpl/vector.hpp>
#include <boost/mpl/map.hpp>
#include <boost/mpl/for_each.hpp>
#include <boost/mpl/at.hpp>
#include <boost/mpl/or.hpp>
#include <boost/mpl/if.hpp>
#include <boost/mpl/logical.hpp>
#include <boost/python/object.hpp>
33
#include <boost/python/class.hpp>
34
#include <boost/python/dict.hpp>
35
#include <boost/python/long.hpp>
36
37
#include <boost/python/extract.hpp>
#include <boost/python/make_function.hpp>
38
39
40
#include <boost/python/self.hpp>
#include <boost/python/operators.hpp>
#include <boost/functional/hash.hpp>
41
42
43
44
45

namespace graph_tool
{
using namespace boost;

46
47
template <class VertexOrEdge>
class get_python_property_value
48
{
49
50
51
52
53
54
55
56
57
58
59
60
61
public:
    get_python_property_value(const dynamic_property_map& dmap, const VertexOrEdge& e)
        : _dmap(dmap), _e(e) {}
        
    python::object operator()()
    {
        typedef mpl::vector<bool,int,long,size_t,float,double,std::string> value_types;
        mpl::for_each<value_types>(try_conversion(*this));
        return _retval;
    }

private:
    struct try_conversion
62
    {
63
64
65
66
        try_conversion(get_python_property_value& parent): _parent(parent) {}
        
        template <class Type>
        void operator()(Type)
67
        {
68
69
70
71
            any any_val = const_cast<dynamic_property_map&>(_parent._dmap).get(_parent._e);
            Type* value = any_cast<Type>(&any_val);
            if (value != 0)
                _parent._retval = python::object(*value);
72
        }
73
74
75
76
77
78
79
80
        
        get_python_property_value& _parent;
    };
    
    const dynamic_property_map& _dmap;
    const VertexOrEdge& _e;
    python::object _retval;
};
81

82
83
template <class Graph>
class PythonEdge;
84

85
86
87
88
89
template <class Graph>
class PythonVertex
{
public:
    PythonVertex(python::object base): _base(base)
90
    {
91
92
93
94
95
96
97
98
99
        static bool first_time = true;
        if (first_time)
        {
            _python_class.def(python::init<python::object>());
            _python_class.def("in_degree", &PythonVertex::GetInDegree);
            _python_class.def("out_degree", &PythonVertex::GetOutDegree);
            _python_class.def("get_property", &PythonVertex::GetProperty);
            _python_class.def("out_edges", &PythonVertex::GetOutEdges);
            _python_class.def("in_edges", &PythonVertex::GetInEdges);
100
101
            _python_class.def(python::self == python::self);
            _python_class.def("__hash__", &PythonVertex::GetHash);
102
103
104
105
            first_time = false;
        }
    }
    PythonVertex(): _base(python::object()) { *this = PythonVertex(_base); }
106

107
108
109
    PythonVertex(const PythonVertex& v)
    {
        if (v._base != python::object())
110
        {
111
112
            base_t base = python::extract<base_t>(_base);
            if (get<3>(base))
113
            {
114
115
116
117
                vertex_descriptor* new_v = new vertex_descriptor;
                *new_v = get<1>(base);
                base_t new_base(get<0>(base), *new_v, get<2>(base), true);
                _base = python::object(new_base);
118
119
            }
        }
120
121
    }

122
    ~PythonVertex()
123
    {
124
        if (_base != python::object())
125
        {
126
127
128
            base_t base = python::extract<base_t>(_base);
            if (get<3>(base))
                delete &get<1>(base);
129
        }
130
    }
131

132
133
134
    typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
    typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
    typedef tuple<const Graph&, const vertex_descriptor&, const dynamic_properties&, bool> base_t;
135

136
    python::object GetInDegree()
137
    {
138
        if (_base != python::object())
139
        {
140
141
142
143
            base_t base = python::extract<base_t>(_base);
            return python::object(in_degreeS()(get<1>(base), get<0>(base)));
        }
        else
144
        {
145
            return python::object();
146
        }
147
    }
148

149
    python::object GetOutDegree()
150
    {
151
152
153
154
155
156
        if (_base != python::object())
        {
            base_t base = python::extract<base_t>(_base);
            return python::object(out_degree(get<1>(base), get<0>(base)));
        }
        else
157
        {
158
            return python::object();
159
        }
160
    }
161

162
163
164
    python::object GetProperty(std::string prop)
    {
        if (_base != python::object())
165
        {
166
167
168
169
            base_t base = python::extract<base_t>(_base);
            const dynamic_properties& dp = get<2>(base);
            const vertex_descriptor& v = get<1>(base);
            for(typeof(dp.begin()) iter = dp.lower_bound(prop); iter != dp.end(); ++iter)
170
            {
171
172
                if (iter->second->key() == typeid(vertex_descriptor))
                    return get_python_property_value<vertex_descriptor>(*iter->second, v)();
173
            }
174
            return python::object();
175
        }
176
177
178
179
180
        else
        {
            return python::object();
        }
    }
181

182
183
184
    python::object GetOutEdges()
    {
        if (_base != python::object())
185
        {
186
187
188
189
190
191
192
193
            python::list out_edge_list;
            base_t base = python::extract<base_t>(_base);
            const Graph& g = get<0>(base);
            const vertex_descriptor& v = get<1>(base);
            const dynamic_properties& dp = get<2>(base);
            python::object edge_class = PythonEdge<Graph>().GetPythonClass();
            typename graph_traits<Graph>::out_edge_iterator e, e_end;
            for (tie(e, e_end) = out_edges(v, g); e != e_end; ++e)
194
            {
195
196
197
198
199
                edge_descriptor* new_edge = new edge_descriptor;
                *new_edge = *e;
                typename PythonEdge<Graph>::base_t edge_base(g, *new_edge, dp, true);
                python::object edge = (edge_class)(python::object(edge_base));
                out_edge_list.append(edge);
200
            }
201
            return out_edge_list;
202
        }
203
        else
204
        {
205
            return python::object();
206
        }
207
    }
208

209
    python::object GetInEdges()
210
    {
211
212
213
214
215
216
        if (_base != python::object())
        {
            base_t base = python::extract<base_t>(_base);
            const Graph& g = get<0>(base);
            const vertex_descriptor& v = get<1>(base);
            const dynamic_properties& dp = get<2>(base);
217
            return get_in_edges(g, v, dp, typename is_convertible<typename graph_traits<Graph>::directed_category, directed_tag>::type());
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
        }
        else
        {
            return python::object();
        }
    }

    python::object GetHash()
    {
        if (_base != python::object())
        {            
            base_t base = python::extract<base_t>(_base);
            return python::object(hash<vertex_descriptor>()(get<1>(base)));
        }
        else
        {
            return python::object(0);
        }
    }

    bool operator==(const PythonVertex& other)
    {
        if (_base != python::object() && other._base != python::object())
        {            
            const base_t o_base = python::extract<base_t>(other._base);
            base_t base = python::extract<base_t>(_base);
            return python::object(get<1>(base) == get<1>(o_base));
        }
        else
        {
            return false;
        }
250
    }
251

252
253
254
255
256
257
258
259
260
    python::class_<PythonVertex> GetPythonClass() { return _python_class; }
        
private:
    template<class G>
    python::object get_in_edges(const G& g, const typename graph_traits<G>::vertex_descriptor& v, const dynamic_properties& dp, true_type)
    {
        python::list in_edge_list;
        typename graph_traits<Graph>::in_edge_iterator e, e_end;
        for (tie(e, e_end) = in_edges(v, g); e != e_end; ++e)
261
        {
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
            edge_descriptor* new_edge = new edge_descriptor;
            *new_edge = *e;
            typename PythonEdge<Graph>::base_t edge_base(g, *new_edge, dp, true);
            python::object edge = (PythonEdge<Graph>().GetPythonClass())(python::object(edge_base));
            in_edge_list.append(edge);
        }
        return in_edge_list;
    }
        
    template<class G>
    python::object get_in_edges(const G& g, const typename graph_traits<G>::vertex_descriptor& v, const dynamic_properties& dp, false_type)
    {
        python::list props;
        return props;
    }
277

278
279
280
    python::object _base;
    static python::class_<PythonVertex> _python_class;
};
281

282
template <class Graph> python::class_<PythonVertex<Graph> > PythonVertex<Graph>::_python_class =  python::class_<PythonVertex<Graph> >("Vertex", python::no_init);
283
284


285
286
287
288
289
290
291
292
293
294
295
296
297
298
template <class Graph>
class PythonEdge
{
public:
    PythonEdge(python::object base): _base(base)
    {
        static bool first_time = true;
        if (first_time)
        {
            _python_class.def(python::init<python::object>());
            _python_class.def("source", &PythonEdge::GetSource);
            _python_class.def("target", &PythonEdge::GetTarget);
            _python_class.def("get_property", &PythonEdge::GetProperty);
            _python_class.def("n_parallel", &PythonEdge::GetNParallel);
299
300
            _python_class.def(python::self == python::self);
            _python_class.def("__hash__", &PythonEdge::GetHash);
301
302
303
304
305
            first_time = false;
        }
    }
    PythonEdge(): _base(python::object()) { *this = PythonEdge(_base); }
    PythonEdge(const PythonEdge& e)
306
    {
307
308
309
310
311
312
313
314
315
316
317
        if (e._base != python::object())
        {
            base_t base = python::extract<base_t>(_base);
            if (get<3>(base))
            {
                edge_descriptor* new_e = new edge_descriptor;
                base_t new_base(get<0>(base), *new_e, get<2>(base), true);
                _base = python::object(new_base);
            }
        }
    }
318

319
320
321
    ~PythonEdge()
    {
        if (_base != python::object())
322
        {
323
324
325
            base_t base = python::extract<base_t>(_base);
            if (get<3>(base))
                delete &get<1>(base);
326
        }
327
    }
328

329
330
331
    typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
    typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
    typedef tuple<const Graph&, const edge_descriptor&, const dynamic_properties&, bool> base_t;
332

333
    python::object GetSource()
334
    {
335
        if (_base != python::object())
336
        {
337
338
339
340
341
342
            base_t base = python::extract<base_t>(_base);
            vertex_descriptor *v = new vertex_descriptor;
            *v = source(get<1>(base), get<0>(base));
            typename PythonVertex<Graph>::base_t vertex_base(get<0>(base), *v, get<2>(base), true);
            python::object source_vertex = (PythonVertex<Graph>().GetPythonClass())(python::object(vertex_base));
            return source_vertex;
343
        }
344
345
346
347
348
        else
        {
            return python::object();
        }
    }
349

350
    python::object GetTarget()
351
    {
352
353
354
355
356
357
358
359
360
361
362
363
364
365
        if (_base != python::object())
        {
            base_t base = python::extract<base_t>(_base);            
            vertex_descriptor *v = new vertex_descriptor;
            *v = target(get<1>(base), get<0>(base));
            typename PythonVertex<Graph>::base_t vertex_base(get<0>(base), *v, get<2>(base), true);
            python::object target_vertex = (PythonVertex<Graph>().GetPythonClass())(python::object(vertex_base));
            return target_vertex;
        }
        else
        {
            return python::object();
        }
    }
366

367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
    python::object GetProperty(std::string prop)
    {
        if (_base != python::object())
        {
            base_t base = python::extract<base_t>(_base);
            const dynamic_properties& dp = get<2>(base);
            const edge_descriptor& e = get<1>(base);
            for(typeof(dp.begin()) iter = dp.lower_bound(prop); iter != dp.end(); ++iter)
            {
                if (iter->second->key() != typeid(vertex_descriptor)) // FIXME: graph properties?
                    return get_python_property_value<edge_descriptor>(*iter->second, e)();
            }
            return python::object();
        }
        else
        {
            return python::object();
        }
    }
386

387
388
389
    python::object GetNParallel()
    {
        if (_base != python::object())
390
        {
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
            base_t base = python::extract<base_t>(_base);
            const Graph& g = get<0>(base);
            const edge_descriptor& e = get<1>(base);
            size_t n = 0;
            vertex_descriptor s,t;
            s = source(e, g);
            t = target(e, g);
            typename graph_traits<Graph>::adjacency_iterator a, a_end;
            for(tie(a, a_end) = adjacent_vertices(s, g); a != a_end; ++a)
                if (*a == t)
                    n++;
            return python::object(n-1);
        }
        else
        {
            return python::object();
407
        }
408
409
    };

410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
    python::object GetHash()
    {
        if (_base != python::object())
        {            
            base_t base = python::extract<base_t>(_base);
            const Graph& g = get<0>(base);
            const edge_descriptor& e = get<1>(base);
            vertex_descriptor s,t;
            s = source(e, g);
            t = target(e, g);
            return python::object(hash<std::pair<vertex_descriptor,vertex_descriptor> >()(make_pair(s,t)));
        }
        else
        {
            return python::object(0);
        }
    }

    bool operator==(const PythonEdge& other)
    {
        if (_base != python::object() && other._base != python::object())
        {            
            const base_t o_base = python::extract<base_t>(other._base);
            base_t base = python::extract<base_t>(_base);
            return python::object(get<1>(base) == get<1>(o_base));
        }
        else
        {
            return false;
        }
    }

442
443
444
445
446
447
448
    python::class_<PythonEdge> GetPythonClass() { return _python_class; }
        
private:

    python::object _base;
    static python::class_<PythonEdge> _python_class;
};
449

450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
template <class Graph> python::class_<PythonEdge<Graph> > PythonEdge<Graph>::_python_class =  python::class_<PythonEdge<Graph> >("Edge", python::no_init);

//==============================================================================
// populate_python_funcs
//==============================================================================

template <class Graph>
struct init_counter
{
    static bool registered;
};
template <class Graph> bool init_counter<Graph>::registered = false;

template <class Descriptor, class HasBase = mpl::bool_<false> >
class populate_python_funcs
{
public:
    template<class Graph>
    void operator()(const Graph& g, Descriptor& u, const dynamic_properties& dp, python::object& variables)
    {
        if (!init_counter<Graph>::registered)
471
        {
472
473
474
475
476
            base_from_tuple<typename PythonVertex<Graph>::base_t>();
            python::to_python_converter<typename PythonVertex<Graph>::base_t, base_to_tuple<typename PythonVertex<Graph>::base_t> >();
            base_from_tuple<typename PythonEdge<Graph>::base_t>();
            python::to_python_converter<typename PythonEdge<Graph>::base_t, base_to_tuple<typename PythonEdge<Graph>::base_t> >();
            init_counter<Graph>::registered = true;
477
478
        }

479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
        variables["Vertex"] = PythonVertex<Graph>().GetPythonClass();
        variables["Edge"] = PythonEdge<Graph>().GetPythonClass();
        populate_specific(g, u, dp, variables);
    }

private:

    template <class Base>
    struct base_to_tuple
    {
        static PyObject* convert(const Base& b)
        {
            boost::python::tuple t = boost::python::make_tuple(python::long_(size_t(&get<0>(b))), python::long_(size_t(&get<1>(b))), python::long_(size_t(&get<2>(b))), get<3>(b));
            return python::incref(t.ptr());
        }
494
495
    };

496
497
    template <class Base>
    struct base_from_tuple
498
    {
499
500
501
502
        base_from_tuple()
        {
            python::converter::registry::push_back(&convertible, &construct, boost::python::type_id<Base>());
        }
503

504
        static void* convertible(PyObject* obj_ptr)
505
        {
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
            python::handle<> x(python::borrowed(obj_ptr));
            python::object o(x);
            python::extract<size_t> first(o[0]);
            python::extract<size_t> second(o[1]);
            python::extract<size_t> third(o[2]);
            python::extract<bool> fourth(o[3]);
            if (!first.check() || !second.check() || !third.check() || !fourth.check())
                return 0;
            return obj_ptr;
        }
        
        static void construct(PyObject* obj_ptr, python::converter::rvalue_from_python_stage1_data* data)
        {          
            python::handle<> x(python::borrowed(obj_ptr));
            python::object o(x);
            typedef typename remove_reference<typename tuples::element<0,Base>::type>::type t0;
            typedef typename remove_reference<typename tuples::element<1,Base>::type>::type t1;
            typedef typename remove_reference<typename tuples::element<2,Base>::type>::type t2;
            t0* p0 = static_cast<t0*>((void *) size_t(python::extract<size_t>(o[0])));
            t1* p1 = static_cast<t1*>((void *) size_t(python::extract<size_t>(o[1])));
            t2* p2 = static_cast<t2*>((void *) size_t(python::extract<size_t>(o[2])));
            bool p4 = python::extract<bool>(o[3]);
            Base value(*p0, *p1, *p2, p4);
            
            void* storage = ( (python::converter::rvalue_from_python_storage<Base>*) data)->storage.bytes;
            new (storage) Base(value);
            data->convertible = storage;
533
        }
534
    };
535

536
537
538

    template <class Graph>
    void populate_specific(const Graph& g, typename graph_traits<Graph>::vertex_descriptor& v, const dynamic_properties& dp, python::object& variables)
539
    {
540
541
542
543
544
        typename PythonVertex<Graph>::base_t vertex_base(g, v, dp, false);
        python::object vertex = (PythonVertex<Graph>().GetPythonClass())(python::object(vertex_base));                
        variables["v"] = vertex;
        populate_base(g, v, dp, variables, HasBase());
    }
545

546
547
548
549
550

    template <class Graph>
    void populate_base(const Graph& g, typename graph_traits<Graph>::vertex_descriptor& v, const dynamic_properties& dp, python::object& variables,  mpl::bool_<true>) 
    {
        if (!init_counter<Graph>::registered)
551
        {
552
553
554
555
556
            base_from_tuple<typename PythonVertex<typename Graph::graph_type>::base_t>();
            python::to_python_converter<typename PythonVertex<typename Graph::graph_type>::base_t, base_to_tuple<typename PythonVertex<typename Graph::graph_type>::base_t> >();
            base_from_tuple<typename PythonEdge<typename Graph::graph_type>::base_t>();
            python::to_python_converter<typename PythonEdge<typename Graph::graph_type>::base_t, base_to_tuple<typename PythonEdge<typename Graph::graph_type>::base_t> >();
            init_counter<Graph>::registered = true;
557
        }
558

559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
        variables["BaseVertex"] = PythonVertex<typename Graph::graph_type>().GetPythonClass();
        variables["BaseEdge"] = PythonEdge<typename Graph::graph_type>().GetPythonClass();
        typename PythonVertex<typename Graph::graph_type>::base_t vertex_base(g.m_g, v, dp, false);
        python::object vertex = (PythonVertex<typename Graph::graph_type>().GetPythonClass())(python::object(vertex_base));
        variables["base_v"] = vertex;
    }

    template <class Graph>
    void populate_base(const Graph& g, typename graph_traits<Graph>::vertex_descriptor& v, const dynamic_properties& dp, python::object& variables,  mpl::bool_<false>)
    {
    }

    template <class Graph>
    void populate_specific(const Graph& g, typename graph_traits<Graph>::edge_descriptor& e, const dynamic_properties& dp, python::object& variables)
    {
        typename PythonEdge<Graph>::base_t edge_base(g, e, dp, false);
        python::object edge = (PythonEdge<Graph>().GetPythonClass())(python::object(edge_base));                
        variables["e"] = edge;
    }
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
};


//==============================================================================
// PythonFilter
//==============================================================================
template <class Graph, class Descriptor, class HasBase = mpl::bool_<false> >
class PythonFilter
{
public:
    typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
    typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;

    typedef mpl::vector<in_degreeS,out_degreeS,total_degreeS> degrees;

    PythonFilter(){}
    PythonFilter(const Graph& g, const dynamic_properties& dp, python::object filter)
        : _g(&g), _filter(filter[0])
    {
597
598
        python::object variables = filter[1];
        populate_python_funcs<Descriptor, HasBase>()(*_g, _u, dp, variables);
599
600
601
602
    }
    
 
    inline bool operator() (Descriptor u) const
603
604
605
    {              
        _u = u;
        return python::extract<bool>(_filter());
606
607
608
609
610
    }

private:
    Graph const*  _g;
    python::object _filter;
611
    static Descriptor _u;
612
613
};

614
615
template <class Graph, class Descriptor, class HasBase> 
Descriptor PythonFilter<Graph,Descriptor,HasBase>::_u;
616
617
618
619

} //graph_tool namespace

#endif