graph_betweenness.cc 8.46 KB
Newer Older
Tiago Peixoto's avatar
Tiago Peixoto committed
1
2
// graph-tool -- a general graph modification and manipulation thingy
//
Tiago Peixoto's avatar
Tiago Peixoto committed
3
// Copyright (C) 2006-2020 Tiago de Paula Peixoto <tiago@skewed.de>
Tiago Peixoto's avatar
Tiago Peixoto committed
4
//
5
6
7
8
// This program is free software; you can redistribute it and/or modify it under
// the terms of the GNU Lesser General Public License as published by the Free
// Software Foundation; either version 3 of the License, or (at your option) any
// later version.
Tiago Peixoto's avatar
Tiago Peixoto committed
9
//
10
11
12
13
// 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 Lesser General Public License for more
// details.
Tiago Peixoto's avatar
Tiago Peixoto committed
14
//
15
// You should have received a copy of the GNU Lesser General Public License
Tiago Peixoto's avatar
Tiago Peixoto committed
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// along with this program. If not, see <http://www.gnu.org/licenses/>.

#include "graph_filtering.hh"

#include <boost/python.hpp>
#include <boost/graph/betweenness_centrality.hpp>

#include "graph.hh"
#include "graph_selectors.hh"
#include "graph_util.hh"

using namespace std;
using namespace boost;
using namespace graph_tool;

template <class Graph, class EdgeBetweenness, class VertexBetweenness>
void normalize_betweenness(const Graph& g,
33
                           std::vector<size_t>& pivots,
Tiago Peixoto's avatar
Tiago Peixoto committed
34
35
36
37
                           EdgeBetweenness edge_betweenness,
                           VertexBetweenness vertex_betweenness,
                           size_t n)
{
38
39
40
41
    size_t p = pivots.size();
    double pfactor = (p > 1 && n > 2) ? ((p - 1) * (n - 2)) : .0;
    double vfactor = (p > 0 && n > 2) ? (p * (n - 2)) : .0;
    double efactor = (p > 0 && n > 1) ? (p * (n - 1)) : .0;
Tiago Peixoto's avatar
Tiago Peixoto committed
42
43
    if (std::is_convertible<typename graph_traits<Graph>::directed_category,
                            undirected_tag>::value)
Tiago Peixoto's avatar
Tiago Peixoto committed
44
    {
45
46
47
        pfactor /= 2;
        vfactor /= 2;
        efactor /= 2;
Tiago Peixoto's avatar
Tiago Peixoto committed
48
49
    }

50
51
52
53
54
55
56
    pfactor = (pfactor > 0) ? 1./pfactor : 0;
    vfactor = (vfactor > 0) ? 1./vfactor : 0;
    efactor = (efactor > 0) ? 1./efactor : 0;

    typedef typename vprop_map_t<bool>::type::unchecked_t vprop_t;
    vprop_t is_pivot(get(vertex_index, g), num_vertices(g));

57
58
59
60
61
62
63
64
65
66
67
68
69
    for (auto v : pivots)
        is_pivot[v] = true;

    for (auto v : vertices_range(g))
    {
        if (is_pivot[v])
            put(vertex_betweenness, v, pfactor * get(vertex_betweenness, v));
        else
            put(vertex_betweenness, v, vfactor * get(vertex_betweenness, v));
    }

    for (auto e : edges_range(g))
        put(edge_betweenness, e, efactor * get(edge_betweenness, e));
Tiago Peixoto's avatar
Tiago Peixoto committed
70
71
72
73
}

