graph_histograms.hh 4.37 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
38
39
public:
    template <class Graph, class DegreeSelector, class Hist>
    void operator()(Graph& g, typename graph_traits<Graph>::vertex_descriptor v,
                    DegreeSelector& deg, Hist& hist)
40
    {
41
42
43
        typename Hist::point_t p;
        p[0] = deg(v, g);
        hist.PutValue(p);
44
    }
45
};
46

47
class EdgeHistogramFiller
48
{
49
50
51
52
53
public:
    template <class Graph, class EdgeProperty, class Hist>
    void operator()(Graph& g, typename graph_traits<Graph>::vertex_descriptor v,
                    EdgeProperty& eprop, Hist& hist)
    {
54
        typename Hist::point_t p;
55
56
57
        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)
58
        {
59
60
            p[0] = eprop[*e];
            hist.PutValue(p);
61
62
63
64
        }
    }
};

65
66
67
// generalized functor to obtain histogram of different types of "degrees"
template <class HistogramFiller>
struct get_histogram
68
{
69
70
71
72
73
    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>
74
    void operator()(Graph& g, DegreeSelector deg) const
75
    {
76
77
        typedef typename DegreeSelector::value_type value_type;
        typedef Histogram<value_type, size_t, 1> hist_t;
78

79
        HistogramFiller filler;
80

Tiago Peixoto's avatar
Tiago Peixoto committed
81
        vector<value_type> bins(_bins.size());
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
        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();
            }
        }
98

99
100
        // sort the bins
        sort(bins.begin(), bins.end());
101

102
103
104
105
106
107
108
109
110
        // 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;
111

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

115
        hist_t hist(bin_list);
116
        SharedHistogram<hist_t> s_hist(hist);
117
118

        int i, N = num_vertices(g);
119
120
        #pragma omp parallel for default(shared) private(i) \
            firstprivate(s_hist) schedule(dynamic)
121
122
123
124
125
        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
126
            filler(g, v, deg, s_hist);
127
        }
128
        s_hist.Gather();
129

130
131
132
133
        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());
134
    }
135
136
137
138
    python::object& _hist;
    const vector<long double>& _bins;
    python::object& _ret_bins;
};
139

140
} // graph_tool namespace
141

142
#endif // GRAPH_HISTOGRAMS_HH