graph_histograms.hh 4.43 KB
Newer Older
1
// Copyright (C) 2006-2013 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
        #pragma omp parallel for default(shared) private(i) \
122
            firstprivate(s_hist) schedule(static, 100)
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