graph_python_interface.hh 18.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) 2006-2015 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
#include <boost/python.hpp>
#include <boost/python/type_id.hpp>

Tiago Peixoto's avatar
Tiago Peixoto committed
24
25
26
27
28
29
30
31
32
#include <functional>

namespace std
{
    template<>
    struct hash<boost::python::object>
    {
        size_t operator()(const boost::python::object& o) const
        {
33
            return std::hash<int64_t>()(boost::python::extract<int64_t>(o.attr("__hash__")()));
Tiago Peixoto's avatar
Tiago Peixoto committed
34
35
36
37
        }
    };
}

38
39
#include <boost/graph/graph_traits.hpp>
#include <boost/mpl/logical.hpp>
40
#include <boost/iterator/iterator_facade.hpp>
41

Tiago Peixoto's avatar
Tiago Peixoto committed
42
43
#include <type_traits>

44
45
#include "graph.hh"
#include "graph_filtering.hh"
46
#include "graph_selectors.hh"
47
#include "numpy_bind.hh"
48

49

50
// this file includes a simple python interface for the internally kept
51
52
53
54
// 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).
55

56
57
58
namespace graph_tool
{

59
60
// generic iterator adaptor which can be used to iterate vertices, edges,
// out_edges and in_edges through python
61
template <class Graph, class Descriptor, class Iterator>
62
class PythonIterator
63
{
64
public:
65
    PythonIterator(std::shared_ptr<Graph>& gp,
66
                   std::pair<Iterator,Iterator> e)
67
        : _g(gp), _e(e) {}
68
    Descriptor Next()
69
    {
70
        if (_e.first == _e.second)
Tiago Peixoto's avatar
Tiago Peixoto committed
71
            boost::python::objects::stop_iteration_error();
72
        Descriptor e(_g, *_e.first);
73
74
        ++_e.first;
        return e;
75
76
    }
private:
77
    std::shared_ptr<Graph> _g;
78
    std::pair<Iterator,Iterator> _e;
Tiago Peixoto's avatar
Tiago Peixoto committed
79
80
81
};


82
// forward declaration of PythonEdge
83
84
template <class Graph>
class PythonEdge;
85

86
87
class VertexBase {}; // useful to unite all vertex

88
// below are classes related to the PythonVertex type
89
90
template <class Graph>
class PythonVertex : public VertexBase
91
92
{
public:
93
94
    PythonVertex(std::shared_ptr<Graph> g, GraphInterface::vertex_t v):
        _g(g), _v(v) {}
95
96
97

    bool IsValid() const
    {
98
99
100
        std::shared_ptr<Graph> gp(_g);
        Graph* g = gp.get();
        if (g == nullptr)
101
            return false;
102
103
        return ((_v != boost::graph_traits<Graph>::null_vertex()) &&
                (_v < num_vertices(*g)));
104
    }
105

106
107
108
    void CheckValid() const
    {
        if (!IsValid())
109
            throw ValueException("invalid vertex descriptor: " +
Tiago Peixoto's avatar
Tiago Peixoto committed
110
                                 boost::lexical_cast<string>(_v));
111
    }
112

113
    GraphInterface::vertex_t GetDescriptor() const
114
115
116
117
    {
        return _v;
    }

118
119
120
    template <class DegSelector>
    struct get_degree
    {
121
        void operator()(const Graph& g,
Tiago Peixoto's avatar
Tiago Peixoto committed
122
                        typename boost::graph_traits<Graph>::vertex_descriptor v,
123
124
                        size_t& deg) const
        {
125
            deg = DegSelector()(v, g);
126
        }
127

128
        template<class PMap>
129
130
        void operator()(const Graph& g,
                        typename boost::graph_traits<Graph>::vertex_descriptor v,
131
132
                        const boost::any& aweight, boost::python::object& deg,
                        bool& found, PMap) const
133
        {
134
135
136
137
138
139
140
            try
            {
                const PMap& weight = boost::any_cast<const PMap&>(aweight);
                deg = boost::python::object(DegSelector()(v, g, weight));
                found = true;
            }
            catch (boost::bad_any_cast&) {}
141
        }
142
143
    };

144
    size_t GetInDegree() const
145
    {
146
        CheckValid();
147
148
        std::shared_ptr<Graph> gp(_g);
        Graph& g = *gp.get();
149
        size_t in_deg;
150
        get_degree<in_degreeS>()(g, _v, in_deg);
151
        return in_deg;
152
    }
153

154
155
    boost::python::object GetWeightedInDegree(boost::any pmap) const
    {
156
157
        std::shared_ptr<Graph> gp(_g);
        Graph& g = *gp.get();
158
        boost::python::object in_deg;
159
160
161
162
163
164
165
166
167
        bool found = false;
        boost::mpl::for_each<edge_scalar_properties>(std::bind(get_degree<in_degreeS>(),
                                                               std::ref(g), _v,
                                                               std::ref(pmap),
                                                               std::ref(in_deg),
                                                               std::ref(found),
                                                               std::placeholders::_1));
        if (!found)
            throw ValueException("edge weight property must be of scalar type");
168
169
170
        return in_deg;
    }

171
    size_t GetOutDegree() const
172
    {
173
        CheckValid();
174
175
        std::shared_ptr<Graph> gp(_g);
        Graph& g = *gp.get();
176
        size_t out_deg;
177
        get_degree<out_degreeS>()(g, _v, out_deg);
178
        return out_deg;
Tiago Peixoto's avatar
Tiago Peixoto committed
179
180
    }

181
182
183

    boost::python::object GetWeightedOutDegree(boost::any pmap) const
    {
184
185
        std::shared_ptr<Graph> gp(_g);
        Graph& g = *gp.get();
186
        boost::python::object out_deg;
187
188
189
190
191
192
193
194
195
        bool found = false;
        boost::mpl::for_each<edge_scalar_properties>(std::bind(get_degree<out_degreeS>(),
                                                               std::ref(g), _v,
                                                               std::ref(pmap),
                                                               std::ref(out_deg),
                                                               std::ref(found),
                                                               std::placeholders::_1));
        if (!found)
            throw ValueException("edge weight property must be of scalar type");
196
197
198
        return out_deg;
    }

199
    // provide iterator support for out_edges
Tiago Peixoto's avatar
Tiago Peixoto committed
200
    boost::python::object OutEdges() const
Tiago Peixoto's avatar
Tiago Peixoto committed
201
    {
202
        CheckValid();
203
204
205
206
207
208
209
        std::shared_ptr<Graph> pg(_g);
        Graph& g = *pg;
        typedef typename boost::graph_traits<Graph>::out_edge_iterator
            out_edge_iterator;
        return boost::python::object(PythonIterator<Graph,PythonEdge<Graph>,
                                                    out_edge_iterator>
                                     (pg, out_edges(_v, g)));
210
    }
211

Tiago Peixoto's avatar
Tiago Peixoto committed
212
    boost::python::object InEdges() const
213
    {
214
        CheckValid();
215
216
217
218
219
220
221
        std::shared_ptr<Graph> pg(_g);
        Graph& g = *pg;
        typedef typename in_edge_iteratorS<Graph>::type
            in_edge_iterator;
        return boost::python::object(PythonIterator<Graph, PythonEdge<Graph>,
                                                    in_edge_iterator>
                                     (pg, in_edge_iteratorS<Graph>::get_edges(_v, g)));
Tiago Peixoto's avatar
Tiago Peixoto committed
222
    }
223

224
225
    std::string GetString() const
    {
226
        CheckValid();
Tiago Peixoto's avatar
Tiago Peixoto committed
227
        return boost::lexical_cast<std::string>(_v);
228
229
    }

230
    size_t GetHash() const
231
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
232
        return std::hash<size_t>()(_v);
233
234
    }

235
236
    size_t GetIndex() const
    {
237
        return _v;
238
239
    }

240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
    size_t GetGraphPtr() const
    {
        std::shared_ptr<Graph> pg(_g);
        return size_t(pg.get());
    }

