graph_python_interface.cc 14.7 KB
Newer Older
1
2
// graph-tool -- a general graph modification and manipulation thingy
//
Tiago Peixoto's avatar
Tiago Peixoto committed
3
// Copyright (C) 2007-2011 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
31
namespace graph_tool
{

32
33
34
struct get_vertex_iterator
{
    template <class Graph>
35
    void operator()(Graph& g, python::object& pg,
36
37
38
                    python::object& iter) const
    {
        typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
39
        iter = python::object(PythonIterator<PythonVertex,
40
                                             vertex_iterator>(pg, vertices(g)));
41
42
43
    }
};

44
python::object get_vertices(python::object g)
45
{
46
    GraphInterface& gi = python::extract<GraphInterface&>(g().attr("_Graph__graph"));
47
    python::object iter;
48
49
50
    run_action<>()(gi, bind<void>(get_vertex_iterator(), _1,
                                  ref(g),
                                  ref(iter)))();
51
52
53
    return iter;
}

54
55
56
struct get_vertex_soft
{
    template <class Graph>
57
    void operator()(Graph& g,
58
                    python::object& pg,
59
60
                    size_t i, python::object& v) const
    {
61
        v = python::object(PythonVertex(pg, vertex(i, g)));
62
63
64
65
66
67
    }
};

struct get_vertex_hard
{
    template <class Graph>
68
    void operator()(Graph& g, python::object& pg, size_t i,
69
70
71
72
73
74
75
                    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)
76
            {
77
                v = python::object(PythonVertex(pg, *vi));
78
79
                return;
            }
80
81
            ++c;
        }
82
        v = python::object(PythonVertex(pg,
83
                                        graph_traits<Graph>::null_vertex()));
84
85
86
    }
};

87
python::object get_vertex(python::object g, size_t i)
88
{
89
    GraphInterface& gi = python::extract<GraphInterface&>(g().attr("_Graph__graph"));
90
    python::object v;
91
92
93
    if (gi.IsVertexFilterActive())
        run_action<>()(gi,
                       bind<void>(get_vertex_hard(), _1, ref(g), i, ref(v)))();
94
    else
95
96
        run_action<>()(gi,
                       bind<void>(get_vertex_soft(), _1, ref(g), i, ref(v)))();
97
98
99
    return v;
}

100
101
102
struct get_edge_iterator
{
    template <class Graph>
103
104
    void operator()(Graph& g, const python::object& pg, python::object& iter)
        const
105
106
    {
        typedef typename graph_traits<Graph>::edge_iterator edge_iterator;
107
        iter = python::object(PythonIterator<PythonEdge<Graph>,
108
                                             edge_iterator>(pg, edges(g)));
109
110
111
    }
};

112
python::object get_edges(python::object g)
113
{
114
    GraphInterface& gi = python::extract<GraphInterface&>(g().attr("_Graph__graph"));
115
    python::object iter;
116
117
    run_action<>()(gi,
                   bind<void>(get_edge_iterator(), _1, ref(g), ref(iter)))();
118
119
120
    return iter;
}

121
python::object add_vertex(python::object g)
122
{
123
    GraphInterface& gi = python::extract<GraphInterface&>(g().attr("_Graph__graph"));
124
    return python::object(PythonVertex(g, add_vertex(gi.GetGraph())));
125
126
}

127
struct shift_vertex_property
128
{
129
    template <class Graph, class PropertyMap>
130
    void operator()(const Graph& g, size_t vi, PropertyMap pmap)
131
132
        const
    {
133
        size_t N = num_vertices(g);
134
135
        if (N <= 1 || vi >= N - 1)
            return;
136
137
138
139
        for (size_t i = vi; i < N-1; ++i)
        {
            pmap[vertex(i, g)] = pmap[vertex(i+1, g)];
        }
140
141
142
    }
};

