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-2017 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
218

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];
    return v1;
}

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
219
    {
220
221
        for (auto vi : vertices_range(g))
            temp[vi] = vprop[vi] * get(vweight, vi);
222
    }
223
};
224

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

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;

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

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

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

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

struct get_edge_community_property_sum
{
    template <class Graph, class CommunityGraph, class CommunityMap,
264
              class CCommunityMap, class Eprop, class CEprop>
265
    void operator()(const Graph& g, CommunityGraph& cg, CommunityMap s_map,
266
267
                    CCommunityMap cs_map, Eprop eprop, CEprop ceprop,
                    bool self_loops, bool parallel_edges) const
268
    {
269
270
271
272
273
274
275
276
        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;

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

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

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

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

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

            auto* ces = &comm_edges[make_pair(cs, ct)];
299
            if (ces->empty() && !graph_tool::is_directed(g))
300
301
302
303
304
305
306
307
308
309
                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();
310
        }
311
    }
312
};
313

314
315
316
} // graph_tool namespace

#endif // GRAPH_COMMUNITY_NETWORK_HH