graph_python_interface.cc 16.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-2015 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
}


146
void remove_vertex(GraphInterface& gi, const python::object& oindex, bool fast)
147
{
148
149
    boost::multi_array_ref<int64_t,1> index = get_array<int64_t,1>(oindex);
    auto& g = gi.GetGraph();
150
    if (fast)
151
152
153
154
    {
        for (auto v : index)
            remove_vertex_fast(vertex(v, g), g);
    }
155
    else
156
157
158
159
    {
        for (auto v : index)
            remove_vertex(vertex(v, g), g);
    }
160
161
162
163
}

struct add_new_edge
{
164
    template <class Graph, class EdgeIndexMap>
165
    void operator()(Graph& g, python::object& pg, GraphInterface&,
166
                    const PythonVertex& s, const PythonVertex& t,
167
                    EdgeIndexMap, python::object& new_e) const
168
    {
169
        typename graph_traits<Graph>::edge_descriptor e =
170
            add_edge(s.GetDescriptor(), t.GetDescriptor(), g).first;
171
        new_e = python::object(PythonEdge<Graph>(pg, e));
172
173
174
    }
};

175
176
python::object add_edge(python::object g, const python::object& s,
                        const python::object& t)
177
{
178
179
    PythonVertex& src = python::extract<PythonVertex&>(s);
    PythonVertex& tgt = python::extract<PythonVertex&>(t);
180
181
    src.CheckValid();
    tgt.CheckValid();
182
    GraphInterface& gi = python::extract<GraphInterface&>(g().attr("_Graph__graph"));
183
    python::object new_e;
Tiago Peixoto's avatar
Tiago Peixoto committed
184
185
186
    run_action<>()(gi, std::bind(add_new_edge(), placeholders::_1, std::ref(g),
                                 std::ref(gi), src, tgt, gi.GetEdgeIndex(),
                                 std::ref(new_e)))();
187
188
189
190
191
192
    return new_e;
}

struct get_edge_descriptor
{
    template <class Graph>
193
    void operator()(const Graph& g, const python::object& e,
194
                    typename GraphInterface::edge_t& edge,
195
                    bool& found)  const
196
    {
197
        typedef typename graph_traits<Graph>::edge_descriptor edge_t;
198
199
200
        PythonEdge<Graph>& pe = python::extract<PythonEdge<Graph>&>(e);
        pe.CheckValid();
        pe.SetValid(false);
201
        edge = pe.GetDescriptor();
202
        found = true;
203
204
205
    }
};

206
void remove_edge(GraphInterface& gi, const python::object& e)
207
{
208
    GraphInterface::edge_t de;
209
    bool found = false;
Tiago Peixoto's avatar
Tiago Peixoto committed
210
211
    run_action<>()(gi, std::bind(get_edge_descriptor(), placeholders::_1,
                                 std::ref(e), std::ref(de), std::ref(found)))();
212
    remove_edge(de, gi.GetGraph());
213
    if (!found)
Tiago Peixoto's avatar
Tiago Peixoto committed
214
        throw ValueException("invalid edge descriptor");
215
216
}

217
218
struct get_degree_map
{
219
220
    template <class Graph, class DegS, class Weight>
    void operator()(const Graph& g, python::object& odeg_map, DegS deg, Weight weight) const
221
    {
222
        typedef typename detail::get_weight_type<Weight>::type weight_t;
Tiago Peixoto's avatar
Tiago Peixoto committed
223
        typedef typename mpl::if_<std::is_same<weight_t, size_t>, int32_t, weight_t>::type deg_t;
224
225
226
227
228
229
230
231

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

232
        int i, N = num_vertices(g);
233
        #pragma omp parallel for default(shared) private(i) schedule(runtime) if (N > 100)
234
235
236
237
238
        for (i = 0; i < N; ++i)
        {
            typename graph_traits<Graph>::vertex_descriptor v = vertex(i, g);
            if (v == graph_traits<Graph>::null_vertex())
                continue;
239
            deg_map[v] = deg(v, g, weight);
240
        }
241
242

        odeg_map = python::object(PythonPropertyMap<map_t>(cdeg_map));
243
244
245
    }
};

