graph_properties.cc 10.6 KB
Newer Older
Tiago Peixoto's avatar
Tiago Peixoto committed
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>
Tiago Peixoto's avatar
Tiago Peixoto committed
4
5
6
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
Tiago Peixoto's avatar
Tiago Peixoto committed
7
// as published by the Free Software Foundation; either version 3
Tiago Peixoto's avatar
Tiago Peixoto committed
8
9
10
11
12
13
14
15
// 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
16
17
// along with this program. If not, see <http://www.gnu.org/licenses/>.

18
#include "graph_python_interface.hh"
19
#include "graph.hh"
Tiago Peixoto's avatar
Tiago Peixoto committed
20
#include "graph_properties.hh"
21
#include "graph_filtering.hh"
22
#include "graph_selectors.hh"
23
#include "graph_util.hh"
Tiago Peixoto's avatar
Tiago Peixoto committed
24

Tiago Peixoto's avatar
Tiago Peixoto committed
25
#include <unordered_set>
26

27
28
#include <boost/mpl/for_each.hpp>

29
30
#include <boost/python/extract.hpp>

31
32
33
34
using namespace std;
using namespace boost;
using namespace graph_tool;

35
36
namespace graph_tool
{
37

38
// global property types' names
39
const char* type_names[] =
40
41
42
43
    {"bool", "int16_t", "int32_t", "int64_t", "double", "long double",
     "string", "vector<bool>", "vector<int16_t>", "vector<int32_t>",
     "vector<int64_t>", "vector<double>", "vector<long double>",
     "vector<string>", "python::object"};
44
45


46
struct shift_vertex_property
47
{
48
    template <class PropertyMap, class Vec>
49
    void operator()(PropertyMap, const GraphInterface::multigraph_t& g,
50
                    boost::any map, const Vec& vi, bool& found) const
Tiago Peixoto's avatar
Tiago Peixoto committed
51
    {
52
        try
Tiago Peixoto's avatar
Tiago Peixoto committed
53
        {
54
            PropertyMap pmap = any_cast<PropertyMap>(map);
55
56
57
58
59
60
61
            size_t back = num_vertices(g) - 1;
            for (auto v : vi)
            {
                for (size_t i = v; i < back; ++i)
                    pmap[vertex(i, g)] = pmap[vertex(i + 1, g)];
                back--;
            }
62
            found = true;
63
        }
64
        catch (bad_any_cast&) {}
65
    }
66
67
};

68
// this function will shift all the properties when a vertex is to be deleted
69
void GraphInterface::ShiftVertexProperty(boost::any prop, python::object oindex) const
70
{
71
    boost::multi_array_ref<int64_t,1> index = get_array<int64_t,1>(oindex);
72
    bool found = false;
73
    mpl::for_each<writable_vertex_properties>
Tiago Peixoto's avatar
Tiago Peixoto committed
74
75
        (std::bind(shift_vertex_property(), std::placeholders::_1, std::ref(*_mg),
                   prop, index, std::ref(found)));
76
    if (!found)
77
        throw GraphException("invalid writable property map");
78
}
79

80
81
struct move_vertex_property
{
82
    template <class PropertyMap, class Vec>
83
    void operator()(PropertyMap, const GraphInterface::multigraph_t& g,
84
85
                    boost::any map, const Vec& vi, size_t back,
                    bool& found) const
86
87
88
89
    {
        try
        {
            PropertyMap pmap = any_cast<PropertyMap>(map);
90
91
92
93
94
            for (auto v : vi)
            {
                pmap[vertex(v, g)] = pmap[vertex(back, g)];
                back--;
            }
95
96
97
98
99
100
101
            found = true;
        }
        catch (bad_any_cast&) {}
    }
};

// this function will move the back of the property map when a vertex in the middle is to be deleted
102
void GraphInterface::MoveVertexProperty(boost::any prop, python::object oindex) const
103
{
104
    boost::multi_array_ref<int64_t,1> index = get_array<int64_t,1>(oindex);
105
106
107
    size_t back = num_vertices(*_mg) - 1;
    bool found = false;
    mpl::for_each<writable_vertex_properties>
Tiago Peixoto's avatar
Tiago Peixoto committed
108
109
        (std::bind(move_vertex_property(), std::placeholders::_1, std::ref(*_mg),
                   prop, index, back, std::ref(found)));
110
111
112
113
114
    if (!found)
        throw GraphException("invalid writable property map");
}


115
116
117
118
119
120
121
122
123
124
125
126
struct reindex_vertex_property
{
    template <class PropertyMap, class IndexMap>
    void operator()(PropertyMap, const GraphInterface::multigraph_t& g,
                    boost::any map, IndexMap old_index, bool& found) const
    {
        try
        {
            PropertyMap pmap = any_cast<PropertyMap>(map);
            for (size_t i = 0; i < num_vertices(g); ++i)
            {
                GraphInterface::vertex_t v = vertex(i, g);
127
128
                if (old_index[v] != int(i))
                    pmap[v] = pmap[vertex(old_index[v], g)];
129
130
131
132
133
134
135
136
137
138
139
            }
            found = true;
        }
        catch (bad_any_cast&) {}
    }
};


void GraphInterface::ReIndexVertexProperty(boost::any map,
                                           boost::any aold_index) const
{
140
    typedef property_map_type::apply<int64_t,
141
142
143
144
145
146
                                     GraphInterface::vertex_index_map_t>::type
        index_prop_t;
    index_prop_t old_index = any_cast<index_prop_t>(aold_index);

    bool found = false;
    mpl::for_each<writable_vertex_properties>
Tiago Peixoto's avatar
Tiago Peixoto committed
147
148
        (std::bind(reindex_vertex_property(), std::placeholders::_1, std::ref(*_mg),
                   map, old_index, std::ref(found)));
149
150
151
152
    if (!found)
        throw GraphException("invalid writable property map");

}
153

154
} // graph_tool namespace
155
156
157
158
159
160


