graph_properties.cc 10.2 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
49
50
    template <class PropertyMap>
    void operator()(PropertyMap, const GraphInterface::multigraph_t& g,
                    boost::any map, size_t vi, bool& found) const
Tiago Peixoto's avatar
Tiago Peixoto committed
51
    {
52
        try
Tiago Peixoto's avatar
Tiago Peixoto committed
53
        {
54
55
56
            PropertyMap pmap = any_cast<PropertyMap>(map);
            for (size_t i = vi; i < num_vertices(g)-1; ++i)
                pmap[vertex(i,g)] = pmap[vertex(i+1,g)];
57
            found = true;
58
        }
59
        catch (bad_any_cast&) {}
60
    }
61
62
};

63
64
// this function will shift all the properties when a vertex is to be deleted
void GraphInterface::ShiftVertexProperty(boost::any prop, size_t index) const
65
{
66
    bool found = false;
67
    mpl::for_each<writable_vertex_properties>
Tiago Peixoto's avatar
Tiago Peixoto committed
68
69
        (std::bind(shift_vertex_property(), std::placeholders::_1, std::ref(*_mg),
                   prop, index, std::ref(found)));
70
    if (!found)
71
        throw GraphException("invalid writable property map");
72
}
73

74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
struct move_vertex_property
{
    template <class PropertyMap>
    void operator()(PropertyMap, const GraphInterface::multigraph_t& g,
                    boost::any map, size_t vi, size_t back, bool& found) const
    {
        try
        {
            PropertyMap pmap = any_cast<PropertyMap>(map);
            pmap[vertex(vi,g)] = pmap[vertex(back,g)];
            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
void GraphInterface::MoveVertexProperty(boost::any prop, size_t index) const
{
    size_t back = num_vertices(*_mg) - 1;
    bool found = false;
    mpl::for_each<writable_vertex_properties>
Tiago Peixoto's avatar
Tiago Peixoto committed
96
97
        (std::bind(move_vertex_property(), std::placeholders::_1, std::ref(*_mg),
                   prop, index, back, std::ref(found)));
98
99
100
101
102
    if (!found)
        throw GraphException("invalid writable property map");
}


103
104
105
106
107
108
109
110
111
112
113
114
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);
115
116
                if (old_index[v] != int(i))
                    pmap[v] = pmap[vertex(old_index[v], g)];
117
118
119
120
121
122
123
124
125
126
127
            }
            found = true;
        }
        catch (bad_any_cast&) {}
    }
};


void GraphInterface::ReIndexVertexProperty(boost::any map,
                                           boost::any aold_index) const
{
128
    typedef property_map_type::apply<int64_t,
129
130
131
132
133
134
                                     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
135
136
        (std::bind(reindex_vertex_property(), std::placeholders::_1, std::ref(*_mg),
                   map, old_index, std::ref(found)));
137
138
139
140
    if (!found)
        throw GraphException("invalid writable property map");

}
141

142
} // graph_tool namespace
143
144
145
146
147
148


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
149
                    boost::python::object oval) const
150
151
152
153
    {
        typedef typename property_traits<PropertyMap>::value_type val_t;
        bool all = false;

Tiago Peixoto's avatar
Tiago Peixoto committed
154
155
        std::unordered_set<val_t, std::hash<val_t> > vals;
        if (oval == boost::python::object())
156
157
158
159
160
161
162
        {
            all = true;
        }
        else
        {
            for (int i = 0; i < len(oval); ++i)
            {
Tiago Peixoto's avatar
Tiago Peixoto committed
163
                val_t val = boost::python::extract<val_t>(oval[i]);
164
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
193
194
195
196
197
198
199
200
201
202
                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
203
                            boost::python::object val)
204
{
Tiago Peixoto's avatar
Tiago Peixoto committed
205
206
        run_action<>()(gi, std::bind(do_infect_vertex_property(), std::placeholders::_1,
                                     gi.GetVertexIndex(), std::placeholders::_2, val),
207
208
                   writable_vertex_properties())(prop);
}
Tiago Peixoto's avatar
Tiago Peixoto committed
209
210
211
212
213
214
215
216
217
218
219

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

220
221
222
223
224
225
226
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)     \
227
                schedule(runtime) if (N > 100)
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
        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
245
246
247
248
249
250
251
252
253
254


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;
255
        typedef unordered_map<val_t, hash_t> dict_t;
Tiago Peixoto's avatar
Tiago Peixoto committed
256
257
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

        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;
294
        typedef unordered_map<val_t, hash_t> dict_t;
Tiago Peixoto's avatar
Tiago Peixoto committed
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323

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