graph_distance_sampled.cc 5.85 KB
Newer Older
1
2
3
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
40
41
42
43
44
45
46
47
48
49
// graph-tool -- a general graph modification and manipulation thingy
//
// Copyright (C) 2006  Tiago de Paula Peixoto <tiago@forked.de>
//
// 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 2
// 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, write to the Free Software
// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.

#include <algorithm>
#include <tr1/unordered_set>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/lambda/bind.hpp>
#include <boost/random.hpp>

#include "graph.hh"
#include "histogram.hh"
#include "graph_filtering.hh"
#include "graph_selectors.hh"
#include "graph_properties.hh"

using namespace std;
using namespace boost;
using namespace boost::lambda;
using namespace graph_tool;

typedef boost::mt19937 rng_t;

//==============================================================================
// GetSampledDistanceHistogram()
// retrieves the histogram of sampled vertex-vertex distances
//==============================================================================
struct no_weightS {};

struct get_sampled_distances
{

    template <class Graph, class IndexMap, class WeightMap, class Hist>
    void operator()(const Graph &g, IndexMap index_map, WeightMap weights, Hist& hist, size_t samples, size_t seed) const
50
51
52
53
    {        
        // select get_sum_vertex_dists based on the existence of weights
        typedef typename mpl::if_<is_same<WeightMap, no_weightS>,
                                       get_dists_bfs,
54
                                  get_dists_djk>::type get_vertex_dists_t;
55
56
57
58
59
        get_vertex_dists_t get_vertex_dists;

        tr1::unordered_map<size_t, typename graph_traits<Graph>::vertex_descriptor> descriptors;

        typename graph_traits<Graph>::vertex_iterator v, v_end;
60
        int i = 0, N = 0;
61
        for(tie(v, v_end) = vertices(g); v != v_end; ++v,++i)
62
        {
63
            descriptors[i] = *v;
64
65
            N++;
        }
66
67
68
69

        rng_t rng(static_cast<rng_t::result_type>(seed));
        uniform_int<size_t> sampler(0,descriptors.size()-1);

70
71
        #pragma omp parallel for default(shared) private(i,v,v_end) 
        for(i=0; i < int(samples); ++i)
72
        {
73
74
75
            typedef HashedDescriptorMap<IndexMap,double> dist_map_t;
            dist_map_t dist_map(index_map);

76
            for(tie(v, v_end) = vertices(g); v != v_end; ++v)
77
                dist_map[*v] = numeric_limits<double>::max();
78
79
80
            typename graph_traits<Graph>::vertex_descriptor s,t;

            #pragma omp critical
81
            {
82
83
84
85
86
87
                s = descriptors[sampler(rng)];
                do
                {
                    t = descriptors[sampler(rng)];
                }
                while (t == s && N != 1);
88
89
            }

90
91
            dist_map[s] = 0.0;
            get_vertex_dists(g, s, index_map, dist_map, weights);
92
            if (dist_map[t] != numeric_limits<double>::max() && dist_map[t] != 0.0)
93
94
            {
                #pragma omp atomic
95
                hist[dist_map[t]]++;
96
            }
97
98
        }
        
99
100
101
102
103
    }

    // weighted version. Use dijkstra_shortest_paths()
    struct get_dists_djk
    {
104
105
106
        template <class Graph, class Vertex, class IndexMap, class DistanceMap, class WeightMap>
        void operator()(const Graph& g, Vertex s, IndexMap index_map, DistanceMap dist_map, WeightMap weights) const
        {
107
            dijkstra_shortest_paths(g, s, vertex_index_map(index_map).weight_map(weights).distance_map(dist_map));            
108
        }
109
110
111
112
113
    };

    // unweighted version. Use BFS.
    struct get_dists_bfs
    {
114
115
        template <class Graph, class Vertex, class IndexMap, class DistanceMap>
        void operator()(const Graph& g, Vertex s, IndexMap index_map, DistanceMap dist_map, no_weightS) const
116
        {            
117
118
            breadth_first_search(g, s, visitor(make_bfs_visitor(record_distances(dist_map, on_tree_edge()))));
        }
119
120
121
122
123
124
125
126
127
128
129
    };
    
};

GraphInterface::hist_t 
GraphInterface::GetSampledDistanceHistogram(string weight, size_t samples, size_t seed) const
{
    hist_t hist;

    if (weight == "")
    {
130
        check_filter(*this, bind<void>(get_sampled_distances(), _1, _vertex_index, no_weightS(), var(hist), samples, seed),
131
                     reverse_check(), directed_check()); 
132
133
134
    }
    else
    {
135
136
137
138
139
        try 
        {
            dynamic_property_map& weight_prop = find_property_map(_properties, weight, typeid(graph_traits<multigraph_t>::edge_descriptor));
            try 
            {
140
141
142
143
                vector_property_map<double, edge_index_map_t> weight_map;
                weight_map = get_static_property_map<vector_property_map<double, edge_index_map_t> >(weight_prop);
                check_filter(*this, bind<void>(get_sampled_distances(), _1, _vertex_index, weight_map, var(hist), samples, seed),
                             reverse_check(), directed_check()); 
144
145
146
            }
            catch (bad_cast)
            {
147
148
149
                DynamicPropertyMapWrap<double, graph_traits<multigraph_t>::edge_descriptor> weight_map(weight_prop);
                check_filter(*this, bind<void>(get_sampled_distances(), _1, _vertex_index, weight_map, var(hist), samples, seed),
                             reverse_check(), directed_check()); 
150
151
152
153
154
155
            }
        }
        catch (property_not_found& e)
        {
            throw GraphException("error getting scalar property: " + string(e.what()));
        }
156
157
158
    }
    return hist;
}