graph_properties.cc 7.4 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-2012 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
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);
89 90
                if (old_index[v] != int(i))
                    pmap[v] = pmap[vertex(old_index[v], g)];
91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114
            }
            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");

}
115

116
} // graph_tool namespace
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 182


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
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 224

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)
{
225 226 227
    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
228 229 230 231
    run_action<>()(gi, bind<void>(do_edge_difference(), _1,
                                  gi.GetEdgeIndex(), _2, eprop),
                   vprops_t())(prop);
}