graph_clustering.hh 4.51 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
//
// 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.
//
15
// you should have received a copy of the GNU General Public License
16 17 18 19 20
// along with this program. If not, see <http://www.gnu.org/licenses/>.

#ifndef GRAPH_CLUSTERING_HH
#define GRAPH_CLUSTERING_HH

21 22
#include "config.h"

23
#include "hash_map_wrap.hh"
24 25
#include <boost/mpl/if.hpp>

26 27 28 29
#ifdef USING_OPENMP
#include "omp.h"
#endif

Tiago Peixoto's avatar
Tiago Peixoto committed
30
#ifndef __clang__
31 32
#include <ext/numeric>
using __gnu_cxx::power;
Tiago Peixoto's avatar
Tiago Peixoto committed
33 34 35 36 37 38 39
#else
template <class Value>
Value power(Value value, int n)
{
    return pow(value, n);
}
#endif
40

41 42 43
namespace graph_tool
{
using namespace boost;
44
using namespace std;
45 46

// calculates the number of triangles to which v belongs
47
template <class Graph, class VProp>
48
pair<int,int>
49
get_triangles(typename graph_traits<Graph>::vertex_descriptor v, VProp& mark,
50
              const Graph& g)
51
{
52
    size_t triangles = 0;
53

54
    for (auto n : adjacent_vertices_range(v, g))
55
    {
56
        if (n == v)
57
            continue;
58
        mark[n] = true;
59
    }
60

61
    for (auto n : adjacent_vertices_range(v, g))
62
    {
63 64 65
        if (n == v)
            continue;
        for (auto n2 : adjacent_vertices_range(n, g))
66
        {
67
            if (n2 == n)
68
                continue;
69
            if (mark[n2])
70
                ++triangles;
71 72
        }
    }
73

74 75 76
    for (auto n : adjacent_vertices_range(v, g))
        mark[n] = false;

77
    size_t k = out_degree(v, g);
78 79 80 81
    if (is_directed::apply<Graph>::type::value)
        return make_pair(triangles, (k * (k - 1)));
    else
        return make_pair(triangles / 2, (k * (k - 1)) / 2);
82 83 84 85 86 87 88
}


// retrieves the global clustering coefficient
struct get_global_clustering
{
    template <class Graph>
89
    void operator()(const Graph& g, double& c, double& c_err) const
90 91
    {
        size_t triangles = 0, n = 0;
92
        vector<bool> mask(num_vertices(g), false);
93

Tiago Peixoto's avatar
Tiago Peixoto committed
94 95 96 97 98 99 100 101 102 103
        #pragma omp parallel if (num_vertices(g) > OPENMP_MIN_THRESH) \
            firstprivate(mask) reduction(+:triangles, n)
        parallel_vertex_loop_no_spawn
                (g,
                 [&](auto v)
                 {
                     auto temp = get_triangles(v, mask, g);
                     triangles += temp.first;
                     n += temp.second;
                 });
104
        c = double(triangles) / n;
105 106 107

        // "jackknife" variance
        c_err = 0.0;
108
        double cerr = 0.0;
Tiago Peixoto's avatar
Tiago Peixoto committed
109 110 111 112 113 114 115 116 117 118 119
        #pragma omp parallel if (num_vertices(g) > OPENMP_MIN_THRESH) \
            firstprivate(mask) reduction(+:cerr)
        parallel_vertex_loop_no_spawn
                (g,
                 [&](auto v)
                 {
                     auto temp = get_triangles(v, mask, g);
                     double cl = double(triangles - temp.first) /
                         (n - temp.second);
                     cerr += power(c - cl, 2);
                 });
120
        c_err = sqrt(cerr);
121 122 123 124 125 126 127
    }
};

// sets the local clustering coefficient to a property
struct set_clustering_to_property
{
    template <class Graph, class ClustMap>
128
    void operator()(const Graph& g, ClustMap clust_map) const
129
    {
130
        typedef typename property_traits<ClustMap>::value_type c_type;
131
        vector<bool> mask(num_vertices(g), false);
132

Tiago Peixoto's avatar
Tiago Peixoto committed
133 134 135 136 137 138
        #pragma omp parallel if (num_vertices(g) > OPENMP_MIN_THRESH) \
            firstprivate(mask)
        parallel_vertex_loop_no_spawn
            (g,
             [&](auto v)
             {
139
                 auto triangles = get_triangles(v, mask, g);
Tiago Peixoto's avatar
Tiago Peixoto committed
140 141 142 143 144
                 double clustering = (triangles.second > 0) ?
                     double(triangles.first)/triangles.second :
                     0.0;
                 clust_map[v] = c_type(clustering);
             });
145
    }
146

147 148 149 150
    template <class Graph>
    struct get_undirected_graph
    {
        typedef typename mpl::if_
Tiago Peixoto's avatar
Tiago Peixoto committed
151 152 153 154
           <std::is_convertible<typename graph_traits<Graph>::directed_category,
                                directed_tag>,
            const UndirectedAdaptor<Graph>,
            const Graph& >::type type;
155 156 157
    };
};

158
} //graph-tool namespace
159 160

#endif // GRAPH_CLUSTERING_HH