    std::string GetGraphType() const
    {
        using boost::python::detail::gcc_demangle;
        return gcc_demangle(typeid(Graph).name());
    }

    template <class OGraph>
    bool operator==(const PythonVertex<OGraph>& other) const { return _v == other._v; }
    template <class OGraph>
    bool operator!=(const PythonVertex<OGraph>& other) const { return _v != other._v; }
    template <class OGraph>
    bool operator<(const PythonVertex<OGraph>& other) const { return _v < other._v; }
    template <class OGraph>
    bool operator<=(const PythonVertex<OGraph>& other) const { return _v <= other._v; }
    template <class OGraph>
    bool operator>(const PythonVertex<OGraph>& other) const { return _v > other._v; }
    template <class OGraph>
    bool operator>=(const PythonVertex<OGraph>& other) const { return _v >= other._v; }

265
private:
266
    std::weak_ptr<Graph> _g;
267
    GraphInterface::vertex_t _v;
268
};
269

270
// below are classes related to the PythonEdge type
271

272
273
class EdgeBase {}; // useful to unite all edge types

274
template <class Graph>
275
class PythonEdge : public EdgeBase
276
277
{
public:
Tiago Peixoto's avatar
Tiago Peixoto committed
278
    typedef typename boost::graph_traits<Graph>::edge_descriptor edge_descriptor;
279
280
    PythonEdge(std::shared_ptr<Graph> g, edge_descriptor e)
        : _g(g), _e(e) {}
281
282

    bool IsValid() const
Tiago Peixoto's avatar
Tiago Peixoto committed
283
    {
284
285
286
        std::shared_ptr<Graph> gp(_g);
        Graph* g = gp.get();
        if (g == nullptr)
287
            return false;
288

289
290
        auto s = source(_e, *g);
        auto t = target(_e, *g);
291

292
293
294
295
        return ((s != boost::graph_traits<Graph>::null_vertex()) &&
                (s < num_vertices(*g)) &&
                (t != boost::graph_traits<Graph>::null_vertex()) &&
                (t < num_vertices(*g)));
296
297
298
299
    }

    void CheckValid() const
    {
300
        if (!IsValid())
Tiago Peixoto's avatar
Tiago Peixoto committed
301
            throw ValueException("invalid edge descriptor");
Tiago Peixoto's avatar
Tiago Peixoto committed
302
303
    }

304
    GraphInterface::edge_t GetDescriptor() const
305
306
307
308
    {
        return _e;
    }

309
    PythonVertex<Graph> GetSource() const
310
    {
311
312
313
314
315
        CheckValid();
        std::shared_ptr<Graph> pg(_g);
        Graph& g = *pg;
        return PythonVertex<Graph>(pg, source(_e, g));
    }
316

317
    PythonVertex<Graph> GetTarget() const
Tiago Peixoto's avatar
Tiago Peixoto committed
318
    {
319
        CheckValid();
320
321
322
        std::shared_ptr<Graph> pg(_g);
        Graph& g = *pg;
        return PythonVertex<Graph>(pg, target(_e, g));
Tiago Peixoto's avatar
Tiago Peixoto committed
323
324
    }

325
    std::string GetString() const
326
    {
327
328
329
330
331
332
333
        CheckValid();
        Graph& g = *std::shared_ptr<Graph>(_g);
        auto s = source(_e, g);
        auto t = target(_e, g);
        return "(" + boost::lexical_cast<std::string>(s) + ", "
            + boost::lexical_cast<std::string>(t) + ")";
    }
334

335
    size_t GetHash() const
Tiago Peixoto's avatar
Tiago Peixoto committed
336
    {
337
        CheckValid();
338
339
340
        Graph& g = *std::shared_ptr<Graph>(_g);
        auto eindex = get(boost::edge_index_t(), g);
        return std::hash<size_t>()(eindex[_e]);
Tiago Peixoto's avatar
Tiago Peixoto committed
341
342
    }

343
    size_t GetGraphPtr() const
344
    {
345
346
        std::shared_ptr<Graph> pg(_g);
        return site_t(pg.get());
347
348
    }

349
350
351
352
353
354
355
356
357
358
359
360
    std::string GetGraphType() const
    {
        using boost::python::detail::gcc_demangle;
        return gcc_demangle(typeid(Graph).name());
    }

    template <class OGraph>
    bool operator==(const PythonEdge<OGraph>& other) const { return _e == other._e; }
    template <class OGraph>
    bool operator!=(const PythonEdge<OGraph>& other) const { return !(*this == other); }
    template <class OGraph>
    bool operator<(const PythonEdge<OGraph>& other)  const
Tiago Peixoto's avatar
Tiago Peixoto committed
361
    {
362
        CheckValid();
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
        other.CheckValid();
        Graph& g = *std::shared_ptr<Graph>(_g);
        OGraph& og = *std::shared_ptr<OGraph>(other._g);
        auto s = source(_e, g);
        auto t = target(_e, g);
        auto os = source(other._e, og);
        auto ot = target(other._e, og);
        if (not is_directed::apply<Graph>::type::value ||
            not is_directed::apply<OGraph>::type::value)
        {
            if (t < s)
                std::swap(s, t);
            if (ot < os)
                std::swap(os, ot);
        }
        return s < os && t < ot;
Tiago Peixoto's avatar
Tiago Peixoto committed
379
    }
380
381
382
383
384
385
    template <class OGraph>
    bool operator<=(const PythonEdge<OGraph>& other) const {return *this < other || *this == other;}
    template <class OGraph>
    bool operator>(const PythonEdge<OGraph>& other) const {return !(*this < other || *this == other);}
    template <class OGraph>
    bool operator>=(const PythonEdge<OGraph>& other) const {return *this > other || *this == other;}
Tiago Peixoto's avatar
Tiago Peixoto committed
386

387
private:
388
    std::weak_ptr<Graph> _g;
389
    edge_descriptor _e;
390
391
392

    template <class OGraph>
    friend class PythonEdge;
393
394
};

