graph_python_interface.cc 17.1 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-2014 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
20
21
#include "graph_filtering.hh"
#include "graph.hh"
#include "graph_python_interface.hh"

22
#include <boost/python.hpp>
23
#include <set>
24
25
26
27
28

using namespace std;
using namespace boost;
using namespace graph_tool;

29
30
namespace boost
{
Tiago Peixoto's avatar
Tiago Peixoto committed
31
32
33
34
size_t hash_value(const boost::python::object& o)
{
    return std::hash<boost::python::object>()(o);
}
35
36
}

37
38
39
namespace graph_tool
{

40
41
42
struct get_vertex_iterator
{
    template <class Graph>
43
    void operator()(Graph& g, python::object& pg,
44
45
46
                    python::object& iter) const
    {
        typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
47
        iter = python::object(PythonIterator<PythonVertex,
48
                                             vertex_iterator>(pg, vertices(g)));
49
50
51
    }
};

52
python::object get_vertices(python::object g)
53
{
54
    GraphInterface& gi = python::extract<GraphInterface&>(g().attr("_Graph__graph"));
55
    python::object iter;
Tiago Peixoto's avatar
Tiago Peixoto committed
56
57
58
    run_action<>()(gi, std::bind(get_vertex_iterator(), placeholders::_1,
                                 std::ref(g),
                                 std::ref(iter)))();
59
60
61
    return iter;
}

62
63
64
struct get_vertex_soft
{
    template <class Graph>
65
    void operator()(Graph& g,
66
                    python::object& pg,
67
68
                    size_t i, python::object& v) const
    {
69
        v = python::object(PythonVertex(pg, vertex(i, g)));
70
71
72
73
74
75
    }
};

struct get_vertex_hard
{
    template <class Graph>
76
    void operator()(Graph& g, python::object& pg, size_t i,
77
78
79
80
81
82
83
                    python::object& v) const
    {
        size_t c = 0;
        typename graph_traits<Graph>::vertex_iterator vi, v_end;
        for (tie(vi, v_end) = vertices(g); vi != v_end; ++vi)
        {
            if (c == i)
84
            {
85
                v = python::object(PythonVertex(pg, *vi));
86
87
                return;
            }
88
89
            ++c;
        }
90
        v = python::object(PythonVertex(pg,
91
                                        graph_traits<Graph>::null_vertex()));
92
93
94
    }
};

95
python::object get_vertex(python::object g, size_t i)
96
{
97
    GraphInterface& gi = python::extract<GraphInterface&>(g().attr("_Graph__graph"));
98
    python::object v;
99
100
    if (gi.IsVertexFilterActive())
        run_action<>()(gi,
Tiago Peixoto's avatar
Tiago Peixoto committed
101
102
                       std::bind(get_vertex_hard(), placeholders::_1,
                                 std::ref(g), i, std::ref(v)))();
103
    else
104
        run_action<>()(gi,
Tiago Peixoto's avatar
Tiago Peixoto committed
105
106
                       std::bind(get_vertex_soft(), placeholders::_1,
                                 std::ref(g), i, std::ref(v)))();
107
108
109
    return v;
}

110
111
112
struct get_edge_iterator
{
    template <class Graph>
113
114
    void operator()(Graph& g, const python::object& pg, python::object& iter)
        const
115
116
    {
        typedef typename graph_traits<Graph>::edge_iterator edge_iterator;
117
        iter = python::object(PythonIterator<PythonEdge<Graph>,
118
                                             edge_iterator>(pg, edges(g)));
119
120
121
    }
};

122
python::object get_edges(python::object g)
123
{
124
    GraphInterface& gi = python::extract<GraphInterface&>(g().attr("_Graph__graph"));
125
    python::object iter;
126
    run_action<>()(gi,
Tiago Peixoto's avatar
Tiago Peixoto committed
127
128
                   std::bind(get_edge_iterator(), placeholders::_1,
                             std::ref(g), std::ref(iter)))();
129
130
131
    return iter;
}

132
python::object add_vertex(python::object g, size_t n)
133
{
134
    GraphInterface& gi = python::extract<GraphInterface&>(g().attr("_Graph__graph"));
135
136
137
138
139
140
141

    if (n > 1)
    {
        for (size_t i = 0; i < n; ++i)
            add_vertex(gi.GetGraph());
        return python::object();
    }
142
    return python::object(PythonVertex(g, add_vertex(gi.GetGraph())));
143
144
}

145
struct shift_vertex_property
146
{
147
    template <class Graph, class PropertyMap>
148
    void operator()(const Graph& g, size_t vi, PropertyMap pmap)
149
150
        const
    {
151
        size_t N = num_vertices(g);
152
153
        if (N <= 1 || vi >= N - 1)
            return;
154
155
156
157
        for (size_t i = vi; i < N-1; ++i)
        {
            pmap[vertex(i, g)] = pmap[vertex(i+1, g)];
        }
158
159
160
    }
};

161
void remove_vertex(GraphInterface& gi, const python::object& v, bool fast)
162
{
163
    PythonVertex& pv = python::extract<PythonVertex&>(v);
164
    pv.CheckValid();
165
    GraphInterface::vertex_t dv = pv.GetDescriptor();
166
167
    pv.SetValid(false);

168
169
170
171
    if (fast)
        remove_vertex_fast(dv, gi.GetGraph());
    else
        remove_vertex(dv, gi.GetGraph());
172
173
174
175
}

struct add_new_edge
{
176
    template <class Graph, class EdgeIndexMap>
177
    void operator()(Graph& g, python::object& pg, GraphInterface&,
178
                    const PythonVertex& s, const PythonVertex& t,
179
                    EdgeIndexMap, python::object& new_e) const
180
    {
181
        typename graph_traits<Graph>::edge_descriptor e =
182
            add_edge(s.GetDescriptor(), t.GetDescriptor(), g).first;
183
        new_e = python::object(PythonEdge<Graph>(pg, e));
184
185
186
    }
};

187
188
python::object add_edge(python::object g, const python::object& s,
                        const python::object& t)
189
{
190
191
    PythonVertex& src = python::extract<PythonVertex&>(s);
    PythonVertex& tgt = python::extract<PythonVertex&>(t);
192
193
    src.CheckValid();
    tgt.CheckValid();
194
    GraphInterface& gi = python::extract<GraphInterface&>(g().attr("_Graph__graph"));
195
    python::object new_e;
Tiago Peixoto's avatar
Tiago Peixoto committed
196
197
198
    run_action<>()(gi, std::bind(add_new_edge(), placeholders::_1, std::ref(g),
                                 std::ref(gi), src, tgt, gi.GetEdgeIndex(),
                                 std::ref(new_e)))();
199
200
201
202
203
204
    return new_e;
}

struct get_edge_descriptor
{
    template <class Graph>
205
    void operator()(const Graph& g, const python::object& e,
206
                    typename GraphInterface::edge_t& edge,
207
                    bool& found)  const
208
    {
209
        typedef typename graph_traits<Graph>::edge_descriptor edge_t;
210
211
212
        PythonEdge<Graph>& pe = python::extract<PythonEdge<Graph>&>(e);
        pe.CheckValid();
        pe.SetValid(false);
213
        edge = pe.GetDescriptor();
214
        found = true;
215
216
217
    }
};

218
void remove_edge(GraphInterface& gi, const python::object& e)
219
{
220
    GraphInterface::edge_t de;
221
    bool found = false;
Tiago Peixoto's avatar
Tiago Peixoto committed
222
223
    run_action<>()(gi, std::bind(get_edge_descriptor(), placeholders::_1,
                                 std::ref(e), std::ref(de), std::ref(found)))();
224
    remove_edge(de, gi.GetGraph());
225
    if (!found)
Tiago Peixoto's avatar
Tiago Peixoto committed
226
        throw ValueException("invalid edge descriptor");
227
228
}

229
230
struct get_degree_map
{
231
232
    template <class Graph, class DegS, class Weight>
    void operator()(const Graph& g, python::object& odeg_map, DegS deg, Weight weight) const
233
    {
234
        typedef typename detail::get_weight_type<Weight>::type weight_t;
Tiago Peixoto's avatar
Tiago Peixoto committed
235
        typedef typename mpl::if_<std::is_same<weight_t, size_t>, int32_t, weight_t>::type deg_t;
236
237
238
239
240
241
242
243

        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));

244
        int i, N = num_vertices(g);
245
        #pragma omp parallel for default(shared) private(i) schedule(runtime) if (N > 100)
246
247
248
249
250
        for (i = 0; i < N; ++i)
        {
            typename graph_traits<Graph>::vertex_descriptor v = vertex(i, g);
            if (v == graph_traits<Graph>::null_vertex())
                continue;
251
            deg_map[v] = deg(v, g, weight);
252
        }
253
254