struct do_infect_vertex_property
{
    template <class Graph, class IndexMap, class PropertyMap>
    void operator()(Graph& g, IndexMap index, PropertyMap prop,
Tiago Peixoto's avatar
Tiago Peixoto committed
161
                    boost::python::object oval) const
162
163
164
165
    {
        typedef typename property_traits<PropertyMap>::value_type val_t;
        bool all = false;

Tiago Peixoto's avatar
Tiago Peixoto committed
166
167
        std::unordered_set<val_t, std::hash<val_t> > vals;
        if (oval == boost::python::object())
168
169
170
171
172
173
174
        {
            all = true;
        }
        else
        {
            for (int i = 0; i < len(oval); ++i)
            {
Tiago Peixoto's avatar
Tiago Peixoto committed
175
                val_t val = boost::python::extract<val_t>(oval[i]);
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
                vals.insert(val);
            }
        }

        unchecked_vector_property_map<uint8_t, IndexMap>
            marked(index, num_vertices(g));

        int i, N = num_vertices(g);
        #pragma omp parallel for default(shared) private(i)
        for (i = 0; i < N; ++i)
        {
            typename graph_traits<Graph>::vertex_descriptor v = vertex(i, g);
            if (v == graph_traits<Graph>::null_vertex())
                continue;
            bool skip;
            {
                #pragma omp critical
                skip = marked[v];
            }
            if (skip)
                continue;
            if (!all && vals.find(prop[v]) == vals.end())
                continue;
            typename graph_traits<Graph>::adjacency_iterator a, a_end;
            for (tie(a, a_end) = adjacent_vertices(v, g); a != a_end; ++a)
            {
                if (prop[*a] == prop[v])
                    continue;
                {
                    #pragma omp critical
                    marked[*a] = true;
                }
                prop[*a] = prop[v];
            }
        }
    }
};

void infect_vertex_property(GraphInterface& gi, boost::any prop,
Tiago Peixoto's avatar
Tiago Peixoto committed
215
                            boost::python::object val)
216
{
Tiago Peixoto's avatar
Tiago Peixoto committed
217
218
        run_action<>()(gi, std::bind(do_infect_vertex_property(), std::placeholders::_1,
                                     gi.GetVertexIndex(), std::placeholders::_2, val),
219
220
                   writable_vertex_properties())(prop);
}
Tiago Peixoto's avatar
Tiago Peixoto committed
221
222
223
224
225
226
227
228
229
230
231