395
396
397
398
399
400
401
402
403
404
// 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

Tiago Peixoto's avatar
Tiago Peixoto committed
405
406
407
408
409
410
411
412
        typedef typename boost::mpl::if_<
            typename boost::mpl::and_<
                std::is_class<ValueType>,
                typename boost::mpl::and_<
                    typename boost::mpl::not_<std::is_same<ValueType,
                                                           string> >::type,
                    typename boost::mpl::not_<std::is_same<ValueType,
                                                           boost::python::object> >::type>::type
413
                >::type,
Tiago Peixoto's avatar
Tiago Peixoto committed
414
415
            boost::mpl::bool_<true>,
            boost::mpl::bool_<false> >::type type;
416
417
418
419
    };
};

template <class PropertyMap>
420
421
422
class PythonPropertyMap
{
public:
423
424
    PythonPropertyMap(const PropertyMap& pmap)
        : _pmap(pmap) {}
425

Tiago Peixoto's avatar
Tiago Peixoto committed
426
    typedef typename boost::property_traits<PropertyMap>::value_type value_type;
427

Tiago Peixoto's avatar
Tiago Peixoto committed
428
    typedef typename boost::mpl::if_<
429
430
431
432
        typename return_reference::apply<value_type>::type,
        value_type&,
        value_type>::type reference;

433
    template <class PythonDescriptor>
434
    reference GetValue(const PythonDescriptor& key)
435
    {
436
        key.CheckValid();
437
        return get(_pmap, key.GetDescriptor());
438
439
    }

440
441
    // in this case, val should be a copy, not a reference. This is to avoid a
    // problem with vector-valued property maps
442
    template <class PythonDescriptor>
443
    void SetValue(const PythonDescriptor& key, value_type val)
444
    {
445
        set_value(key, val,
Tiago Peixoto's avatar
Tiago Peixoto committed
446
447
                  std::is_convertible<typename boost::property_traits<PropertyMap>::category,
                                      boost::writable_property_map_tag>());
448
449
    }

450
451
    template <class PythonDescriptor>
    void set_value(const PythonDescriptor& key, const value_type& val,
Tiago Peixoto's avatar
Tiago Peixoto committed
452
                   std::true_type)
453
    {
454
455
        key.CheckValid();
        put(_pmap, key.GetDescriptor(), val);
456
457
    }

458
    template <class PythonDescriptor>
459
    void set_value(const PythonDescriptor&, const value_type&,
Tiago Peixoto's avatar
Tiago Peixoto committed
460
                   std::false_type)
461
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
462
        throw ValueException("property is read-only");
463
464
465
466
    }

    size_t GetHash() const
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
467
        return std::hash<size_t>()(size_t(this));
