graph_community_network.hh 10.1 KB
Newer Older
1 2
// graph-tool -- a general graph modification and manipulation thingy
//
Tiago Peixoto's avatar
Tiago Peixoto committed
3
// Copyright (C) 2006-2018 Tiago de Paula Peixoto <tiago@skewed.de>
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 3
// 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
// along with this program. If not, see <http://www.gnu.org/licenses/>.

#ifndef GRAPH_COMMUNITY_NETWORK_HH
#define GRAPH_COMMUNITY_NETWORK_HH

21
#include "hash_map_wrap.hh"
22

23 24 25 26 27 28 29 30 31 32 33
#include <iostream>
#include <iomanip>

namespace graph_tool
{

using namespace std;
using namespace boost;

// retrieves the network of communities given a community structure

34
struct get_community_network_vertices
35
{
36
    template <class Graph, class CommunityGraph, class CommunityMap,
37 38 39 40 41
              class CCommunityMap, class VertexWeightMap,
              class VertexProperty>
    void operator()(const Graph& g, CommunityGraph& cg, CommunityMap s_map,
                    CCommunityMap cs_map, VertexWeightMap vweight,
                    VertexProperty vertex_count) const
42 43
    {
        typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
44 45 46 47 48
        typedef typename graph_traits<CommunityGraph>::vertex_descriptor
            cvertex_t;
        typedef typename boost::property_traits<CommunityMap>::value_type
            s_type;

49
        unordered_map<s_type, vertex_t> comms;
50

51
        // create vertices
52
        for (auto vi : vertices_range(g))
53
        {
54
            s_type s = get(s_map, vi);
55
            auto iter = comms.find(s);
56 57 58 59 60 61 62
            cvertex_t v;
            if (iter == comms.end())
            {
                comms[s] = v = add_vertex(cg);
                put_dispatch(cs_map, v, s,
                             typename boost::is_convertible
                             <typename property_traits<CommunityMap>::category,
63
                             writable_property_map_tag>::type());
64 65 66 67 68
            }
            else
            {
                v = iter->second;
            }
69
            put(vertex_count, v, get(vertex_count, v) + get(vweight, vi));
70
        }
71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96
    }

    template <class PropertyMap>
    void put_dispatch(PropertyMap cs_map,
                      const typename property_traits<PropertyMap>::key_type& v,
                      const typename property_traits<PropertyMap>::value_type& val,
                      mpl::true_ /*is_writable*/) const
    {
        put(cs_map, v, val);
    }

    template <class PropertyMap>
    void put_dispatch(PropertyMap,
                      const typename property_traits<PropertyMap>::key_type&,
                      const typename property_traits<PropertyMap>::value_type&,
                      mpl::false_ /*is_writable*/) const
    {
    }

};

struct get_community_network_edges
{
    template <class Graph, class CommunityGraph, class CommunityMap,
              class CCommunityMap, class EdgeWeightMap,
              class EdgeIndex, class EdgeProperty>
97
    void operator()(const Graph& g, CommunityGraph& cg, EdgeIndex,
98 99
                    CommunityMap s_map, CCommunityMap cs_map,
                    EdgeWeightMap eweight, EdgeProperty edge_count,
100
                    bool self_loops, bool parallel_edges) const
101 102 103 104 105 106 107 108 109
    {
        typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
        typedef typename graph_traits<CommunityGraph>::vertex_descriptor
            cvertex_t;
        typedef typename graph_traits<CommunityGraph>::edge_descriptor
            cedge_t;
        typedef typename boost::property_traits<CommunityMap>::value_type
            s_type;

110
        typedef unordered_map<s_type, vertex_t> comms_t;
111
        comms_t comms;
112
        typedef unordered_map<cvertex_t, cedge_t> ecomms_t;
113

114 115 116
        auto index_map = get(vertex_index_t(), cg);
        unchecked_vector_property_map<ecomms_t, decltype(index_map)>
            comm_edges(index_map, num_vertices(cg));
117

118 119
        for (auto v : vertices_range(cg))
            comms[cs_map[v]] = v;
120

121
        // create edges
122
        for (auto e : edges_range(g))
123
        {
124 125
            cvertex_t cs = comms[get(s_map, source(e, g))];
            cvertex_t ct = comms[get(s_map, target(e, g))];
126 127 128
            if (ct == cs && !self_loops)
                continue;
            cedge_t ce;
129

130
            if (parallel_edges)
131
            {
132
                ce = add_edge(cs, ct, cg).first;
133
            }
134
            else
135
            {
136
                auto iter = comm_edges[cs].find(ct);
137 138 139 140 141
                if (iter != comm_edges[cs].end())
                {
                    ce = iter->second;
                }
                else
142
                {
143
                    if (!graph_tool::is_directed(g))
144
                    {
145 146 147 148 149 150 151 152 153 154
                        iter = comm_edges[ct].find(cs);
                        if (iter != comm_edges[ct].end())
                        {
                            ce = iter->second;
                        }
                        else
                        {
                            ce = add_edge(cs, ct, cg).first;
                            comm_edges[cs][ct] = ce;
                        }
155 156 157 158
                    }
                    else
                    {
                        ce = add_edge(cs, ct, cg).first;
159
                        comm_edges[cs][ct] = ce;
160 161
                    }
                }
162
            }
163
            put(edge_count, ce, get(edge_count, ce) + get(eweight, e));
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 210 211 212 213 214 215 216 217

template <class T1, class T2>
inline vector<T1> operator*(const vector<T1>& v, const T2& c)
{
    vector<T1> r(v);
    for (size_t i = 0; i < r.size(); ++i)
        r[i] = v[i] * c;
    return r;
}

template <class T1, class T2>
inline void operator/=(vector<T1>& v, const T2& c)
{
    for (size_t i = 0; i < v.size(); ++i)
        v[i] /= c;
}

template <class T1, class T2>
inline vector<T1> operator*(const vector<T1>& v1, const vector<T2>& v2)
{
    vector<T1> r(max(v1.size(), v2.size()));
    for (size_t i = 0; i < min(v1.size(), v2.size()); ++i)
        r[i] = v1[i] * v2[i];
    return r;
}

template <class T1, class T2>
inline void operator/=(vector<T1>& v1, const vector<T2>& v2)
{
    v1.resize(max(v1.size(), v2.size()));
    for (size_t i = 0; i < v2.size(); ++i)
        v1[i] /= v2[i];
}

template <class T1, class T2>
inline void operator+=(vector<T1>& v1, const vector<T2>& v2)
{
    v1.resize(max(v1.size(), v2.size()));
    for (size_t i = 0; i < v2.size(); ++i)
        v1[i] += v2[i];
}


// retrieves the average property of a community structure

struct get_weighted_vertex_property
{
    template <class Graph, class VertexWeightMap, class Vprop>
    void operator()(const Graph& g, VertexWeightMap vweight, Vprop vprop,
                    Vprop temp) const
218
    {
219 220
        for (auto vi : vertices_range(g))
            temp[vi] = vprop[vi] * get(vweight, vi);
221
    }
222
};
223

224 225 226 227 228 229 230 231 232 233 234 235

struct get_vertex_community_property_sum
{
    template <class Graph, class CommunityGraph, class CommunityMap,
              class CCommunityMap, class Vprop>
    void operator()(const Graph& g, CommunityGraph& cg, CommunityMap s_map,
                    CCommunityMap cs_map, Vprop vprop, Vprop cvprop) const
    {
        typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
        typedef typename boost::property_traits<CommunityMap>::value_type
            s_type;

236
        unordered_map<s_type, vertex_t> comms;
237 238 239 240 241

        for (auto v : vertices_range(cg))
            comms[cs_map[v]] = v;

        for (auto v : vertices_range(g))
242
        {
243 244
            s_type s = get(s_map, v);
            cvprop[comms[s]] += vprop[v];
245 246 247 248 249 250 251 252 253 254
        }
    }
};

struct get_weighted_edge_property
{
    template <class Graph, class EdgeWeightMap, class Eprop>
    void operator()(const Graph& g, EdgeWeightMap eweight, Eprop eprop,
                    Eprop temp) const
    {
255 256
        for (auto e : edges_range(g))
            temp[e] = eprop[e] * get(eweight, e);
257 258 259 260 261 262
    }
};

struct get_edge_community_property_sum
{
    template <class Graph, class CommunityGraph, class CommunityMap,
263
              class CCommunityMap, class Eprop, class CEprop>
264
    void operator()(const Graph& g, CommunityGraph& cg, CommunityMap s_map,
265 266
                    CCommunityMap cs_map, Eprop eprop, CEprop ceprop,
                    bool self_loops, bool parallel_edges) const
267
    {
268 269 270 271 272 273 274 275
        typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
        typedef typename graph_traits<CommunityGraph>::vertex_descriptor
            cvertex_t;
        typedef typename graph_traits<CommunityGraph>::edge_descriptor
            cedge_t;
        typedef typename boost::property_traits<CommunityMap>::value_type
            s_type;

276
        unordered_map<s_type, vertex_t> comms;
277 278 279 280

        for (auto v : vertices_range(cg))
            comms[cs_map[v]] = v;

281
        gt_hash_map<pair<size_t, size_t>, vector<cedge_t>> comm_edges;
282 283

        for (auto e : edges_range(cg))
284
        {
285 286
            cvertex_t cs = comms[get(cs_map, source(e, cg))];
            cvertex_t ct = comms[get(cs_map, target(e, cg))];
287
            comm_edges[make_pair(cs, ct)].push_back(e);
288 289
        }

290
        for (auto e : edges_range(g))
291
        {
292 293
            cvertex_t cs = comms[get(s_map, source(e, g))];
            cvertex_t ct = comms[get(s_map, target(e, g))];
294 295 296 297
            if (cs == ct && !self_loops)
                continue;  // self-loops not allowed

            auto* ces = &comm_edges[make_pair(cs, ct)];
298
            if (ces->empty() && !graph_tool::is_directed(g))
299 300 301 302 303 304 305 306 307 308
                ces = &comm_edges[make_pair(ct, cs)];
            if (ces->empty())
            {
                throw GraphException("Bug: condensed edge not found! " +
                                     lexical_cast<string>(cs) +  " " +
                                     lexical_cast<string>(ct));
            }
            ceprop[ces->back()] += eprop[e];
            if (parallel_edges)
                ces->pop_back();
309
        }
310
    }
311
};
312

313 314 315
} // graph_tool namespace

#endif // GRAPH_COMMUNITY_NETWORK_HH