graph_closeness.hh 6.38 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-2015 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
29
30
31
32
33
34
35
36
37
38
39
//
// 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"
#include "numpy_bind.hh"

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
60
        typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;

        // select get_vertex_dists based on the existence of weights
Tiago Peixoto's avatar
Tiago Peixoto committed
61
        typedef typename mpl::if_<std::is_same<WeightMap, no_weightS>,
Tiago Peixoto's avatar
Tiago Peixoto committed
62
63
64
65
66
67
68
69
70
                                  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);
        int i, N = num_vertices(g);
71
        #pragma omp parallel for default(shared) private(i) schedule(runtime) if (N > 100)
Tiago Peixoto's avatar
Tiago Peixoto committed
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
107
108
109
110
111
112
113
114
115
        for (i = 0; i < N; ++i)
        {
            vertex_t v = vertex(i, g);
            if (v == graph_traits<Graph>::null_vertex())
                continue;

            unchecked_vector_property_map<val_type,VertexIndex>
                dist_map(vertex_index, num_vertices(g));

            for (int j = 0; j < N; ++j)
            {
                if (vertex(j, g) != graph_traits<Graph>::null_vertex())
                    dist_map[vertex(j, g)] = 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;
            typename graph_traits<Graph>::vertex_iterator v2, v_end;
            for (tie(v2, v_end) = vertices(g); v2 != v_end; ++v2)
            {
                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
116
    class component_djk_visitor: public boost::dijkstra_visitor<>
Tiago Peixoto's avatar
Tiago Peixoto committed
117
118
119
120
121
122
123
    {
    public:
        //component_visitor() { }
        component_djk_visitor(size_t& comp_size)
            : _comp_size(comp_size) { }

        template <class Vertex, class Graph>
124
        void discover_vertex(Vertex, const Graph&)
Tiago Peixoto's avatar
Tiago Peixoto committed
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
        {
            ++_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
142
            using namespace boost;
Tiago Peixoto's avatar
Tiago Peixoto committed
143
144
145
146
147
148
149
            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
150
    class component_bfs_visitor: public boost::bfs_visitor<>
Tiago Peixoto's avatar
Tiago Peixoto committed
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
177
178
179
180
181
182
    {
    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
183
            using namespace boost;
Tiago Peixoto's avatar
Tiago Peixoto committed
184
            typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
Tiago Peixoto's avatar
Tiago Peixoto committed
185
186
            typedef unordered_map<vertex_t,default_color_type,
                                  DescriptorHash<VertexIndex> > cmap_t;
Tiago Peixoto's avatar
Tiago Peixoto committed
187
188
189
190
191
192
193
194
195
196
197
198
199
            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