struct get_betweenness
{
Tiago Peixoto's avatar
Tiago Peixoto committed
74
    typedef void result_type;
Tiago Peixoto's avatar
Tiago Peixoto committed
75
    template <class Graph, class EdgeBetweenness, class VertexBetweenness>
76
    void operator()(Graph& g,
77
                    std::vector<size_t>& pivots,
Tiago Peixoto's avatar
Tiago Peixoto committed
78
79
                    GraphInterface::vertex_index_map_t index_map,
                    EdgeBetweenness edge_betweenness,
80
                    VertexBetweenness vertex_betweenness) const
Tiago Peixoto's avatar
Tiago Peixoto committed
81
82
    {
        vector<vector<typename graph_traits<Graph>::edge_descriptor> >
83
84
            incoming_map(num_vertices(g));
        vector<size_t> distance_map(num_vertices(g));
Tiago Peixoto's avatar
Tiago Peixoto committed
85
        vector<typename property_traits<VertexBetweenness>::value_type>
86
87
            dependency_map(num_vertices(g));
        vector<size_t> path_count_map(num_vertices(g));
Tiago Peixoto's avatar
Tiago Peixoto committed
88
        brandes_betweenness_centrality
89
            (g, pivots, vertex_betweenness, edge_betweenness,
Tiago Peixoto's avatar
Tiago Peixoto committed
90
91
92
93
94
95
96
97
98
99
             make_iterator_property_map(incoming_map.begin(), index_map),
             make_iterator_property_map(distance_map.begin(), index_map),
             make_iterator_property_map(dependency_map.begin(), index_map),
             make_iterator_property_map(path_count_map.begin(), index_map),
             index_map);
    }
};

struct get_weighted_betweenness
{
Tiago Peixoto's avatar
Tiago Peixoto committed
100
    typedef void result_type;
Tiago Peixoto's avatar
Tiago Peixoto committed
101
102
    template <class Graph, class EdgeBetweenness, class VertexBetweenness,
              class VertexIndexMap>
103
104
105
106
    void operator()(Graph& g, std::vector<size_t>& pivots,
                    VertexIndexMap vertex_index,
                    EdgeBetweenness edge_betweenness,
                    VertexBetweenness vertex_betweenness,
107
108
                    boost::any weight_map,
                    size_t max_eindex) const
Tiago Peixoto's avatar
Tiago Peixoto committed
109
110
    {
        vector<vector<typename graph_traits<Graph>::edge_descriptor> >
111
            incoming_map(num_vertices(g));
Tiago Peixoto's avatar
Tiago Peixoto committed
112
        vector<typename property_traits<EdgeBetweenness>::value_type>
113
            distance_map(num_vertices(g));
Tiago Peixoto's avatar
Tiago Peixoto committed
114
        vector<typename property_traits<VertexBetweenness>::value_type>
115
116
            dependency_map(num_vertices(g));
        vector<size_t> path_count_map(num_vertices(g));
Tiago Peixoto's avatar
Tiago Peixoto committed
117

118
119
120
        typename EdgeBetweenness::checked_t weight =
            any_cast<typename EdgeBetweenness::checked_t>(weight_map);

Tiago Peixoto's avatar
Tiago Peixoto committed
121
        brandes_betweenness_centrality
122
            (g, pivots, vertex_betweenness, edge_betweenness,
Tiago Peixoto's avatar
Tiago Peixoto committed
123
124
125
126
             make_iterator_property_map(incoming_map.begin(), vertex_index),
             make_iterator_property_map(distance_map.begin(), vertex_index),
             make_iterator_property_map(dependency_map.begin(), vertex_index),
             make_iterator_property_map(path_count_map.begin(), vertex_index),
127
             vertex_index, weight.get_unchecked(max_eindex+1));
Tiago Peixoto's avatar
Tiago Peixoto committed
128
129
130
    }
};

131
132
void betweenness(GraphInterface& g, std::vector<size_t>& pivots,
                 boost::any weight,
Tiago Peixoto's avatar
Tiago Peixoto committed
133
                 boost::any edge_betweenness,
134
                 boost::any vertex_betweenness)