        odeg_map = python::object(PythonPropertyMap<map_t>(cdeg_map));
255
256
257
    }
};

258
python::object GraphInterface::DegreeMap(string deg, boost::any weight) const
259
260
{

261
262
    python::object deg_map;

263
264
    typedef mpl::push_back<edge_scalar_properties,
                           detail::no_weightS>::type weight_t;
265
266
    if (weight.empty())
        weight = detail::no_weightS();
267
268

    if (deg == "in")
269
        run_action<>()(const_cast<GraphInterface&>(*this),
Tiago Peixoto's avatar
Tiago Peixoto committed
270
271
                       std::bind(get_degree_map(), placeholders::_1,
                                 std::ref(deg_map), in_degreeS(), placeholders::_2), weight_t())
272
            (weight);
273
    else if (deg == "out")
274
        run_action<>()(const_cast<GraphInterface&>(*this),
Tiago Peixoto's avatar
Tiago Peixoto committed
275
276
                       std::bind(get_degree_map(), placeholders::_1,
                                 std::ref(deg_map), out_degreeS(), placeholders::_2), weight_t())
277
            (weight);
278
    else if (deg == "total")
279
        run_action<>()(const_cast<GraphInterface&>(*this),
Tiago Peixoto's avatar
Tiago Peixoto committed
280
281
                       std::bind(get_degree_map(), placeholders::_1,
                                 std::ref(deg_map), total_degreeS(), placeholders::_2), weight_t())
282
283
            (weight);
    return deg_map;
284
285
}