143
void remove_vertex(GraphInterface& gi, const python::object& v)
144
{
145
    PythonVertex& pv = python::extract<PythonVertex&>(v);
146
    pv.CheckValid();
147
    GraphInterface::vertex_t dv = pv.GetDescriptor();
148
149
    pv.SetValid(false);

150
    //remove vertex
151
152
    clear_vertex(dv, gi.GetGraph());
    remove_vertex(dv, gi.GetGraph());
153
154
155
156
}

struct add_new_edge
{
157
    template <class Graph, class EdgeIndexMap>
158
159
160
    void operator()(Graph& g, python::object& pg, GraphInterface& gi,
                    const PythonVertex& s, const PythonVertex& t,
                    EdgeIndexMap edge_index, python::object& new_e) const
161
    {
162
        typename graph_traits<Graph>::edge_descriptor e =
163
            add_edge(s.GetDescriptor(), t.GetDescriptor(), g).first;
164
        new_e = python::object(PythonEdge<Graph>(pg, e));
Tiago Peixoto's avatar
Tiago Peixoto committed
165
        gi.AddEdgeIndex(e);
166
167
168
    }
};

Tiago Peixoto's avatar
Tiago Peixoto committed
169
170
void GraphInterface::AddEdgeIndex(const edge_t& e)
{
Tiago Peixoto's avatar
Tiago Peixoto committed
171
    if (!_state->_free_indexes.empty())
Tiago Peixoto's avatar
Tiago Peixoto committed
172
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
173
174
        _edge_index[e] = _state->_free_indexes.front();
        _state->_free_indexes.pop_front();
Tiago Peixoto's avatar
Tiago Peixoto committed
175
176
177
    }
    else
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
178
179
        _edge_index[e] = _state->_nedges;
        _state->_max_edge_index = _state->_nedges;
Tiago Peixoto's avatar
Tiago Peixoto committed
180
    }
Tiago Peixoto's avatar
Tiago Peixoto committed
181
    _state->_nedges++;
Tiago Peixoto's avatar
Tiago Peixoto committed
182
183
}

184
185
python::object add_edge(python::object g, const python::object& s,
                        const python::object& t)
186
{
187
188
    PythonVertex& src = python::extract<PythonVertex&>(s);
    PythonVertex& tgt = python::extract<PythonVertex&>(t);
189
190
    src.CheckValid();
    tgt.CheckValid();
191
    GraphInterface& gi = python::extract<GraphInterface&>(g().attr("_Graph__graph"));
192
    python::object new_e;
193
194
    run_action<>()(gi, bind<void>(add_new_edge(), _1, ref(g), ref(gi), src, tgt,
                                  gi.GetEdgeIndex(), ref(new_e)))();
195
196
197
198
199
200
    return new_e;
}

struct get_edge_descriptor
{
    template <class Graph>
201
    void operator()(const Graph& g, const python::object& e,
202
                    typename GraphInterface::edge_t& edge,
203
                    bool& found)  const
204
    {
205
        typedef typename graph_traits<Graph>::edge_descriptor edge_t;
206
207
208
        PythonEdge<Graph>& pe = python::extract<PythonEdge<Graph>&>(e);
        pe.CheckValid();
        pe.SetValid(false);
209
        typename graph_traits<Graph>::out_edge_iterator e_begin, e_end;
210
        tie(e_begin, e_end) = out_edges(source(edge_t(pe.GetDescriptor()),g),g);
211
212
        while(e_begin != e_end && *e_begin != pe.GetDescriptor())
            ++e_begin;
213
214
215
        if (e_begin == e_end)
            return; // invalid edge descriptor
        edge = pe.GetDescriptor();
216
        found = true;
217
218
219
    }
};

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

