graph_properties.cc 7.35 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) 2007-2011 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.hh"
Tiago Peixoto's avatar
Tiago Peixoto committed
19
#include "graph_properties.hh"
20
#include "graph_filtering.hh"
21
#include "graph_selectors.hh"
22
#include "graph_util.hh"
Tiago Peixoto's avatar
Tiago Peixoto committed
23

24
25
26
27
28
29
#if (GCC_VERSION >= 40400)
#   include <tr1/unordered_set>
#else
#   include <boost/tr1/unordered_set.hpp>
#endif

30
31
#include <boost/mpl/for_each.hpp>

32
33
#include <boost/python/extract.hpp>

34
35
36
37
using namespace std;
using namespace boost;
using namespace graph_tool;

38
39
namespace graph_tool
{
40

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


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

66
67
// this function will shift all the properties when a vertex is to be deleted
void GraphInterface::ShiftVertexProperty(boost::any prop, size_t index) const
68
{
69
    bool found = false;
70
    mpl::for_each<writable_vertex_properties>
Tiago Peixoto's avatar
Tiago Peixoto committed
71
        (bind<void>(shift_vertex_property(), _1, ref(_state->_mg),
72
                    prop, index, ref(found)));
73
    if (!found)
74
        throw GraphException("invalid writable property map");
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
104
105
106
107
108
109
110
111
112
113
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);
                pmap[v] = pmap[vertex(old_index[v], g)];
            }
            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>
        (bind<void>(reindex_vertex_property(), _1, ref(_state->_mg),
                    map, old_index, ref(found)));
    if (!found)
        throw GraphException("invalid writable property map");

}
114

115
} // graph_tool namespace
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
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


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
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
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>
    void operator()(Graph& g, EdgeIndexMap edge_index, VertexPropertyMap prop,
                    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)
{
224
225
226
    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
227
228
229
230
    run_action<>()(gi, bind<void>(do_edge_difference(), _1,
                                  gi.GetEdgeIndex(), _2, eprop),
                   vprops_t())(prop);
}