graph_python_interface.cc 20.8 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-2016 Tiago de Paula Peixoto <tiago@skewed.de>
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//
// 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 3
// 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, see <http://www.gnu.org/licenses/>.

18
19
#include "graph_filtering.hh"
#include "graph.hh"
20
#include "graph_util.hh"
21
22
#include "graph_python_interface.hh"

23
#include <boost/python.hpp>
24
#include <boost/python/stl_iterator.hpp>
25
#include <set>
26

27

28
29
30
31
using namespace std;
using namespace boost;
using namespace graph_tool;

32
33
34
namespace graph_tool
{

35
36
37
struct get_vertex_iterator
{
    template <class Graph>
38
    void operator()(Graph& g, GraphInterface& gi,
39
40
                    python::object& iter) const
    {
41
        auto gp = retrieve_graph_view<Graph>(gi, g);
42
        typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
43
44
        iter = python::object(PythonIterator<Graph, PythonVertex<Graph>,
                                             vertex_iterator>(gp, vertices(g)));
45
46
47
    }
};

48
python::object get_vertices(GraphInterface& gi)
49
50
{
    python::object iter;
51
    run_action<>()(gi, std::bind(get_vertex_iterator(),
52
                                 std::placeholders::_1,
53
                                 std::ref(gi),
Tiago Peixoto's avatar
Tiago Peixoto committed
54
                                 std::ref(iter)))();
55
56
57
    return iter;
}

58
59
60
struct get_vertex_soft
{
    template <class Graph>
61
    void operator()(Graph& g, GraphInterface& gi, size_t i, python::object& v) const
62
    {
63
        auto gp = retrieve_graph_view<Graph>(gi, g);
64
65
66
67
68
        if (i < num_vertices(g))
            v = python::object(PythonVertex<Graph>(gp, vertex(i, g)));
        else
            v = python::object(PythonVertex<Graph>(gp,
                                                   graph_traits<Graph>::null_vertex()));
69
70
71
72
73
74
    }
};

struct get_vertex_hard
{
    template <class Graph>
75
    void operator()(Graph& g, GraphInterface& gi, size_t i, python::object& v) const
76
    {
77
        auto gp = retrieve_graph_view<Graph>(gi, g);
78
        size_t c = 0;
79
        for (auto vi : vertices_range(g))
80
81
        {
            if (c == i)
82
            {
83
                v = python::object(PythonVertex<Graph>(gp, vi));
84
85
                return;
            }
86
87
            ++c;
        }
88
89
        v = python::object(PythonVertex<Graph>(gp,
                                               graph_traits<Graph>::null_vertex()));
90
91
92
    }
};

93
python::object get_vertex(GraphInterface& gi, size_t i, bool use_index)
94
95
{
    python::object v;
96
    if (!use_index)
97
        run_action<>()(gi,
98
                       std::bind(get_vertex_hard(), std::placeholders::_1,
99
                                 std::ref(gi), i, std::ref(v)))();
100
    else
101
        run_action<>()(gi,
102
                       std::bind(get_vertex_soft(), std::placeholders::_1,
103
                                 std::ref(gi), i, std::ref(v)))();
104
105
106
    return v;
}

107
108
109
struct get_edge_iterator
{
    template <class Graph>
110
    void operator()(Graph& g, GraphInterface& gi, python::object& iter)
111
        const
112
    {
113
        auto gp = retrieve_graph_view<Graph>(gi, g);
114
        typedef typename graph_traits<Graph>::edge_iterator edge_iterator;
115
116
        iter = python::object(PythonIterator<Graph, PythonEdge<Graph>,
                                             edge_iterator>(gp, edges(g)));
117
118
119
    }
};

120
python::object get_edges(GraphInterface& gi)
121
122
{
    python::object iter;
123
    run_action<>()(gi, std::bind(get_edge_iterator(), std::placeholders::_1,
124
                                 std::ref(gi), std::ref(iter)))();
125
126
127
    return iter;
}

128
struct add_new_vertex
129
{
130
131
132
    template <class Graph>
    void operator()(Graph& g, GraphInterface& gi, size_t n,
                    python::object& new_v) const
133
    {
134
        auto gp = retrieve_graph_view<Graph>(gi, g);
135
        if (n != 1)
136
137
138
139
140
141
142
143
144
        {
            for (size_t i = 0; i < n; ++i)
                add_vertex(g);
            new_v = python::object();
        }
        else
        {
            new_v = python::object(PythonVertex<Graph>(gp, add_vertex(g)));
        }
145
    }
146
147
148
149
150
151
};


python::object add_vertex(GraphInterface& gi, size_t n)
{
    python::object v;
152
    run_action<>()(gi, std::bind(add_new_vertex(), std::placeholders::_1,
153
154
                                 std::ref(gi), n, std::ref(v)))();
    return v;
155
156
157
}


158
void remove_vertex_array(GraphInterface& gi, const python::object& oindex, bool fast)
159
{
160
    boost::multi_array_ref<int64_t,1> index = get_array<int64_t,1>(oindex);
161
    auto& g = gi.get_graph();
162
    if (fast)
163
164
165
166
    {
        for (auto v : index)
            remove_vertex_fast(vertex(v, g), g);
    }
167
    else
168
169
170
171
    {
        for (auto v : index)
            remove_vertex(vertex(v, g), g);
    }
172
173
}

174
175
void remove_vertex(GraphInterface& gi, size_t v, bool fast)
{
176
    auto& g = gi.get_graph();
177
178
179
180
181
182
183
184
185
186
    if (fast)
    {
        remove_vertex_fast(vertex(v, g), g);
    }
    else
    {
        remove_vertex(vertex(v, g), g);
    }
}

187
188
189
190
191
192
193
194
195
196
197
struct do_clear_vertex
{
    template <class Graph>
    void operator()(Graph& g, size_t v) const
    {
        clear_vertex(vertex(v, g), g);
    }
};

void clear_vertex(GraphInterface& gi, size_t v)
{
198
    run_action<>()(gi, std::bind(do_clear_vertex(), std::placeholders::_1, v))();
199
}
200

201
202
struct add_new_edge
{
203
204
205
    template <class Graph>
    void operator()(Graph& g, GraphInterface& gi, size_t s, size_t t,
                    python::object& new_e) const
206
    {
207
        auto gp = retrieve_graph_view<Graph>(gi, g);
208
209
        auto e = add_edge(vertex(s, g), vertex(t, g), g).first;
        new_e = python::object(PythonEdge<Graph>(gp, e));
210
211
212
    }
};

213
python::object add_edge(GraphInterface& gi, size_t s, size_t t)
214
215
{
    python::object new_e;
216
    run_action<>()(gi, std::bind(add_new_edge(), std::placeholders::_1, std::ref(gi),
217
                                 s, t, std::ref(new_e)))();
218
219
220
221
222
223
    return new_e;
}

struct get_edge_descriptor
{
    template <class Graph>
224
    void operator()(const Graph&, const python::object& e,
225
                    typename GraphInterface::edge_t& edge,
226
                    bool& found)  const
227
    {
228
        PythonEdge<Graph>& pe = python::extract<PythonEdge<Graph>&>(e);
229
230
        pe.check_valid();
        edge = pe.get_descriptor();
231
        found = true;
232
233
234
    }
};

235
void remove_edge(GraphInterface& gi, const python::object& e)
236
{
237
    GraphInterface::edge_t de;
238
    bool found = false;
239
    run_action<>()(gi, std::bind(get_edge_descriptor(), std::placeholders::_1,
Tiago Peixoto's avatar
Tiago Peixoto committed
240
                                 std::ref(e), std::ref(de), std::ref(found)))();
241
    remove_edge(de, gi.get_graph());
242
    if (!found)
Tiago Peixoto's avatar
Tiago Peixoto committed
243
        throw ValueException("invalid edge descriptor");
244
245
}

246
247
248
struct get_edge_dispatch
{
    template <class Graph>
249
    void operator()(Graph& g, GraphInterface& gi, size_t s, size_t t,
250
251
                    bool all_edges, boost::python::list& es) const
    {
252
        auto gp = retrieve_graph_view<Graph>(gi, g);
253
254
255
        size_t k_t = is_directed::apply<Graph>::type::value ?
            in_degreeS()(t, g) : out_degree(t, g);
        if (out_degree(s, g) <= k_t)
256
        {
257
            for (auto e : out_edges_range(vertex(s, g), g))
258
            {
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
                if (target(e, g) == vertex(t, g))
                {
                    es.append(PythonEdge<Graph>(gp, e));
                    if (!all_edges)
                        break;
                }
            }
        }
        else
        {
            for (auto e : in_or_out_edges_range(vertex(t, g), g))
            {
                auto w = is_directed::apply<Graph>::type::value ?
                    source(e, g) : target(e, g);
                if (w == vertex(s, g))
                {
                    if (!is_directed::apply<Graph>::type::value)
                        e.inv ^= true;
                    es.append(PythonEdge<Graph>(gp, e));
                    if (!all_edges)
                        break;
                }
281
282
283
284
285
            }
        }
    }
};

286
python::object get_edge(GraphInterface& gi, size_t s, size_t t, bool all_edges)
287
288
{
    python::list es;
289
    run_action<>()(gi, std::bind(get_edge_dispatch(), std::placeholders::_1,
290
291
                                 std::ref(gi), s, t, all_edges,
                                 std::ref(es)))();
292
293
294
295
    return es;
}


296
297
struct get_degree_map
{
298
299
    template <class Graph, class DegS, class Weight>
    void operator()(const Graph& g, python::object& odeg_map, DegS deg, Weight weight) const
300
    {
301
        typedef typename detail::get_weight_type<Weight>::type weight_t;
Tiago Peixoto's avatar
Tiago Peixoto committed
302
        typedef typename mpl::if_<std::is_same<weight_t, size_t>, int32_t, weight_t>::type deg_t;
303
304
305
306
307
308
309
310

        typedef typename property_map_type::apply<deg_t,
                                                  GraphInterface::vertex_index_map_t>::type
            map_t;

        map_t cdeg_map(get(vertex_index, g));
        typename map_t::unchecked_t deg_map = cdeg_map.get_unchecked(num_vertices(g));

311
        int i, N = num_vertices(g);
312
        #pragma omp parallel for default(shared) private(i) schedule(runtime) if (N > 100)
313
314
        for (i = 0; i < N; ++i)
        {
315
316
            auto v = vertex(i, g);
            if (!is_valid_vertex(v, g))
317
                continue;
318
            deg_map[v] = deg(v, g, weight);
319
        }
320
321

        odeg_map = python::object(PythonPropertyMap<map_t>(cdeg_map));
322
323
324
    }
};

325
python::object GraphInterface::degree_map(string deg, boost::any weight) const
326
327
{

328
329
    python::object deg_map;

330
331
    typedef mpl::push_back<edge_scalar_properties,
                           detail::no_weightS>::type weight_t;
332
333
    if (weight.empty())
        weight = detail::no_weightS();
334
335

    if (deg == "in")
336
        run_action<>()(const_cast<GraphInterface&>(*this),
337
338
                       std::bind(get_degree_map(), std::placeholders::_1,
                                 std::ref(deg_map), in_degreeS(), std::placeholders::_2), weight_t())
339
            (weight);
340
    else if (deg == "out")
341
        run_action<>()(const_cast<GraphInterface&>(*this),
342
343
                       std::bind(get_degree_map(), std::placeholders::_1,
                                 std::ref(deg_map), out_degreeS(), std::placeholders::_2), weight_t())
344
            (weight);
345
    else if (deg == "total")
346
        run_action<>()(const_cast<GraphInterface&>(*this),
347
348
                       std::bind(get_degree_map(), std::placeholders::_1,
                                 std::ref(deg_map), total_degreeS(), std::placeholders::_2), weight_t())
349
350
            (weight);
    return deg_map;
351
352
}

353
354
355
356
357
//
// Below are the functions with will properly register all the types to python,
// for every filter, type, etc.
//

358
359
360
// this will register all the Vertex/Edge classes to python
struct export_python_interface
{
361
362
363
    template <class Graph, class GraphViews>
    void operator()(Graph* gp, python::list vclasses,
                    python::list eclasses, GraphViews) const
364
365
    {
        using namespace boost::python;
366

367
368
        class_<PythonVertex<Graph>, bases<VertexBase>> vclass("Vertex", no_init);
        vclass
369
            .def("__in_degree", &PythonVertex<Graph>::get_in_degree,
370
                 "Return the in-degree.")
371
            .def("__weighted_in_degree", &PythonVertex<Graph>::get_weighted_in_degree,
372
                 "Return the weighted in-degree.")
373
            .def("__out_degree", &PythonVertex<Graph>::get_out_degree,
374
                 "Return the out-degree.")
375
            .def("__weighted_out_degree", &PythonVertex<Graph>::get_weighted_out_degree,
376
                 "Return the weighted out-degree.")
377
            .def("in_edges", &PythonVertex<Graph>::in_edges,
378
                 "Return an iterator over the in-edges.")
379
            .def("out_edges", &PythonVertex<Graph>::out_edges,
380
                 "Return an iterator over the out-edges.")
381
            .def("is_valid", &PythonVertex<Graph>::is_valid,
382
                 "Return whether the vertex is valid.")
383
384
385
386
387
            .def("graph_ptr", &PythonVertex<Graph>::get_graph_ptr)
            .def("graph_type", &PythonVertex<Graph>::get_graph_type)
            .def("__str__", &PythonVertex<Graph>::get_string)
            .def("__int__", &PythonVertex<Graph>::get_index)
            .def("__hash__", &PythonVertex<Graph>::get_hash);
388
389
390
391
392

        vclasses.append(vclass);

        class_<PythonEdge<Graph>, bases<EdgeBase>> eclass("Edge", no_init);
        eclass
393
            .def("source", &PythonEdge<Graph>::get_source,
394
                 "Return the source vertex.")
395
            .def("target", &PythonEdge<Graph>::get_target,
396
                 "Return the target vertex.")
397
            .def("is_valid", &PythonEdge<Graph>::is_valid,
398
                 "Return whether the edge is valid.")
399
400
            .def("graph_ptr", &PythonEdge<Graph>::get_graph_ptr)
            .def("graph_type", &PythonEdge<Graph>::get_graph_type)
401
402
            .def("__str__", &PythonEdge<Graph>::get_string)
            .def("__hash__", &PythonEdge<Graph>::get_hash);
403

404
405
406
407
408
409
        boost::mpl::for_each<GraphViews>(std::bind(export_python_interface(),
                                                   gp, std::placeholders::_1,
                                                   std::ref(eclass)));

        eclasses.append(eclass);

410
        typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
411
412
413
414
        class_<PythonIterator<Graph, PythonVertex<Graph>, vertex_iterator> >
            ("VertexIterator", no_init)
            .def("__iter__", objects::identity_function())
            .def("__next__", &PythonIterator<Graph, PythonVertex<Graph>,
415
                                             vertex_iterator>::next)
416
            .def("next", &PythonIterator<Graph, PythonVertex<Graph>,
417
                                         vertex_iterator>::next);
418

419
        typedef typename graph_traits<Graph>::edge_iterator edge_iterator;
420
        class_<PythonIterator<Graph, PythonEdge<Graph>,
421
422
                              edge_iterator> >("EdgeIterator", no_init)
            .def("__iter__", objects::identity_function())
423
            .def("__next__", &PythonIterator<Graph, PythonEdge<Graph>,
424
                                             edge_iterator>::next)
425
            .def("next", &PythonIterator<Graph, PythonEdge<Graph>,
426
                                         edge_iterator>::next);
427
428
429

        typedef typename graph_traits<Graph>::out_edge_iterator
            out_edge_iterator;
430
        class_<PythonIterator<Graph, PythonEdge<Graph>,
431
432
                              out_edge_iterator> >("OutEdgeIterator", no_init)
            .def("__iter__", objects::identity_function())
433
            .def("__next__", &PythonIterator<Graph, PythonEdge<Graph>,
434
                                             out_edge_iterator>::next)
435
            .def("next", &PythonIterator<Graph, PythonEdge<Graph>,
436
                                         out_edge_iterator>::next);
437
438
439

        typedef typename graph_traits<Graph>::directed_category
            directed_category;
Tiago Peixoto's avatar
Tiago Peixoto committed
440
441
        typedef typename std::is_convertible<directed_category,
                                             boost::directed_tag>::type is_directed;
442
443
444
        if (is_directed::value)
        {
            typedef typename in_edge_iteratorS<Graph>::type in_edge_iterator;
445
            class_<PythonIterator<Graph, PythonEdge<Graph>,
446
447
                                  in_edge_iterator> >("InEdgeIterator", no_init)
                .def("__iter__", objects::identity_function())
448
                .def("__next__", &PythonIterator<Graph, PythonEdge<Graph>,
449
                                                 in_edge_iterator>::next)
450
                .def("next", &PythonIterator<Graph, PythonEdge<Graph>,
451
                                             in_edge_iterator>::next);
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
481
482
483
484
485
486
487
488
489
490

    template <class Graph, class OGraph, class Eclass>
    void operator()(Graph*, OGraph*, Eclass& eclass) const
    {
        std::function<bool(const PythonEdge<Graph>&,
                           const PythonEdge<OGraph>&)> eq =
            [] (const PythonEdge<Graph>& e1,
                const PythonEdge<OGraph>& e2) -> bool { return e1 == e2; };
        std::function<bool(const PythonEdge<Graph>& e1,
                           const PythonEdge<OGraph>&)> ne =
            [] (const PythonEdge<Graph>& e1,
                const PythonEdge<OGraph>& e2) -> bool { return e1 != e2; };
        std::function<bool(const PythonEdge<Graph>&,
                           const PythonEdge<OGraph>&)> gt =
            [] (const PythonEdge<Graph>& e1,
                const PythonEdge<OGraph>& e2) -> bool { return e1 > e2; };
        std::function<bool(const PythonEdge<Graph>&,
                           const PythonEdge<OGraph>&)> lt =
            [] (const PythonEdge<Graph>& e1,
                const PythonEdge<OGraph>& e2) -> bool { return e1 < e2; };
        std::function<bool(const PythonEdge<Graph>&,
                           const PythonEdge<OGraph>&)> ge =
            [] (const PythonEdge<Graph>& e1,
                const PythonEdge<OGraph>& e2) -> bool { return e1 >= e2; };
        std::function<bool(const PythonEdge<Graph>&,
                           const PythonEdge<OGraph>&)> le =
            [] (const PythonEdge<Graph>& e1,
                const PythonEdge<OGraph>& e2) -> bool { return e1 <= e2; };

        eclass
            .def("__eq__", eq)
            .def("__ne__", ne)
            .def("__lt__", lt)
            .def("__gt__", gt)
            .def("__le__", le)
            .def("__ge__", ge);
    }
491
492
};

493
494
495
496
PythonPropertyMap<GraphInterface::vertex_index_map_t>
get_vertex_index(GraphInterface& g)
{
    return PythonPropertyMap<GraphInterface::vertex_index_map_t>
497
        (g.get_vertex_index());
498
499
500
}

PythonPropertyMap<GraphInterface::edge_index_map_t>
501
do_get_edge_index(GraphInterface& g)
502
503
{
    return PythonPropertyMap<GraphInterface::edge_index_map_t>
504
        (g.get_edge_index());
505
506
}

507
void do_add_edge_list(GraphInterface& gi, python::object aedge_list,
508
                      python::object eprops);
509
510

void do_add_edge_list_hashed(GraphInterface& gi, python::object aedge_list,
511
                             boost::any& vertex_map, bool is_str,
512
                             python::object eprops);
513
514

void do_add_edge_list_iter(GraphInterface& gi, python::object edge_list,
515
                           python::object eprops);
516

517
518
} // namespace graph_tool

519
520
// register everything

521
522
void export_python_properties();

523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
python::list* _vlist(0);
python::list* _elist(0);

python::list get_vlist()
{
    if (_vlist == nullptr)
        _vlist = new python::list();
    return *_vlist;
}

python::list get_elist()
{
    if (_elist == nullptr)
        _elist = new python::list();
    return *_elist;
}

540
void export_python_interface()
541
{
542
543
    using namespace boost::python;

544
    class_<VertexBase>("VertexBase", no_init);
545
    class_<EdgeBase>("EdgeBase", no_init);
546

547
    typedef boost::mpl::transform<graph_tool::all_graph_views,
548
                                  boost::mpl::quote1<std::add_const> >::type const_graph_views;
549
    typedef boost::mpl::transform<graph_tool::all_graph_views,
550
551
552
553
                                  boost::mpl::quote1<std::add_pointer> >::type all_graph_views;
    typedef boost::mpl::transform<const_graph_views,
                                  boost::mpl::quote1<std::add_pointer> >::type all_const_graph_views;
    typedef boost::mpl::joint_view<all_graph_views, all_const_graph_views>::type graph_views;
Tiago Peixoto's avatar
Tiago Peixoto committed
554
    boost::mpl::for_each<graph_views>(std::bind(graph_tool::export_python_interface(),
555
                                                std::placeholders::_1, get_vlist(),
556
                                                get_elist(), graph_views()));
557
    export_python_properties();
558
559
560
561
562
563
    def("new_vertex_property",
        &new_property<GraphInterface::vertex_index_map_t>);
    def("new_edge_property", &new_property<GraphInterface::edge_index_map_t>);
    def("new_graph_property",
        &new_property<ConstantPropertyMap<size_t,graph_property_tag> >);

564
565
566
567
568
569
    def("get_vertex", get_vertex);
    def("get_vertices", get_vertices);
    def("get_edges", get_edges);
    def("add_vertex", graph_tool::add_vertex);
    def("add_edge", graph_tool::add_edge);
    def("remove_vertex", graph_tool::remove_vertex);
570
    def("remove_vertex_array", graph_tool::remove_vertex_array);
571
    def("clear_vertex", graph_tool::clear_vertex);
572
    def("remove_edge", graph_tool::remove_edge);
573
    def("add_edge_list", graph_tool::do_add_edge_list);
574
    def("add_edge_list_hashed", graph_tool::do_add_edge_list_hashed);
575
    def("add_edge_list_iter", graph_tool::do_add_edge_list_iter);
576
    def("get_edge", get_edge);
577

578
    def("get_vertex_index", get_vertex_index);
579
    def("get_edge_index", do_get_edge_index);
580
581
582

    def("get_vlist", get_vlist);
    def("get_elist", get_elist);
583
584
585
586
587
588
589

#ifdef HAVE_BOOST_COROUTINE
    class_<CoroGenerator>("CoroGenerator", no_init)
        .def("__iter__", objects::identity_function())
        .def("next", &CoroGenerator::next)
        .def("__next__", &CoroGenerator::next);
#endif
590
}