graph_copy.cc 8.45 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 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/>.

#include <boost/lambda/lambda.hpp>
#include <boost/lambda/bind.hpp>
20
21
#include <boost/mpl/contains.hpp>
#include <boost/python/extract.hpp>
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include "graph.hh"
#include "graph_filtering.hh"
#include "graph_properties.hh"

using namespace std;
using namespace boost;
using namespace boost::lambda;
using namespace graph_tool;

struct graph_copy
{
    template <class GraphDst, class GraphSrc, class DstVertexIndexMap,
              class SrcVertexIndexMap,  class DstEdgeIndexMap,
              class SrcEdgeIndexMap>
37
    void operator()(GraphDst& dst, GraphSrc& src,
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
                    DstVertexIndexMap dst_vertex_index,
                    SrcVertexIndexMap src_vertex_index,
                    DstEdgeIndexMap dst_edge_index,
                    SrcEdgeIndexMap src_edge_index) const
    {
        vector<size_t> index_map(num_vertices(src));
        typename graph_traits<GraphSrc>::vertex_iterator v, v_end;
        for (tie(v, v_end) = vertices(src); v != v_end; ++v)
        {
            if (src_vertex_index[*v] >= index_map.size())
                index_map.resize(src_vertex_index[*v]+1);
            typename graph_traits<GraphDst>::vertex_descriptor new_v =
                add_vertex(dst);
            index_map[src_vertex_index[*v]] = dst_vertex_index[new_v];
        }

        typename graph_traits<GraphSrc>::edge_iterator e, e_end;
        for (tie(e, e_end) = edges(src); e != e_end; ++e)
        {
Tiago Peixoto's avatar
Tiago Peixoto committed
57
58
            size_t s = index_map[src_vertex_index[source(*e, src)]];
            size_t t = index_map[src_vertex_index[target(*e, src)]];
59
60
            typename graph_traits<GraphDst>::edge_descriptor new_e =
                add_edge(vertex(s,dst), vertex(t,dst), dst).first;
Tiago Peixoto's avatar
Tiago Peixoto committed
61
            dst_edge_index[new_e] = src_edge_index[*e];
62
63
64
65
66
67
68
        }
    }
};

// copy constructor
GraphInterface::GraphInterface(const GraphInterface& gi)
    :_mg(),
69
     _reversed(gi._reversed),
70
71
72
     _directed(gi._directed),
     _vertex_index(get(vertex_index,_mg)),
     _edge_index(get(edge_index_t(),_mg)),
Tiago Peixoto's avatar
Tiago Peixoto committed
73
74
75
     _max_edge_index(gi._max_edge_index),
     _nedges(gi._nedges),
     _free_indexes(gi._free_indexes),
76
77
78
79
80
81
82
     _vertex_filter_map(_vertex_index),
     _vertex_filter_invert(false),
     _vertex_filter_active(false),
     _edge_filter_map(_edge_index),
     _edge_filter_invert(false),
     _edge_filter_active(false)
{
83

84
    graph_copy()(_mg, gi._mg, _vertex_index,
85
86
87
                 gi._vertex_index, _edge_index,
                 gi._edge_index);
    // filters will be copied in python
88
}
89

90
91
92
//
// Property map copying
// ====================
93

94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
// handle type convertions

// generic types
template <class Type1, class Type2>
struct convert
{

    Type1 operator()(const Type2& v) const
    {
        return do_convert(v, is_convertible<Type2,Type1>());
    }

    Type1 do_convert(const Type2& v, mpl::bool_<true>) const
    {
        return Type1(v);
    }
110

111
    Type1 do_convert(const Type2& v, mpl::bool_<false>) const
112
    {
113
114
115
116
117
118
119
        return specific_convert<Type1,Type2>()(v);
    }

    template <class T1, class T2>
    struct specific_convert
    {
        T1 operator()(const T2& v) const
120
        {
121
            throw bad_lexical_cast(); // default action
122
        }
123
124
125
126
127
128
129
130
131
    };

    // specific specializations

    // python::object
    template <class T1>
    struct specific_convert<T1,python::object>
    {
        T1 operator()(const python::object& v) const
132
        {
133
134
135
136
137
            python::extract<Type1> x(v);
            if (x.check())
                return x();
            else
                throw bad_lexical_cast();
138
        }
139
140
141
142
143
144
145
146
    };

