graph_closeness.hh 6.05 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-2017 Tiago de Paula Peixoto <tiago@skewed.de>
Tiago Peixoto's avatar
Tiago Peixoto committed
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//
// 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_CLOSENESS_HH
#define GRAPH_CLOSENESS_HH

#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>

#include <boost/python/object.hpp>
#include <boost/python/list.hpp>
#include <boost/python/extract.hpp>

#include "histogram.hh"
29
#include "hash_map_wrap.hh"
Tiago Peixoto's avatar
Tiago Peixoto committed
30
31
32
33
34
35
36
37
38
39

namespace graph_tool
{
using namespace std;

struct no_weightS {};

template <class Map>
struct get_val_type
{
Tiago Peixoto's avatar
Tiago Peixoto committed
40
    typedef typename boost::property_traits<Map>::value_type type;
Tiago Peixoto's avatar
Tiago Peixoto committed
41
42
43
44
45
46
47
48
49
50
};

template <>
struct get_val_type<no_weightS>
{
    typedef size_t type;
};

struct get_closeness
{
Tiago Peixoto's avatar
Tiago Peixoto committed
51
    typedef void result_type;
Tiago Peixoto's avatar
Tiago Peixoto committed
52
53
54
55
56
    template <class Graph, class VertexIndex, class WeightMap, class Closeness>
    void operator()(const Graph& g, VertexIndex vertex_index, WeightMap weights,
                    Closeness closeness, bool harmonic, bool norm)
        const
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
57
        using namespace boost;
Tiago Peixoto's avatar
Tiago Peixoto committed
58
59

        // select get_vertex_dists based on the existence of weights
Tiago Peixoto's avatar
Tiago Peixoto committed
60
        typedef typename mpl::if_<std::is_same<WeightMap, no_weightS>,
Tiago Peixoto's avatar
Tiago Peixoto committed
61
62
63
64
65
66
67
68
                                  get_dists_bfs,
                                  get_dists_djk>::type get_vertex_dists_t;

        // distance type
        typedef typename get_val_type<WeightMap>::type val_type;

        get_vertex_dists_t get_vertex_dists;
        size_t HN = HardNumVertices()(g);
69
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
97
98
99
100
101
102
103
104
105
106
        parallel_vertex_loop
            (g,
             [&](auto v)
             {
                 unchecked_vector_property_map<val_type,VertexIndex>
                     dist_map(vertex_index, num_vertices(g));

                 for (auto u : vertices_range(g))
                     dist_map[u] = numeric_limits<val_type>::max();

                 dist_map[v] = 0;

                 size_t comp_size = 0;
                 get_vertex_dists(g, v, vertex_index, dist_map, weights, comp_size);

                 closeness[v] = 0;
                 for (auto v2 : vertices_range(g))
                 {
                     if (v2 != v && dist_map[v2] != numeric_limits<val_type>::max())
                     {
                         if (!harmonic)
                             closeness[v] += dist_map[v2];
                         else
                             closeness[v] += 1. / dist_map[v2];
                     }
                 }

                 if (!harmonic)
                     closeness[v] = 1 / closeness[v];

                 if (norm)
                 {
                     if (harmonic)
                         closeness[v] /= HN - 1;
                     else
                         closeness[v] *= comp_size - 1;
                 }
             });
Tiago Peixoto's avatar
Tiago Peixoto committed
107
108
    }

109

Tiago Peixoto's avatar
Tiago Peixoto committed
110
    class component_djk_visitor: public boost::dijkstra_visitor<>
Tiago Peixoto's avatar
Tiago Peixoto committed
111
112
113
114
115
116
117
    {
    public:
        //component_visitor() { }
        component_djk_visitor(size_t& comp_size)
            : _comp_size(comp_size) { }

        template <class Vertex, class Graph>
118
        void discover_vertex(Vertex, const Graph&)
Tiago Peixoto's avatar
Tiago Peixoto committed
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
        {
            ++_comp_size;
        }

    private:
        size_t& _comp_size;
    };

    // weighted version. Use dijkstra_shortest_paths()
    struct get_dists_djk
    {
        template <class Graph, class Vertex, class VertexIndex,
                  class DistanceMap, class WeightMap>
        void operator()(const Graph& g, Vertex s, VertexIndex vertex_index,
                        DistanceMap dist_map, WeightMap weights,
                        size_t& comp_size) const
        {
Tiago Peixoto's avatar
Tiago Peixoto committed
136
            using namespace boost;
Tiago Peixoto's avatar
Tiago Peixoto committed
137
138
139
140
141
142
143
            component_djk_visitor vis(comp_size);
            dijkstra_shortest_paths(g, s, vertex_index_map(vertex_index).
                                    weight_map(weights).distance_map(dist_map).visitor(vis));
        }
    };

    template <class DistMap>
Tiago Peixoto's avatar
Tiago Peixoto committed
144
    class component_bfs_visitor: public boost::bfs_visitor<>
Tiago Peixoto's avatar
Tiago Peixoto committed
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
    {
    public:
        //component_visitor() { }
        component_bfs_visitor(DistMap dist_map, size_t& comp_size)
            : _dist_map(dist_map), _comp_size(comp_size) { }

        template <class Vertex, class Graph>
        void discover_vertex(Vertex, const Graph&)
        {
            ++_comp_size;
        }

        template <class Edge, class Graph>
        void tree_edge(Edge e, const Graph& g)
        {
            _dist_map[target(e, g)] = _dist_map[source(e, g)] + 1;
        }

    private:
        DistMap _dist_map;
        size_t& _comp_size;
    };


    // unweighted version. Use BFS.
    struct get_dists_bfs
    {
        template <class Graph, class Vertex, class VertexIndex,
                  class DistanceMap>
        void operator()(const Graph& g, Vertex s, VertexIndex vertex_index,
                        DistanceMap dist_map, no_weightS, size_t& comp_size) const
        {
Tiago Peixoto's avatar
Tiago Peixoto committed
177
            using namespace boost;
Tiago Peixoto's avatar
Tiago Peixoto committed
178
            typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
179
180
            typedef gt_hash_map<vertex_t,default_color_type,
                                DescriptorHash<VertexIndex> > cmap_t;
Tiago Peixoto's avatar
Tiago Peixoto committed
181
182
183
184
185
186
187
188
189
190
191
192
193
            cmap_t cmap(0, DescriptorHash<VertexIndex>(vertex_index));
            InitializedPropertyMap<cmap_t>
                color_map(cmap, color_traits<default_color_type>::white());
            component_bfs_visitor<DistanceMap> vis(dist_map, comp_size);
            breadth_first_visit(g, s, visitor(vis).
                                color_map(color_map));
        }
    };
};

} // boost namespace

#endif // GRAPH_CLOSENESS_HH