graph_python_interface.cc 13.6 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// graph-tool -- a general graph modification and manipulation thingy
//
// Copyright (C) 2007  Tiago de Paula Peixoto <tiago@forked.de>
//
// 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
23
#include <boost/python.hpp>
#include <boost/lambda/bind.hpp>
24
#include <set>
25
26
27
28
29
30
31
32

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

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

python::object
GraphInterface::Vertices() const
{
    python::object iter;
47
48
49
    run_action<>()(*this, lambda::bind<void>(get_vertex_iterator(), lambda::_1,
                                             lambda::var(*this),
                                             lambda::var(iter)))();
50
51
52
    return iter;
}

53
54
55
struct get_vertex_soft
{
    template <class Graph>
56
    void operator()(const Graph* gp,
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
                    const GraphInterface& gi,
                    size_t i, python::object& v) const
    {
        const Graph& g = *gp;
        v = python::object(PythonVertex(gi, vertex(i, g)));
    }
};

struct get_vertex_hard
{
    template <class Graph>
    void operator()(const Graph* gp, const GraphInterface& gi, size_t i,
                    python::object& v) const
    {
        const Graph& g = *gp;
        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)
77
            {
78
                v = python::object(PythonVertex(gi, *vi));
79
80
                return;
            }
81
82
            ++c;
        }
83
84
        v = python::object(PythonVertex(gi,
                                        graph_traits<Graph>::null_vertex()));
85
86
87
88
89
90
91
92
    }
};

python::object
GraphInterface::Vertex(size_t i) const
{
    python::object v;
    if (IsVertexFilterActive())
93
        run_action<>()(*this, lambda::bind<void>(get_vertex_hard(), lambda::_1,
94
95
96
                                                 lambda::var(*this),
                                                 i, lambda::var(v)))();
    else
97
98
99
        run_action<>()(*this, lambda::bind<void>(get_vertex_soft(), lambda::_1,
                                                 lambda::var(*this), i,
                                                 lambda::var(v)))();
100
101
102
    return v;
}

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

python::object
GraphInterface::Edges() const
{
    python::object iter;
120
121
122
    run_action<>()(*this, lambda::bind<void>(get_edge_iterator(), lambda::_1,
                                             lambda::var(*this),
                                             lambda::var(iter)))();
123
124
125
    return iter;
}

126
127
python::object GraphInterface::AddVertex()
{
128
    return python::object(PythonVertex(*this, add_vertex(_mg)));
129
130
}

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

148
void GraphInterface::RemoveVertex(const python::object& v)
149
{
150
    PythonVertex& pv = python::extract<PythonVertex&>(v);
151
    pv.CheckValid();
152
    vertex_t dv = pv.GetDescriptor();
153
154
    pv.SetValid(false);

155
    //remove vertex
156
    clear_vertex(dv, _mg);
157
158
159
160
161
    remove_vertex(dv, _mg);
}

struct add_new_edge
{
162
    template <class Graph, class EdgeIndexMap>
Tiago Peixoto's avatar
Tiago Peixoto committed
163
    void operator()(Graph* gp, GraphInterface& gi, const PythonVertex& s,
164
                    const PythonVertex& t, EdgeIndexMap edge_index,
Tiago Peixoto's avatar
Tiago Peixoto committed
165
                    python::object& new_e) const
166
    {
167
        Graph& g = *gp;
168
        typename graph_traits<Graph>::edge_descriptor e =
169
170
            add_edge(s.GetDescriptor(), t.GetDescriptor(), g).first;
        new_e = python::object(PythonEdge<Graph>(gi, e));
Tiago Peixoto's avatar
Tiago Peixoto committed
171
        gi.AddEdgeIndex(e);
172
173
174
    }
};

Tiago Peixoto's avatar
Tiago Peixoto committed
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
void GraphInterface::AddEdgeIndex(const edge_t& e)
{
    if (!_free_indexes.empty())
    {
        _edge_index[e] = _free_indexes.front();
        _free_indexes.pop_front();
    }
    else
    {
        _edge_index[e] = _nedges;
        _max_edge_index = _nedges;
    }
    _nedges++;
}

190
191
python::object GraphInterface::AddEdge(const python::object& s,
                                       const python::object& t)
192
{
193
194
    PythonVertex& src = python::extract<PythonVertex&>(s);
    PythonVertex& tgt = python::extract<PythonVertex&>(t);
195
196
    src.CheckValid();
    tgt.CheckValid();
197
    python::object new_e;
198
199
    run_action<>()(*this, lambda::bind<void>(add_new_edge(), lambda::_1,
                                             lambda::var(*this), src, tgt,
Tiago Peixoto's avatar
Tiago Peixoto committed
200
                                             _edge_index,
201
                                             lambda::var(new_e)))();
202
203
204
205
206
207
    return new_e;
}

