graph_properties.cc 8.29 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-2013 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

25
26
#include "tr1_include.hh"
#include TR1_HEADER(unordered_set)
27

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

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

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

36
37
namespace graph_tool
{
38

39
// global property types' names
40
const char* type_names[] =
41
42
43
44
    {"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"};
45
46


47
struct shift_vertex_property
48
{
49
50
51
    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
52
    {
53
        try
Tiago Peixoto's avatar
Tiago Peixoto committed
54
        {
55
56
57
            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)];
58
            found = true;
59
        }
60
        catch (bad_any_cast&) {}
61
    }
62
63
};

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

75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
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>
        (bind<void>(move_vertex_property(), _1, ref(*_mg),
                    prop, index, back, ref(found)));
    if (!found)
        throw GraphException("invalid writable property map");
}


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


void GraphInterface::ReIndexVertexProperty(boost::any map,
                                           boost::any aold_index) const
{
    typedef property_map_type::apply<int32_t,
                                     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>
136
        (bind<void>(reindex_vertex_property(), _1, ref(*_mg),
137
138
139
140
141
                    map, old_index, ref(found)));
    if (!found)
        throw GraphException("invalid writable property map");

}
142

143
} // graph_tool namespace
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
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
203
204
205
206
207
208
209


struct do_infect_vertex_property
{
    template <class Graph, class IndexMap, class PropertyMap>
    void operator()(Graph& g, IndexMap index, PropertyMap prop,
                    python::object oval) const
    {
        typedef typename property_traits<PropertyMap>::value_type val_t;
        bool all = false;

        tr1::unordered_set<val_t, boost::hash<val_t> > vals;
        if (oval == python::object())
        {
            all = true;
        }
        else
        {
            for (int i = 0; i < len(oval); ++i)
            {
                val_t val = python::extract<val_t>(oval[i]);
                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,
                            python::object val)
{
    run_action<>()(gi, bind<void>(do_infect_vertex_property(), _1,
                                  gi.GetVertexIndex(), _2, val),
                   writable_vertex_properties())(prop);
}
Tiago Peixoto's avatar
Tiago Peixoto committed
210
211
212
213
214
215
216
217
218
219
220
221
222
223

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

struct do_edge_difference
{
    template <class Graph, class EdgeIndexMap, class VertexPropertyMap>
224
    void operator()(Graph& g, EdgeIndexMap, VertexPropertyMap prop,
Tiago Peixoto's avatar
Tiago Peixoto committed
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
                    boost::any eprop) const
    {
        typedef typename property_traits<VertexPropertyMap>::value_type vval_t;
        typedef typename mpl::if_<is_same<vval_t, size_t>, int32_t, vval_t>::type
            val_t;
        typedef typename property_map_type::apply<val_t, EdgeIndexMap>::type
            eprop_t;
        eprop_t ediff = any_cast<eprop_t>(eprop);
        ediff.reserve(num_edges(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;
            typename graph_traits<Graph>::out_edge_iterator e, e_end;
            for (tie(e, e_end) = out_edges(v, g); e != e_end; ++e)
                ediff[*e] = prop[target(*e, g)] - prop[source(*e, g)];
        }
    }
};

void edge_difference(GraphInterface& gi, boost::any prop,
                     boost::any eprop)
{
252
253
254
    typedef mpl::insert_range<vertex_scalar_properties,
                              mpl::end<vertex_scalar_properties>::type,
                              vertex_scalar_vector_properties>::type vprops_t;
Tiago Peixoto's avatar
Tiago Peixoto committed
255
256
257
258
    run_action<>()(gi, bind<void>(do_edge_difference(), _1,
                                  gi.GetEdgeIndex(), _2, eprop),
                   vprops_t())(prop);
}