468
469
470
471
    }

    std::string GetType() const
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
472
473
474
        using boost::python::detail::gcc_demangle;
        if (std::is_same<typename boost::mpl::find<value_types,value_type>::type,
                         typename boost::mpl::end<value_types>::type>::value)
475
476
            return gcc_demangle(typeid(value_type).name());
        else
Tiago Peixoto's avatar
Tiago Peixoto committed
477
            return type_names[boost::mpl::find<value_types,
478
                                               value_type>::type::pos::value];
479
480
    }

481
    boost::any GetMap() const
482
483
484
485
    {
        return _pmap;
    }

486
487
    boost::any GetDynamicMap() const
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
488
        return (boost::dynamic_property_map*)
489
490
491
492
            (new boost::detail::dynamic_property_map_adaptor<PropertyMap>
             (_pmap));
    }

Tiago Peixoto's avatar
Tiago Peixoto committed
493
    boost::python::object GetArray(size_t size)
494
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
495
496
497
498
499
500
501
502
        typedef typename boost::mpl::or_<
            typename boost::mpl::or_<
                std::is_same<PropertyMap,
                             GraphInterface::vertex_index_map_t>,
                std::is_same<PropertyMap,
                             GraphInterface::edge_index_map_t> >::type,
            typename boost::mpl::not_<
                typename boost::mpl::has_key<numpy_types, value_type>::type >
