graph_community_network.hh 5.54 KB
Newer Older
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>
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 22 23 24 25
#if (GCC_VERSION >= 40400)
#   include <tr1/unordered_map>
#else
#   include <boost/tr1/unordered_map.hpp>
#endif
26 27 28 29 30 31 32 33 34 35 36 37 38
#include <iostream>
#include <iomanip>

namespace graph_tool
{

using namespace std;
using namespace boost;

// retrieves the network of communities given a community structure

struct get_community_network
{
39
    template <class Graph, class CommunityGraph, class CommunityMap,
40 41 42
              class CCommunityMap,
              class VertexWeightMap, class EdgeWeightMap, class EdgeIndex,
              class VertexIndex, class VertexProperty, class EdgeProperty>
43
    void operator()(const Graph& g, CommunityGraph& cg,
44
                    VertexIndex cvertex_index, EdgeIndex cedge_index,
45 46
                    CommunityMap s_map, CCommunityMap cs_map,
                    VertexWeightMap vweight, EdgeWeightMap eweight,
47 48
                    VertexProperty vertex_count, EdgeProperty edge_count,
                    bool self_loops) const
49 50 51
    {
        typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
        typedef typename graph_traits<Graph>::edge_descriptor edge_t;
52 53 54 55 56 57
        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;
58 59
        typedef typename boost::property_traits<VertexProperty>::value_type
            vprop_type;
60

61
        tr1::unordered_map<s_type, pair<vector<vertex_t>, vprop_type>, hash<s_type> >
62 63 64
            comms;
        typename graph_traits<Graph>::vertex_iterator v, v_end;
        for (tie(v, v_end) = vertices(g); v != v_end; ++v)
65 66 67 68 69
        {
            pair<vector<vertex_t>, vprop_type>& m = comms[get(s_map, *v)];
            m.first.push_back(*v);
            m.second += get(vweight, *v);
        }
70

71
        // create vertices
72
        tr1::unordered_map<s_type, cvertex_t, hash<s_type> >
73
            comm_vertices;
74 75 76
        for (typeof(comms.begin()) iter = comms.begin(); iter != comms.end();
             ++iter)
        {
77
            cvertex_t v = add_vertex(cg);
78
            put(vertex_count, v, iter->second.second);
79
            comm_vertices[iter->first] = v;
80 81 82 83
            put_dispatch(cs_map, v, iter->first,
                         typename boost::is_convertible
                            <typename property_traits<CommunityMap>::category,
                             writable_property_map_tag>::type());
84 85
        }

86 87
        // create edges
        tr1::unordered_map<pair<size_t, size_t>,
88
                           cedge_t, hash<pair<size_t, size_t> > >
89 90 91
            comm_edges;
        for (typeof(comms.begin()) iter = comms.begin(); iter != comms.end();
             ++iter)
92
        {
93
            cvertex_t cs = comm_vertices[iter->first];
94
            for (size_t i = 0; i < iter->second.first.size(); ++i)
95
            {
96
                vertex_t s = iter->second.first[i];
97 98 99 100 101
                typename graph_traits<Graph>::out_edge_iterator e, e_end;
                for (tie(e, e_end) = out_edges(s, g); e != e_end; ++e)
                {
                    vertex_t t = target(*e, g);
                    cvertex_t ct = comm_vertices[get(s_map, t)];
102
                    if (ct == cs && !self_loops)
103 104 105 106 107 108 109 110 111
                        continue;
                    cedge_t ce;
                    if (comm_edges.find(make_pair(cs, ct)) != comm_edges.end())
                        ce = comm_edges[make_pair(cs, ct)];
                    else if (!is_directed::apply<Graph>::type::value &&
                             comm_edges.find(make_pair(ct, cs)) != comm_edges.end())
                        ce = comm_edges[make_pair(ct, cs)];
                    else
                    {
112
                        ce = add_edge(cs, ct, cg).first;
113
                        comm_edges[make_pair(cs, ct)] = ce;
114
                        put(cedge_index, ce, comm_edges.size() - 1);
115
                    }
116
                    put(edge_count, ce, get(edge_count, ce) + get(eweight, *e));
117
                }
118 119 120
            }
        }
    }
121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138

    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 cs_map,
                      const typename property_traits<PropertyMap>::key_type& v,
                      const typename property_traits<PropertyMap>::value_type& val,
                      mpl::false_ is_writable) const
    {
    }

139 140 141 142 143
};

} // graph_tool namespace

#endif // GRAPH_COMMUNITY_NETWORK_HH