246
python::object GraphInterface::DegreeMap(string deg, boost::any weight) const
247
248
{

249
250
    python::object deg_map;

251
252
    typedef mpl::push_back<edge_scalar_properties,
                           detail::no_weightS>::type weight_t;
253
254
    if (weight.empty())
        weight = detail::no_weightS();
255
256

    if (deg == "in")
257
        run_action<>()(const_cast<GraphInterface&>(*this),
Tiago Peixoto's avatar
Tiago Peixoto committed
258
259
                       std::bind(get_degree_map(), placeholders::_1,
                                 std::ref(deg_map), in_degreeS(), placeholders::_2), weight_t())
260
            (weight);
261
    else if (deg == "out")
262
        run_action<>()(const_cast<GraphInterface&>(*this),
Tiago Peixoto's avatar
Tiago Peixoto committed
263
264
                       std::bind(get_degree_map(), placeholders::_1,
                                 std::ref(deg_map), out_degreeS(), placeholders::_2), weight_t())
265
            (weight);
266
    else if (deg == "total")
267
        run_action<>()(const_cast<GraphInterface&>(*this),
Tiago Peixoto's avatar
Tiago Peixoto committed
268
269
                       std::bind(get_degree_map(), placeholders::_1,
                                 std::ref(deg_map), total_degreeS(), placeholders::_2), weight_t())
270
271
            (weight);
    return deg_map;
272
273
}

274
275
276
277
278
//
// Below are the functions with will properly register all the types to python,
// for every filter, type, etc.
//

279
280
281
282
// this will register all the Vertex/Edge classes to python
struct export_python_interface
{
    template <class Graph>
283
    void operator()(const Graph*, set<string>& v_iterators) const
284
285
    {
        using namespace boost::python;
286

287
        class_<PythonEdge<Graph>, bases<EdgeBase> >
Tiago Peixoto's avatar
Tiago Peixoto committed
288
            ("Edge", no_init)
289
            .def("source", &PythonEdge<Graph>::GetSource,
290
                 "Return the source vertex.")
291
            .def("target", &PythonEdge<Graph>::GetTarget,
292
                 "Return the target vertex.")
293
            .def("is_valid", &PythonEdge<Graph>::IsValid,
294
                 "Return whether the edge is valid.")
295
296
            .def("get_graph", &PythonEdge<Graph>::GetGraph,
                 "Return the graph to which the edge belongs.")
297
            .def("__str__", &PythonEdge<Graph>::GetString)
298
299
300
            .def("__hash__", &PythonEdge<Graph>::GetHash);

        typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
301
        if (v_iterators.find(typeid(vertex_iterator).name()) ==
302
303
            v_iterators.end())
        {
304
305
            class_<PythonIterator<PythonVertex, vertex_iterator> >
                ("VertexIterator", no_init)
306
                .def("__iter__", objects::identity_function())
307
308
                .def("__next__", &PythonIterator<PythonVertex,
                                                 vertex_iterator>::Next)
309
310
311
312
313
                .def("next", &PythonIterator<PythonVertex,
                                             vertex_iterator>::Next);
            v_iterators.insert(typeid(vertex_iterator).name());
        }

314
        typedef typename graph_traits<Graph>::edge_iterator edge_iterator;
315
        class_<PythonIterator<PythonEdge<Graph>,
316
317
                              edge_iterator> >("EdgeIterator", no_init)
            .def("__iter__", objects::identity_function())
318
319
            .def("__next__", &PythonIterator<PythonEdge<Graph>,
                                         edge_iterator>::Next)
320
            .def("next", &PythonIterator<PythonEdge<Graph>,
321
322
323
324
                                         edge_iterator>::Next);

        typedef typename graph_traits<Graph>::out_edge_iterator
            out_edge_iterator;
325
        class_<PythonIterator<PythonEdge<Graph>,
326
327
                              out_edge_iterator> >("OutEdgeIterator", no_init)
            .def("__iter__", objects::identity_function())
328
329
            .def("__next__", &PythonIterator<PythonEdge<Graph>,
                                             out_edge_iterator>::Next)
330
            .def("next", &PythonIterator<PythonEdge<Graph>,
331
332
333
334
                                         out_edge_iterator>::Next);

        typedef typename graph_traits<Graph>::directed_category
            directed_category;
Tiago Peixoto's avatar
Tiago Peixoto committed
335
336
        typedef typename std::is_convertible<directed_category,
                                             boost::directed_tag>::type is_directed;
337
338
339
        if (is_directed::value)
        {
            typedef typename in_edge_iteratorS<Graph>::type in_edge_iterator;
340
            class_<PythonIterator<PythonEdge<Graph>,
341
342
                                  in_edge_iterator> >("InEdgeIterator", no_init)
                .def("__iter__", objects::identity_function())
343
344
                .def("__next__", &PythonIterator<PythonEdge<Graph>,
                                                 in_edge_iterator>::Next)
345
                .def("next", &PythonIterator<PythonEdge<Graph>,
346
347
348
349
350
                                             in_edge_iterator>::Next);
        }
    }
};