503
            ::type>::type isnt_vector_map;
504
        return get_array(size, isnt_vector_map());
505
506
    }

507
    boost::python::object get_array(size_t size, boost::mpl::bool_<false>)
508
509
510
511
512
    {
        _pmap.reserve(size);
        return wrap_vector_not_owned(_pmap.get_storage());
    }

513
    boost::python::object get_array(size_t, boost::mpl::bool_<true>)
514
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
515
        return boost::python::object();
516
517
    }

518
519
    bool IsWritable() const
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
520
521
        return std::is_convertible<typename boost::property_traits<PropertyMap>::category,
                                   boost::writable_property_map_tag>::value;
522
523
    }

524
private:
525
    PropertyMap _pmap; // hold an internal copy, since it's cheap
526
527
528
};


529
530
531
532
533
534
535
536
//
// Create new properties
//

struct new_property_map
{
    template <class ValueType, class IndexMap>
    void operator()(ValueType, IndexMap index, const string& type_name,
Tiago Peixoto's avatar
Tiago Peixoto committed
537
                     boost::any pmap, boost::python::object& new_prop, bool& found) const
538
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
539
        size_t i = boost::mpl::find<value_types,ValueType>::type::pos::value;
540
541
        if (type_name == type_names[i])
        {
542
543
            typedef typename property_map_type::apply<ValueType, IndexMap>::type
                map_t;
544
545
546
547
            map_t prop;
            if (pmap.empty())
                prop = map_t(index);
            else
Tiago Peixoto's avatar
Tiago Peixoto committed
548
                prop = boost::any_cast<map_t>(pmap);
549

Tiago Peixoto's avatar
Tiago Peixoto committed
550
            new_prop = boost::python::object(PythonPropertyMap<map_t>(prop));
551
552
553
554
555
556
            found = true;
        }
    }
};

template <class IndexMap>
Tiago Peixoto's avatar
Tiago Peixoto committed
557
558
boost::python::object new_property(const string& type, IndexMap index_map,
                                   boost::any pmap)
559
{
Tiago Peixoto's avatar
Tiago Peixoto committed
560
    boost::python::object prop;
561
    bool found = false;
Tiago Peixoto's avatar
Tiago Peixoto committed
562
563
564
565
    boost::mpl::for_each<value_types>(std::bind(new_property_map(),
                                                std::placeholders::_1, index_map,
                                                std::ref(type), pmap, std::ref(prop),
                                                std::ref(found)));
566
    if (!found)
Tiago Peixoto's avatar
Tiago Peixoto committed
567
        throw ValueException("Invalid property type: " + type);
568
569
570
    return prop;
}

571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
//
// Python IO streams (minimal access to c++ streams)
//

class OStream
{
public:
    OStream(std::ostream& s): _s(s) {}

    void Write(const std::string& s, size_t n)
    {
        _s.write(s.c_str(), long(n));
    }

    void Flush()
    {
        _s.flush();
    }

private:
    std::ostream& _s;
};

class IStream
{
public:
    IStream(std::istream& s): _s(s) {}

    boost::python::object Read(size_t n)
    {
        std::string buf;
        buf.resize(n);
        _s.read(&buf[0], n);
        buf.resize(_s.gcount());

#if (PY_MAJOR_VERSION >= 3)
        // in python 3 we need to construct a 'bytes' instance
        PyObject* bytes = PyBytes_FromStringAndSize(&buf[0], buf.size());
        boost::python::handle<> x(bytes);
        boost::python::object pbuf(x);
#else
        boost::python::str pbuf(buf);
#endif
        return pbuf;
    }

private:
    std::istream& _s;
};


622
623
624
} //graph_tool namespace

#endif