void GraphInterface::RemoveEdgeIndex(const edge_t& e)
{
    size_t index = _edge_index[e];
Tiago Peixoto's avatar
Tiago Peixoto committed
234
    if (index == _state->_max_edge_index)
Tiago Peixoto's avatar
Tiago Peixoto committed
235
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
236
237
        if (_state->_max_edge_index > 0)
            _state->_max_edge_index--;
238

Tiago Peixoto's avatar
Tiago Peixoto committed
239
240
        while (!_state->_free_indexes.empty() &&
               _state->_max_edge_index == _state->_free_indexes.back())
Tiago Peixoto's avatar
Tiago Peixoto committed
241
        {
Tiago Peixoto's avatar
Tiago Peixoto committed
242
243
244
            _state->_free_indexes.pop_back();
            if (_state->_max_edge_index > 0)
                _state->_max_edge_index--;
Tiago Peixoto's avatar
Tiago Peixoto committed
245
246
        }
    }
247
    else
Tiago Peixoto's avatar
Tiago Peixoto committed
248
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
249
250
251
252
        typeof(_state->_free_indexes.begin()) pos =
                lower_bound(_state->_free_indexes.begin(),
                            _state->_free_indexes.end(), index);
        _state->_free_indexes.insert(pos, index);
Tiago Peixoto's avatar
Tiago Peixoto committed
253
    }
Tiago Peixoto's avatar
Tiago Peixoto committed
254
255
    _state->_nedges--;
    remove_edge(e, _state->_mg);
256
257
}

258
259
260
struct get_degree_map
{
    template <class Graph, class DegreeMap, class DegS>
261
    void operator()(const Graph& g, DegreeMap deg_map, DegS deg) const
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
    {
        int i, N = num_vertices(g);
        #pragma omp parallel for default(shared) private(i) schedule(dynamic)
        for (i = 0; i < N; ++i)
        {
            typename graph_traits<Graph>::vertex_descriptor v = vertex(i, g);
            if (v == graph_traits<Graph>::null_vertex())
                continue;
            deg_map[v] = deg(v, g);
        }
    }
};

python::object GraphInterface::DegreeMap(string deg) const
{
    typedef property_map_type::apply<double,
                                     GraphInterface::vertex_index_map_t>::type
        map_t;

    map_t deg_map(_vertex_index);
Tiago Peixoto's avatar
Tiago Peixoto committed
282
    deg_map.reserve(num_vertices(_state->_mg));
283
284

    if (deg == "in")
285
        run_action<>()(const_cast<GraphInterface&>(*this),
286
287
                       bind<void>(get_degree_map(), _1,
                                  deg_map, in_degreeS()))();
288
    else if (deg == "out")
289
        run_action<>()(const_cast<GraphInterface&>(*this),
290
291
                       bind<void>(get_degree_map(), _1,
                                  deg_map, out_degreeS()))();
292
    else if (deg == "total")
293
        run_action<>()(const_cast<GraphInterface&>(*this),
294
295
                       bind<void>(get_degree_map(), _1,
                                  deg_map, total_degreeS()))();
296
297
298
    return python::object(PythonPropertyMap<map_t>(deg_map));
}

299
300
301
302
303
//
// Below are the functions with will properly register all the types to python,
// for every filter, type, etc.
//