template <class Value>
vector<Value> operator-(const vector<Value>& a, const vector<Value>& b)
{
    vector<Value> c(a);
    c.resize(max(a.size(), b.size()), Value(0));
    for (size_t i = 0; i < b.size(); ++i)
        c[i] = a[i] - b[i];
    return c;
}

232
233
234
235
236
237
238
struct do_mark_edges
{
    template <class Graph, class EdgePropertyMap>
    void operator()(Graph& g, EdgePropertyMap prop) const
    {
        int i, N = num_vertices(g);
        #pragma omp parallel for default(shared) private(i)     \
239
                schedule(runtime) if (N > 100)
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
        for (i = 0; i < N; ++i)
        {
            typename graph_traits<Graph>::vertex_descriptor v = vertex(i, g);
            if (v == graph_traits<Graph>::null_vertex())
                continue;
            typename graph_traits<Graph>::out_edge_iterator e, e_end;
            for (tie(e, e_end) = out_edges(v, g); e != e_end; ++e)
                prop[*e] = true;
        }
    }
};

void mark_edges(GraphInterface& gi, boost::any prop)
{
    run_action<graph_tool::detail::always_directed>()(gi, bind<void>(do_mark_edges(), _1, _2),
                                                      writable_edge_scalar_properties())(prop);
}
Tiago Peixoto's avatar
Tiago Peixoto committed
257
258
259
260
261
262
263
264
265
266


struct do_perfect_vhash
{
    template <class Graph, class VertexPropertyMap, class HashProp>
    void operator()(Graph& g, VertexPropertyMap prop, HashProp hprop,
                    boost::any& adict) const
    {
        typedef typename property_traits<VertexPropertyMap>::value_type val_t;
        typedef typename property_traits<HashProp>::value_type hash_t;
267
        typedef unordered_map<val_t, hash_t> dict_t;
Tiago Peixoto's avatar
Tiago Peixoto committed
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
302
303
304
305

        if (adict.empty())
            adict = dict_t();

        dict_t& dict = any_cast<dict_t&>(adict);

        for (auto v : vertices_range(g))
        {
            auto val = prop[v];
            auto iter = dict.find(val);
            hash_t h;
            if (iter == dict.end())
                h = dict[val] = dict.size() - 1;
            else
                h = iter->second;
            hprop[v] = h;
        }
    }
};

void perfect_vhash(GraphInterface& gi, boost::any prop, boost::any hprop,
                   boost::any& dict)
{
    run_action<graph_tool::detail::always_directed>()
        (gi, std::bind<void>(do_perfect_vhash(), std::placeholders::_1,
         std::placeholders::_2, std::placeholders::_3, std::ref(dict)),
         vertex_properties(), writable_vertex_scalar_properties())
        (prop, hprop);
}

struct do_perfect_ehash
{
    template <class Graph, class EdgePropertyMap, class HashProp>
    void operator()(Graph& g, EdgePropertyMap prop, HashProp hprop,
                    boost::any& adict) const
    {
        typedef typename property_traits<EdgePropertyMap>::value_type val_t;
        typedef typename property_traits<HashProp>::value_type hash_t;
306
        typedef unordered_map<val_t, hash_t> dict_t;
Tiago Peixoto's avatar
Tiago Peixoto committed
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335

        if (adict.empty())
            adict = dict_t();

        dict_t& dict = any_cast<dict_t&>(adict);

        for (auto e : edges_range(g))
        {
            auto val = prop[e];
            auto iter = dict.find(val);
            hash_t h;
            if (iter == dict.end())
                h = dict[val] = dict.size() - 1;
            else
                h = iter->second;
            hprop[e] = h;
        }
    }
};

void perfect_ehash(GraphInterface& gi, boost::any prop, boost::any hprop,
                   boost::any& dict)
{
    run_action<graph_tool::detail::always_directed>()
        (gi, std::bind<void>(do_perfect_ehash(), std::placeholders::_1,
         std::placeholders::_2, std::placeholders::_3, std::ref(dict)),
         edge_properties(), writable_edge_scalar_properties())
        (prop, hprop);
}