286
287
288
289
290
//
// Below are the functions with will properly register all the types to python,
// for every filter, type, etc.
//

291
292
293
294
// this will register all the Vertex/Edge classes to python
struct export_python_interface
{
    template <class Graph>
295
    void operator()(const Graph*, set<string>& v_iterators) const
296
297
    {
        using namespace boost::python;
298

299
        class_<PythonEdge<Graph>, bases<EdgeBase> >
Tiago Peixoto's avatar
Tiago Peixoto committed
300
            ("Edge", no_init)
301
            .def("source", &PythonEdge<Graph>::GetSource,
302
                 "Return the source vertex.")
303
            .def("target", &PythonEdge<Graph>::GetTarget,
304
                 "Return the target vertex.")
305
            .def("is_valid", &PythonEdge<Graph>::IsValid,
306
                 "Return whether the edge is valid.")
307
308
            .def("get_graph", &PythonEdge<Graph>::GetGraph,
                 "Return the graph to which the edge belongs.")
309
310
            .def(python::self == python::self)
            .def(python::self != python::self)
311
            .def("__str__", &PythonEdge<Graph>::GetString)
312
313
314
            .def("__hash__", &PythonEdge<Graph>::GetHash);

        typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
315
        if (v_iterators.find(typeid(vertex_iterator).name()) ==
316
317
            v_iterators.end())
        {
318
319
            class_<PythonIterator<PythonVertex, vertex_iterator> >
                ("VertexIterator", no_init)
320
                .def("__iter__", objects::identity_function())
321
322
                .def("__next__", &PythonIterator<PythonVertex,
                                                 vertex_iterator>::Next)
323
324
325
326
327
                .def("next", &PythonIterator<PythonVertex,
                                             vertex_iterator>::Next);
            v_iterators.insert(typeid(vertex_iterator).name());
        }

328
        typedef typename graph_traits<Graph>::edge_iterator edge_iterator;
329
        class_<PythonIterator<PythonEdge<Graph>,
330
331
                              edge_iterator> >("EdgeIterator", no_init)
            .def("__iter__", objects::identity_function())
332
333
            .def("__next__", &PythonIterator<PythonEdge<Graph>,
                                         edge_iterator>::Next)
334
            .def("next", &PythonIterator<PythonEdge<Graph>,
335
336
337
338
                                         edge_iterator>::Next);

        typedef typename graph_traits<Graph>::out_edge_iterator
            out_edge_iterator;
339
        class_<PythonIterator<PythonEdge<Graph>,
340
341
                              out_edge_iterator> >("OutEdgeIterator", no_init)
            .def("__iter__", objects::identity_function())
342
343
            .def("__next__", &PythonIterator<PythonEdge<Graph>,
                                             out_edge_iterator>::Next)
344
            .def("next", &PythonIterator<PythonEdge<Graph>,
345
346
347
348
                                         out_edge_iterator>::Next);

        typedef typename graph_traits<Graph>::directed_category
            directed_category;
Tiago Peixoto's avatar
Tiago Peixoto committed
349
350
        typedef typename std::is_convertible<directed_category,
                                             boost::directed_tag>::type is_directed;
351
352
353
        if (is_directed::value)
        {
            typedef typename in_edge_iteratorS<Graph>::type in_edge_iterator;
354
            class_<PythonIterator<PythonEdge<Graph>,
355
356
                                  in_edge_iterator> >("InEdgeIterator", no_init)
                .def("__iter__", objects::identity_function())
357
358
                .def("__next__", &PythonIterator<PythonEdge<Graph>,
                                                 in_edge_iterator>::Next)
359
                .def("next", &PythonIterator<PythonEdge<Graph>,
360
361
362
363
364
                                             in_edge_iterator>::Next);
        }
    }
};