    // string
    template <class T1>
    struct specific_convert<T1,string>
    {
        T1 operator()(const string& v) const
        {
147
148
149
150
151
            //uint8_t is not char, it is bool!
            if (is_same<T1, uint8_t>::value)
                return convert<T1,int>()(lexical_cast<int>(v));
            else
                return lexical_cast<Type1>(v);
152
153
154
155
156
157
158
159
        }
    };

    template <class T2>
    struct specific_convert<string,T2>
    {
        string operator()(const T2& v) const
        {
160
161
162
163
164
            //uint8_t is not char, it is bool!
            if (is_same<T2, uint8_t>::value)
                return lexical_cast<string>(convert<int,T2>()(v));
            else
                return lexical_cast<string>(v);
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
        }
    };

    // vectors
    template <class T1, class T2>
    struct specific_convert<vector<T1>, vector<T2> >
    {
        vector<T1> operator()(const vector<T2>& v) const
        {
            vector<T1> v2(v.size());
            convert<T1,T2> c;
            for (size_t i = 0; i < v.size(); ++i)
                v2[i] = c(v[i]);
            return v2;
        }
    };

};

// python::object to string, to solve ambiguity
template<> template<>
struct convert<string,python::object>::specific_convert<string,python::object>
{
    string operator()(const python::object& v) const
    {
        python::extract<string> x(v);
        if (x.check())
                return x();
193
        else
194
195
196
197
198
199
200
201
202
203
            throw bad_lexical_cast();
    }
};


template <class IteratorSel>
struct copy_property
{
    template <class Graph, class PropertySrc,
              class PropertyTgt>
204
    void operator()(const Graph& tgt, const Graph& src, PropertySrc src_map,
205
206
207
208
209
210
                    PropertyTgt dst_map) const
    {
        typedef typename property_traits<PropertySrc>::value_type val_src;
        typedef typename property_traits<PropertyTgt>::value_type val_tgt;

        try
211
        {
212
213
214
215
216
217
218
            convert<val_tgt,val_src> c;
            typename IteratorSel::template apply<Graph>::type vs, vs_end;
            typename IteratorSel::template apply<Graph>::type vt, vt_end;
            tie(vt, vt_end) = IteratorSel::range(tgt);
            for (tie(vs, vs_end) = IteratorSel::range(src); vs != vs_end; ++vs)
            {
                if (vt == vt_end)
Tiago Peixoto's avatar
Tiago Peixoto committed
219
                    throw ValueException("Error copying properties: "
220
221
222
223
                                         "graphs not identical");
                dst_map[*vt] = c(src_map[*vs]);
                ++vt;
            }
224
        }
225
226
        catch (bad_lexical_cast&)
        {
Tiago Peixoto's avatar
Tiago Peixoto committed
227
            throw ValueException("property values are not convertible");
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
        }
    }
};

struct edge_selector
{
    template <class Graph>
    struct apply
    {
        typedef typename graph_traits<Graph>::edge_iterator type;
    };

    template <class Graph>
    static pair<typename apply<Graph>::type,
                typename apply<Graph>::type>
    range(Graph& g)
    {
        return edges(g);
    }
};

struct vertex_selector
{
    template <class Graph>
    struct apply
    {
        typedef typename graph_traits<Graph>::vertex_iterator type;
    };

    template <class Graph>
    static pair<typename apply<Graph>::type,
                typename apply<Graph>::type>
    range(Graph& g)
    {
        return vertices(g);
263
    }
264
265
};

266
267
typedef mpl::vector<GraphInterface::multigraph_t> unfiltered;

268
269
270
271
272
273
void GraphInterface::CopyVertexProperty(const GraphInterface& src,
                                        boost::any prop_src,
                                        boost::any prop_tgt)
{
    typedef edge_properties writable_edge_properties;

274
    run_action<unfiltered>()
275
        (*this, bind<void>(copy_property<vertex_selector>(),
276
                           _1, ref(src._mg),  _2, _3),
277
278
279
280
281
282
283
284
285
286
         vertex_properties(), writable_vertex_properties())
        (prop_src, prop_tgt);
}

void GraphInterface::CopyEdgeProperty(const GraphInterface& src,
                                      boost::any prop_src,
                                      boost::any prop_tgt)
{
    typedef edge_properties writable_edge_properties;

287
    run_action<unfiltered>()
288
        (*this, bind<void>(copy_property<edge_selector>(),
289
                           _1, ref(src._mg), _2, _3),
290
291
         edge_properties(), writable_edge_properties())
        (prop_src, prop_tgt);
292
}