Tiago Peixoto's avatar
Tiago Peixoto committed
135
136
{
    if (!belongs<edge_floating_properties>()(edge_betweenness))
Tiago Peixoto's avatar
Tiago Peixoto committed
137
        throw ValueException("edge property must be of floating point value"
138
                             " type");
Tiago Peixoto's avatar
Tiago Peixoto committed
139
140

    if (!belongs<vertex_floating_properties>()(vertex_betweenness))
Tiago Peixoto's avatar
Tiago Peixoto committed
141
        throw ValueException("vertex property must be of floating point value"
142
                             " type");
Tiago Peixoto's avatar
Tiago Peixoto committed
143
144
145
146

    if (!weight.empty())
    {
        run_action<>()
147
148
149
150
151
152
153
154
155
156
157
            (g,
             [&](auto&& graph, auto&& a2, auto&& a3)
             {
                 return get_weighted_betweenness()
                     (std::forward<decltype(graph)>(graph), pivots,
                      g.get_vertex_index(), std::forward<decltype(a2)>(a2),
                      std::forward<decltype(a3)>(a3), weight,
                      g.get_edge_index_range());
             },
             edge_floating_properties(), vertex_floating_properties())(
                edge_betweenness, vertex_betweenness);
Tiago Peixoto's avatar
Tiago Peixoto committed
158
159
160
161
    }
    else
    {
        run_action<>()
162
163
164
165
166
167
168
169
170
171
            (g,
             [&](auto&& graph, auto&& a2, auto&& a3)
             {
                 return get_betweenness()
                     (std::forward<decltype(graph)>(graph), pivots,
                      g.get_vertex_index(), std::forward<decltype(a2)>(a2),
                      std::forward<decltype(a3)>(a3));
             },
             edge_floating_properties(), vertex_floating_properties())(
                edge_betweenness, vertex_betweenness);
Tiago Peixoto's avatar
Tiago Peixoto committed
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
void norm_betweenness(GraphInterface& g, std::vector<size_t>& pivots,
                      boost::any edge_betweenness,
                      boost::any vertex_betweenness)
{
    if (!belongs<edge_floating_properties>()(edge_betweenness))
        throw ValueException("edge property must be of floating point value"
                             " type");

    if (!belongs<vertex_floating_properties>()(vertex_betweenness))
        throw ValueException("vertex property must be of floating point value"
                             " type");

    size_t n = g.get_num_vertices();
    run_action<>()
        (g, [&](auto& g, auto ep, auto vp)
            {
                normalize_betweenness(g, pivots, ep, vp, n);
            },
         edge_floating_properties(),
         vertex_floating_properties())
        (edge_betweenness, vertex_betweenness);
}


Tiago Peixoto's avatar
Tiago Peixoto committed
199
200
201
struct get_central_point_dominance
{
    template <class Graph, class VertexBetweenness>
202
    void operator()(Graph& g, VertexBetweenness vertex_betweenness, double& c)
Tiago Peixoto's avatar
Tiago Peixoto committed
203
204
        const
    {
205
        c = central_point_dominance(g, vertex_betweenness);
Tiago Peixoto's avatar
Tiago Peixoto committed
206
207
208
209
210
211
212
213
    }
};

double central_point(GraphInterface& g,
                     boost::any vertex_betweenness)
{
    double c = 0.0;
    run_action<graph_tool::detail::never_reversed>()
214
215
216
217
218
219
220
221
        (g,
         [&](auto&& graph, auto&& a2)
         {
             return get_central_point_dominance()
                 (std::forward<decltype(graph)>(graph),
                  std::forward<decltype(a2)>(a2), c);
         },
         vertex_scalar_properties())(vertex_betweenness);
Tiago Peixoto's avatar
Tiago Peixoto committed
222
223
224
225
226
227
228
    return c;
}

void export_betweenness()
{
    using namespace boost::python;
    def("get_betweenness", &betweenness);
229
    def("norm_betweenness", &norm_betweenness);
Tiago Peixoto's avatar
Tiago Peixoto committed
230
231
    def("get_central_point_dominance", &central_point);
}