304
305
306
307
// this will register all the Vertex/Edge classes to python
struct export_python_interface
{
    template <class Graph>
308
    void operator()(const Graph*, set<string>& v_iterators) const
309
310
    {
        using namespace boost::python;
311
        class_<PythonEdge<Graph>, bases<EdgeBase> >
Tiago Peixoto's avatar
Tiago Peixoto committed
312
            ("Edge", no_init)
313
            .def("source", &PythonEdge<Graph>::GetSource,
314
                 "Return the source vertex.")
315
            .def("target", &PythonEdge<Graph>::GetTarget,
316
                 "Return the target vertex.")
317
            .def("is_valid", &PythonEdge<Graph>::IsValid,
318
                 "Return whether the edge is valid.")
319
320
            .def("get_graph", &PythonEdge<Graph>::GetGraph,
                 "Return the graph to which the edge belongs.")
321
322
            .def(python::self == python::self)
            .def(python::self != python::self)
323
            .def("__str__", &PythonEdge<Graph>::GetString)
324
325
326
            .def("__hash__", &PythonEdge<Graph>::GetHash);

        typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
327
        if (v_iterators.find(typeid(vertex_iterator).name()) ==
328
329
            v_iterators.end())
        {
330
331
            class_<PythonIterator<PythonVertex, vertex_iterator> >
                ("VertexIterator", no_init)
332
333
334
335
336
337
                .def("__iter__", objects::identity_function())
                .def("next", &PythonIterator<PythonVertex,
                                             vertex_iterator>::Next);
            v_iterators.insert(typeid(vertex_iterator).name());
        }

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

        typedef typename graph_traits<Graph>::out_edge_iterator
            out_edge_iterator;
347
        class_<PythonIterator<PythonEdge<Graph>,
348
349
                              out_edge_iterator> >("OutEdgeIterator", no_init)
            .def("__iter__", objects::identity_function())
350
            .def("next", &PythonIterator<PythonEdge<Graph>,
351
352
353
354
355
356
357
358
359
                                         out_edge_iterator>::Next);

        typedef typename graph_traits<Graph>::directed_category
            directed_category;
        typedef typename is_convertible<directed_category,
                                        boost::directed_tag>::type is_directed;
        if (is_directed::value)
        {
            typedef typename in_edge_iteratorS<Graph>::type in_edge_iterator;
360
            class_<PythonIterator<PythonEdge<Graph>,
361
362
                                  in_edge_iterator> >("InEdgeIterator", no_init)
                .def("__iter__", objects::identity_function())
363
                .def("next", &PythonIterator<PythonEdge<Graph>,
364
365
366
367
368
                                             in_edge_iterator>::Next);
        }
    }
};

369
370
371
372
PythonPropertyMap<GraphInterface::vertex_index_map_t>
get_vertex_index(GraphInterface& g)
{
    return PythonPropertyMap<GraphInterface::vertex_index_map_t>
373
        (g.GetVertexIndex());
374
375
376
377
378
379
}

PythonPropertyMap<GraphInterface::edge_index_map_t>
get_edge_index(GraphInterface& g)
{
    return PythonPropertyMap<GraphInterface::edge_index_map_t>
380
        (g.GetEdgeIndex());
381
382
}

383
384
} // namespace graph_tool

385
386
// register everything

387
388
389
void export_python_properties();

void export_python_interface()
390
{
391
392
    using namespace boost::python;

393
    class_<PythonVertex>
Tiago Peixoto's avatar
Tiago Peixoto committed
394
        ("Vertex", no_init)
395
        .def("in_degree", &PythonVertex::GetInDegree,
396
             "Return the in-degree.")
397
        .def("out_degree", &PythonVertex::GetOutDegree,
398
             "Return the out-degree.")
399
        .def("out_edges", &PythonVertex::OutEdges,
400
             "Return an iterator over the out-edges.")
401
        .def("in_edges", &PythonVertex::InEdges,
402
             "Return an iterator over the in-edges.")
403
        .def("is_valid", &PythonVertex::IsValid,
404
             "Return whether the vertex is valid.")
405
406
        .def("get_graph", &PythonVertex::GetGraph,
             "Return the graph to which the vertex belongs.")
407
408
409
        .def(python::self == python::self)
        .def(python::self != python::self)
        .def("__str__", &PythonVertex::GetString)
410
        .def("__int__", &PythonVertex::GetIndex)
411
        .def("__hash__", &PythonVertex::GetHash);
412
    class_<EdgeBase>("EdgeBase", no_init);
413
414
415
416

    set<string> v_iterators;
    typedef mpl::transform<graph_tool::detail::all_graph_views,
                           mpl::quote1<add_pointer> >::type graph_views;
417
    mpl::for_each<graph_views>(bind<void>(graph_tool::export_python_interface(),
418
                                          _1,ref(v_iterators)));
419
    export_python_properties();
420
421
422
423
424
425
    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> >);

426
427
428
429
430
431
432
433
    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);

434
435
    def("get_vertex_index", get_vertex_index);
    def("get_edge_index", get_edge_index);
436
}