351
352
353
354
PythonPropertyMap<GraphInterface::vertex_index_map_t>
get_vertex_index(GraphInterface& g)
{
    return PythonPropertyMap<GraphInterface::vertex_index_map_t>
355
        (g.GetVertexIndex());
356
357
358
}

PythonPropertyMap<GraphInterface::edge_index_map_t>
359
do_get_edge_index(GraphInterface& g)
360
361
{
    return PythonPropertyMap<GraphInterface::edge_index_map_t>
362
        (g.GetEdgeIndex());
363
364
}

365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381

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
        {
382
383
            if (found)
                return;
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
            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");
}


418
419
} // namespace graph_tool

420
421
// register everything

422
423
424
void export_python_properties();

void export_python_interface()
425
{
426
427
    using namespace boost::python;

428
    class_<PythonVertex>
Tiago Peixoto's avatar
Tiago Peixoto committed
429
        ("Vertex", no_init)
430
        .def("__in_degree", &PythonVertex::GetInDegree,
431
             "Return the in-degree.")
432
433
434
        .def("__weighted_in_degree", &PythonVertex::GetWeightedOutDegree,
             "Return the weighted in-degree.")
        .def("__out_degree", &PythonVertex::GetOutDegree,
435
             "Return the out-degree.")
436
437
        .def("__weighted_out_degree", &PythonVertex::GetWeightedOutDegree,
             "Return the weighted out-degree.")
438
        .def("in_edges", &PythonVertex::InEdges,
439
             "Return an iterator over the in-edges.")
440
441
        .def("out_edges", &PythonVertex::OutEdges,
             "Return an iterator over the out-edges.")
442
        .def("is_valid", &PythonVertex::IsValid,
443
             "Return whether the vertex is valid.")
444
445
        .def("get_graph", &PythonVertex::GetGraph,
             "Return the graph to which the vertex belongs.")
446
        .def("__str__", &PythonVertex::GetString)
447
        .def("__int__", &PythonVertex::GetIndex)
448
        .def("__hash__", &PythonVertex::GetHash);
449
    class_<EdgeBase>("EdgeBase", no_init);
450
451

    set<string> v_iterators;
Tiago Peixoto's avatar
Tiago Peixoto committed
452
453
454
455
    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)));
456
    export_python_properties();
457
458
459
460
461
462
    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> >);

463
464
465
466
467
468
469
    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);
470
    def("add_edge_list", graph_tool::do_add_edge_list);
471

472
    def("get_vertex_index", get_vertex_index);
473
    def("get_edge_index", do_get_edge_index);
474
}