graph_distance_sampled.hh 5.93 KB
Newer Older
1
2
// graph-tool -- a general graph modification and manipulation thingy
//
Tiago Peixoto's avatar
Tiago Peixoto committed
3
// Copyright (C) 2007-2012 Tiago de Paula Peixoto <tiago@skewed.de>
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//
// 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_DISTANCE_SAMPLED_HH
#define GRAPH_DISTANCE_SAMPLED_HH

#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
23
24
25
26
27
28
29

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

#include "histogram.hh"
#include "numpy_bind.hh"
30
31
32
33
34
35

namespace graph_tool
{
using namespace std;
using namespace boost;

36
// retrieves the sampled vertex-vertex distance histogram
37
38
39

struct no_weightS {};

40
41
template <class Map>
struct get_val_type
42
{
43
44
    typedef typename property_traits<Map>::value_type type;
};
45

46
47
48
49
50
51
52
53
54
55
56
57
58
template <>
struct get_val_type<no_weightS>
{
    typedef size_t type;
};

struct get_sampled_distance_histogram
{

    template <class Graph, class VertexIndex, class WeightMap, class RNG>
    void operator()(const Graph& g, VertexIndex vertex_index, WeightMap weights,
                    size_t n_samples, const vector<long double>& obins,
                    python::object& phist, RNG& rng) const
59
60
61
    {
        typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;

62
        // select get_vertex_dists based on the existence of weights
63
        typedef typename mpl::if_<is_same<WeightMap, no_weightS>,
64
                                  get_dists_bfs,
65
66
67
                                  get_dists_djk>::type get_vertex_dists_t;


68
69
70
        // distance type
        typedef typename get_val_type<WeightMap>::type val_type;
        typedef Histogram<val_type, size_t, 1> hist_t;
71

72
73
74
75
        array<vector<val_type>,1> bins;
        bins[0].resize(obins.size());
        for (size_t i = 0; i < obins.size(); ++i)
            bins[0][i] = obins[i];
76

77
        hist_t hist(bins);
78
        SharedHistogram<hist_t> s_hist(hist);
79

80
81
82
        vector<vertex_t> sources;
        sources.reserve(num_vertices(g));
        int i;
83
        for (i = 0; i < int(num_vertices(g)); ++i)
84
85
86
            if (vertex(i,g) != graph_traits<Graph>::null_vertex())
                sources.push_back(vertex(i,g));
        n_samples = min(n_samples, sources.size());
87

88
89
90
91
92
93
94
        typename hist_t::point_t point;
        get_vertex_dists_t get_vertex_dists;
        #pragma omp parallel for default(shared) private(i,point) \
            firstprivate(s_hist) schedule(dynamic)
        for (i = 0; i < int(n_samples); ++i)
        {
            vertex_t v;
95
            tr1::uniform_int<size_t> randint(0, sources.size()-1);
96
            {
97
98
99
100
101
                #pragma omp critical
                size_t i = randint(rng);
                v = sources[i];
                swap(sources[i], sources.back());
                sources.pop_back();
102
103
            }

104
105
106
107
            unchecked_vector_property_map<val_type,VertexIndex>
                dist_map(vertex_index, num_vertices(g));

            for (size_t j = 0; j < num_vertices(g); ++j)
108
            {
109
110
                if (vertex(i,g) != graph_traits<Graph>::null_vertex())
                    dist_map[vertex(j,g)] =  numeric_limits<val_type>::max();
111
            }
112
113
114
115
116
117
118
119
120
121
122
123

            dist_map[v] = 0;
            get_vertex_dists(g, v, vertex_index, dist_map, weights);

            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())
                {
                    point[0] = dist_map[*v2];
                    s_hist.PutValue(point);
                }
124
        }
125
        s_hist.Gather();
126

127
128
129
130
        python::list ret;
        ret.append(wrap_multi_array_owned<size_t,1>(hist.GetArray()));
        ret.append(wrap_vector_owned<val_type>(hist.GetBins()[0]));
        phist = ret;
131
132
133
134
135
    }

    // weighted version. Use dijkstra_shortest_paths()
    struct get_dists_djk
    {
136
137
138
        template <class Graph, class Vertex, class VertexIndex,
                  class DistanceMap, class WeightMap>
        void operator()(const Graph& g, Vertex s, VertexIndex vertex_index,
139
140
                        DistanceMap dist_map, WeightMap weights) const
        {
141
            dijkstra_shortest_paths(g, s, vertex_index_map(vertex_index).
142
143
144
145
146
147
148
                                    weight_map(weights).distance_map(dist_map));
        }
    };

    // unweighted version. Use BFS.
    struct get_dists_bfs
    {
149
150
151
        template <class Graph, class Vertex, class VertexIndex,
                  class DistanceMap>
        void operator()(const Graph& g, Vertex s, VertexIndex vertex_index,
152
153
                        DistanceMap dist_map, no_weightS) const
        {
154
155
156
157
158
159
160
161
162
163
164
165
            typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
            typedef tr1::unordered_map<vertex_t,default_color_type,
                                       DescriptorHash<VertexIndex> > cmap_t;
            cmap_t cmap(0, DescriptorHash<VertexIndex>(vertex_index));
            InitializedPropertyMap<cmap_t>
                color_map(cmap, color_traits<default_color_type>::white());

            breadth_first_visit(g, s,
                                visitor(make_bfs_visitor
                                        (record_distances(dist_map,
                                                          on_tree_edge()))).
                                color_map(color_map));
166
167
168
169
        }
    };
};

170
} // boost namespace
171
172

#endif // GRAPH_DISTANCE_SAMPLED_HH