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