365
366
367
368
PythonPropertyMap<GraphInterface::vertex_index_map_t>
get_vertex_index(GraphInterface& g)
{
    return PythonPropertyMap<GraphInterface::vertex_index_map_t>
369
        (g.GetVertexIndex());
370
371
372
}

PythonPropertyMap<GraphInterface::edge_index_map_t>
373
do_get_edge_index(GraphInterface& g)
374
375
{
    return PythonPropertyMap<GraphInterface::edge_index_map_t>
376
        (g.GetEdgeIndex());
377
378
}

379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429

template <class ValueList>
struct add_edge_list
{
    template <class Graph>
    void operator()(Graph& g, python::object aedge_list, bool& found) const
    {
        boost::mpl::for_each<ValueList>(std::bind(dispatch(), std::ref(g),
                                                  std::ref(aedge_list),
                                                  std::ref(found), placeholders::_1));
    }

    struct dispatch
    {
        template <class Graph, class Value>
        void operator()(Graph& g, python::object& aedge_list, bool& found, Value) const
        {
            try
            {
                boost::multi_array_ref<Value, 2> edge_list = get_array<Value, 2>(aedge_list);

                if (edge_list.shape()[1] < 2)
                    throw GraphException("Second dimension in edge list must be of size (at least) two");

                for (size_t i = 0; i < edge_list.shape()[0]; ++i)
                {
                    size_t s = edge_list[i][0];
                    size_t t = edge_list[i][1];
                    while (s >= num_vertices(g) || t >= num_vertices(g))
                        add_vertex(g);
                    add_edge(vertex(s, g), vertex(t, g), g);
                }
                found = true;
            }
            catch (invalid_numpy_conversion& e) {}
        }
    };
};

void do_add_edge_list(GraphInterface& gi, python::object aedge_list)
{
    typedef mpl::vector<bool, uint8_t, uint32_t, int16_t, int32_t, int64_t, uint64_t,
                        unsigned long int, double, long double> vals_t;
    bool found = false;
    run_action<>()(gi, std::bind(add_edge_list<vals_t>(), placeholders::_1, aedge_list,
                                 std::ref(found)))();
    if (!found)
        throw GraphException("Invalid type for edge list; must be two-dimensional with a scalar type");
}


430
431
} // namespace graph_tool

432
433
// register everything

434
435
436
void export_python_properties();

void export_python_interface()
437
{
438
439
    using namespace boost::python;

440
    class_<PythonVertex>
Tiago Peixoto's avatar
Tiago Peixoto committed
441
        ("Vertex", no_init)
442
        .def("in_degree", &PythonVertex::GetInDegree,
443
             "Return the in-degree.")
444
        .def("out_degree", &PythonVertex::GetOutDegree,
445
             "Return the out-degree.")
446
        .def("out_edges", &PythonVertex::OutEdges,
447
             "Return an iterator over the out-edges.")
448
        .def("in_edges", &PythonVertex::InEdges,
449
             "Return an iterator over the in-edges.")
450
        .def("is_valid", &PythonVertex::IsValid,
451
             "Return whether the vertex is valid.")
452
453
        .def("get_graph", &PythonVertex::GetGraph,
             "Return the graph to which the vertex belongs.")
Tiago Peixoto's avatar
Tiago Peixoto committed
454
455
        .def(boost::python::self == boost::python::self)
        .def(boost::python::self != boost::python::self)
456
        .def("__str__", &PythonVertex::GetString)
457
        .def("__int__", &PythonVertex::GetIndex)
458
        .def("__hash__", &PythonVertex::GetHash);
459
    class_<EdgeBase>("EdgeBase", no_init);
460
461

    set<string> v_iterators;
Tiago Peixoto's avatar
Tiago Peixoto committed
462
463
464
465
    typedef boost::mpl::transform<graph_tool::detail::all_graph_views,
                                  boost::mpl::quote1<std::add_pointer> >::type graph_views;
    boost::mpl::for_each<graph_views>(std::bind(graph_tool::export_python_interface(),
                                      placeholders::_1, std::ref(v_iterators)));
466
    export_python_properties();
467
468
469
470
471
472
    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> >);

473
474
475
476
477
478
479
    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);
    def("remove_edge", graph_tool::remove_edge);
480
    def("add_edge_list", graph_tool::do_add_edge_list);
481

482
    def("get_vertex_index", get_vertex_index);
483
    def("get_edge_index", do_get_edge_index);
484
}