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