struct get_edge_descriptor
{
    template <class Graph>
208
209
210
    void operator()(const Graph* gp, const python::object& e,
                    typename GraphInterface::edge_t& edge,
                    bool& found)
211
212
        const
    {
213
214
215
216
217
        PythonEdge<Graph>& pe = python::extract<PythonEdge<Graph>&>(e);
        pe.CheckValid();
        edge = pe.GetDescriptor();
        pe.SetValid(false);
        found = true;
218
219
220
    }
};

221
void GraphInterface::RemoveEdge(const python::object& e)
222
{
223
224
225
    edge_t de;
    bool found = false;
    run_action<>()(*this,
226
                   lambda::bind<void>(get_edge_descriptor(), lambda::_1,
227
228
229
230
                                      lambda::var(e), lambda::var(de),
                                      lambda::var(found)))();
    if (!found)
        throw GraphException("invalid edge descriptor");
Tiago Peixoto's avatar
Tiago Peixoto committed
231
232
233
234
235
236
237
238
    RemoveEdgeIndex(de);
}

void GraphInterface::RemoveEdgeIndex(const edge_t& e)
{
    size_t index = _edge_index[e];
    if (index == _max_edge_index)
    {
239
240
241
242
243
        if (_max_edge_index > 0)
            _max_edge_index--;

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

260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
struct get_degree_map
{
    template <class Graph, class DegreeMap, class DegS>
    void operator()(const Graph* gp, DegreeMap deg_map, DegS deg) const
    {
        const Graph& g = *gp;
        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);
    deg_map.reserve(num_vertices(_mg));

    if (deg == "in")
        run_action<>()(*this,
                       lambda::bind<void>(get_degree_map(), lambda::_1,
                                          deg_map, in_degreeS()))();
    else if (deg == "out")
        run_action<>()(*this,
                       lambda::bind<void>(get_degree_map(), lambda::_1,
                                          deg_map, out_degreeS()))();
    else if (deg == "total")
        run_action<>()(*this,
                       lambda::bind<void>(get_degree_map(), lambda::_1,
                                          deg_map, total_degreeS()))();
    return python::object(PythonPropertyMap<map_t>(deg_map));
}

302
303
304
305
306
//
// Below are the functions with will properly register all the types to python,
// for every filter, type, etc.
//

307
308
309
310
// this will register all the Vertex/Edge classes to python
struct export_python_interface
{
    template <class Graph>
311
    void operator()(const Graph*, set<string>& v_iterators) const
312
313
314
    {
        using namespace boost::python;

315
        class_<PythonEdge<Graph> > ("Edge",  no_init)
316
317
            .def("source", &PythonEdge<Graph>::GetSource)
            .def("target", &PythonEdge<Graph>::GetTarget)
318
            .def("is_valid", &PythonEdge<Graph>::IsValid)
319
320
            .def(python::self == python::self)
            .def(python::self != python::self)
321
            .def("__str__", &PythonEdge<Graph>::GetString)
322
323
324
            .def("__hash__", &PythonEdge<Graph>::GetHash);

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

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

        typedef typename graph_traits<Graph>::out_edge_iterator
            out_edge_iterator;
345
        class_<PythonIterator<PythonEdge<Graph>,
346
347
                              out_edge_iterator> >("OutEdgeIterator", no_init)
            .def("__iter__", objects::identity_function())
348
            .def("next", &PythonIterator<PythonEdge<Graph>,
349
350
351
352
353
354
355
356
357
                                         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;
358
            class_<PythonIterator<PythonEdge<Graph>,
359
360
                                  in_edge_iterator> >("InEdgeIterator", no_init)
                .def("__iter__", objects::identity_function())
361
                .def("next", &PythonIterator<PythonEdge<Graph>,
362
363
364
365
366
                                             in_edge_iterator>::Next);
        }
    }
};

367
void export_python_properties(const GraphInterface&);
368

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
// register everything

385
386
void GraphInterface::ExportPythonInterface() const
{
387
388
389
    using namespace boost::python;

    class_<PythonVertex>("Vertex", no_init)
390
391
392
393
        .def("in_degree", &PythonVertex::GetInDegree)
        .def("out_degree", &PythonVertex::GetOutDegree)
        .def("out_edges", &PythonVertex::OutEdges)
        .def("in_edges", &PythonVertex::InEdges)
394
        .def("is_valid", &PythonVertex::IsValid)
395
396
397
398
399
400
401
402
403
404
405
        .def(python::self == python::self)
        .def(python::self != python::self)
        .def("__str__", &PythonVertex::GetString)
        .def("__hash__", &PythonVertex::GetHash);

    set<string> v_iterators;
    typedef mpl::transform<graph_tool::detail::all_graph_views,
                           mpl::quote1<add_pointer> >::type graph_views;
    mpl::for_each<graph_views>(lambda::bind<void>(export_python_interface(),
                                                  lambda::_1,
                                                  lambda::var(v_iterators)));
406
    export_python_properties(*this);
407
408
409
410
411
412
413
414
    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> >);

    def("get_vertex_index", get_vertex_index);
    def("get_edge_index", get_edge_index);
415
}