graph_histograms.hh 4.43 KB
Newer Older
Tiago Peixoto's avatar
Tiago Peixoto committed
1
// Copyright (C) 2008  Tiago de Paula Peixoto <tiago@skewed.de>
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//
// 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/>.

16
17
18
19
20
21
22
23
24
25
26
27
28
29
#ifndef GRAPH_HISTOGRAMS_HH
#define GRAPH_HISTOGRAMS_HH

#include <algorithm>
#include <boost/numeric/conversion/bounds.hpp>
#include <boost/numeric/conversion/cast.hpp>
#include <boost/python/object.hpp>
#include <boost/python/list.hpp>
#include <boost/python/extract.hpp>
#include "numpy_bind.hh"
#include "histogram.hh"
#include "shared_map.hh"

namespace graph_tool
30
{
31
32
using namespace std;
using namespace boost;
33

34
class VertexHistogramFiller
35
{
36
37
public:
    template <class Graph, class DegreeSelector, class Hist>
38
39
    void operator()(const Graph& g,
                    typename graph_traits<Graph>::vertex_descriptor v,
40
                    DegreeSelector& deg, Hist& hist)
41
    {
42
43
44
        typename Hist::point_t p;
        p[0] = deg(v, g);
        hist.PutValue(p);
45
    }
46
};
47

48
class EdgeHistogramFiller
49
{
50
51
public:
    template <class Graph, class EdgeProperty, class Hist>
52
53
    void operator()(const Graph& g,
                    typename graph_traits<Graph>::vertex_descriptor v,
54
55
                    EdgeProperty& eprop, Hist& hist)
    {
56
        typename Hist::point_t p;
57
58
59
        typename graph_traits<Graph>::out_edge_iterator e, e_begin, e_end;
        tie(e_begin,e_end) = out_edges(v,g);
        for(e = e_begin; e != e_end; ++e)
60
        {
61
62
            p[0] = eprop[*e];
            hist.PutValue(p);
63
64
65
66
        }
    }
};

67
68
69
// generalized functor to obtain histogram of different types of "degrees"
template <class HistogramFiller>
struct get_histogram
70
{
71
72
73
74
75
    get_histogram(python::object& hist, const vector<long double>& bins,
                  python::object& ret_bins)
        : _hist(hist), _bins(bins), _ret_bins(ret_bins) {}

    template <class Graph, class DegreeSelector>
76
    void operator()(const Graph& g, DegreeSelector deg) const
77
    {
78
79
        typedef typename DegreeSelector::value_type value_type;
        typedef Histogram<value_type, size_t, 1> hist_t;
80

81
        HistogramFiller filler;
82

Tiago Peixoto's avatar
Tiago Peixoto committed
83
        vector<value_type> bins(_bins.size());
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
        for (size_t i = 0; i < bins.size(); ++i)
        {
            // we'll attempt to recover from out of bounds conditions
            try
            {
                bins[i] = numeric_cast<value_type,long double>(_bins[i]);
            }
            catch (boost::numeric::negative_overflow&)
            {
                bins[i] = boost::numeric::bounds<value_type>::lowest();
            }
            catch (boost::numeric::positive_overflow&)
            {
                bins[i] = boost::numeric::bounds<value_type>::highest();
            }
        }
100

101
102
        // sort the bins
        sort(bins.begin(), bins.end());
103

104
105
106
107
108
109
110
111
112
        // clean bins of zero size
        vector<value_type> temp_bin(1);
        temp_bin[0] = bins[0];
        for (size_t j = 1; j < bins.size(); ++j)
        {
            if (bins[j] > bins[j-1])
                temp_bin.push_back(bins[j]);
        }
        bins = temp_bin;
113

114
115
116
        boost::array<vector<value_type>, 1> bin_list;
        bin_list[0] = bins;

117
        hist_t hist(bin_list);
118
        SharedHistogram<hist_t> s_hist(hist);
119
120

        int i, N = num_vertices(g);
121
122
        #pragma omp parallel for default(shared) private(i) \
            firstprivate(s_hist) schedule(dynamic)
123
124
125
126
127
        for (i = 0; i < N; ++i)
        {
            typename graph_traits<Graph>::vertex_descriptor v = vertex(i, g);
            if (v == graph_traits<Graph>::null_vertex())
                continue;
Tiago Peixoto's avatar
Tiago Peixoto committed
128
            filler(g, v, deg, s_hist);
129
        }
130
        s_hist.Gather();
131

132
133
134
135
        bin_list = hist.GetBins();
        python::object ret_bins = wrap_vector_owned(bin_list[0]);
        _ret_bins = ret_bins;
        _hist = wrap_multi_array_owned<size_t,1>(hist.GetArray());
136
    }
137
138
139
140
    python::object& _hist;
    const vector<long double>& _bins;
    python::object& _ret_bins;
};
141

142
} // graph_tool namespace
143

144
#endif // GRAPH_HISTOGRAMS_HH