graph_correlations_neighbours.cc 5.36 KB
Newer Older
Tiago Peixoto's avatar
Tiago Peixoto committed
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
// 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/lambda/lambda.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;

//==============================================================================
37
38
// average_nearest_neighbours_correlation
// return generalized average nearest neighbours correlation
Tiago Peixoto's avatar
Tiago Peixoto committed
39
40
//==============================================================================

41
template <class DegreeSelectorOrigin, class DegreeSelectorNeighbours>
42
struct get_average_nearest_neighbours_correlation
Tiago Peixoto's avatar
Tiago Peixoto committed
43
{
44
    get_average_nearest_neighbours_correlation(DegreeSelectorOrigin& origin_deg, DegreeSelectorNeighbours& neighbours_deg)
Tiago Peixoto's avatar
Tiago Peixoto committed
45
46
47
48
49
50
51
52
53
54
55
	: _origin_degree(origin_deg), _neighbours_degree(neighbours_deg) {}

    template <class Graph, class AvgDeg>
    void operator()(const Graph& g, AvgDeg& avg_deg) const
    {
	tr1::unordered_map<double,size_t> count;

	typename graph_traits<Graph>::vertex_iterator v, v_begin, v_end;
	tie(v_begin,v_end) = vertices(g);
	for(v = v_begin; v != v_end; ++v)
	{
56
57
	    typename graph_traits<Graph>::out_edge_iterator e, e_begin, e_end;
	    tie(e_begin,e_end) = out_edges(*v,g);
Tiago Peixoto's avatar
Tiago Peixoto committed
58
59
	    for(e = e_begin; e != e_end; ++e)
	    {		
60
		typename AvgDeg::value_type::second_type::first_type deg = _neighbours_degree(target(*e,g),g);
Tiago Peixoto's avatar
Tiago Peixoto committed
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
		typename AvgDeg::key_type orig_deg = _origin_degree(*v,g);
		avg_deg[orig_deg].first += deg;
		avg_deg[orig_deg].second += deg*deg;
		count[orig_deg]++;
	    }
	}

	for (typeof(avg_deg.begin()) iter = avg_deg.begin(); iter != avg_deg.end(); ++iter)
	{
	    size_t N = count[iter->first];
	    iter->second.first /= N;
	    if (N > 1)
		iter->second.second = sqrt((iter->second.second - N*iter->second.first*iter->second.first)/(N*(N-1)));
	    else
		iter->second.second = 0.0;
	}
    }
    DegreeSelectorOrigin& _origin_degree;
    DegreeSelectorNeighbours& _neighbours_degree;
};

template <class DegreeSelectors>
83
struct choose_average_nearest_neighbours_correlation
Tiago Peixoto's avatar
Tiago Peixoto committed
84
{
85
    choose_average_nearest_neighbours_correlation(const GraphInterface &g, GraphInterface::deg_t origin_deg, GraphInterface::deg_t neighbour_deg, GraphInterface::avg_corr_t &avg_deg)
86
	: _g(g), _avg_deg(avg_deg) 
Tiago Peixoto's avatar
Tiago Peixoto committed
87
88
89
90
91
    {
	tie(_origin_deg, _origin_deg_name) = get_degree_type(origin_deg);
	tie(_neighbour_deg, _neighbour_deg_name) = get_degree_type(neighbour_deg);
    }

92
    template <class OriginDegreeSelector>
Tiago Peixoto's avatar
Tiago Peixoto committed
93
94
    struct choose_neighbour_degree
    {
95
	choose_neighbour_degree(choose_average_nearest_neighbours_correlation<DegreeSelectors>& parent):_parent(parent) {}
Tiago Peixoto's avatar
Tiago Peixoto committed
96
97
98
99
	template <class DegreeSelector>
	void operator()(DegreeSelector)
	{
	    if ( mpl::at<degree_selector_index, DegreeSelector>::type::value == _parent._neighbour_deg)
100
101
102
	    {
		OriginDegreeSelector origin_deg(_parent._origin_deg_name, _parent._g);
		DegreeSelector deg(_parent._neighbour_deg_name, _parent._g);
103
		check_filter(_parent._g, bind<void>(get_average_nearest_neighbours_correlation<OriginDegreeSelector,DegreeSelector>(origin_deg, deg),
104
						    _1, var(_parent._avg_deg)),
Tiago Peixoto's avatar
Tiago Peixoto committed
105
			     reverse_check(),directed_check()); 
106
	    }
Tiago Peixoto's avatar
Tiago Peixoto committed
107
	}
108
	choose_average_nearest_neighbours_correlation<DegreeSelectors> &_parent;
Tiago Peixoto's avatar
Tiago Peixoto committed
109
110
    };

111
112
    template <class DegreeSelector>
    void operator()(DegreeSelector)
Tiago Peixoto's avatar
Tiago Peixoto committed
113
    {
114
115
	if (mpl::at<degree_selector_index, DegreeSelector>::type::value == _origin_deg)
	    mpl::for_each<DegreeSelectors>(choose_neighbour_degree<DegreeSelector>(*this));
Tiago Peixoto's avatar
Tiago Peixoto committed
116
117
118
119
120
121
122
123
124
125
126
    }

    const GraphInterface &_g;
    GraphInterface::avg_corr_t &_avg_deg;
    GraphInterface::degree_t _origin_deg;
    string _origin_deg_name;
    GraphInterface::degree_t _neighbour_deg;
    string _neighbour_deg_name;
};

//==============================================================================
127
// GetAverageNearestNeighboursCorrelation(neigh, orign_deg, neighbours_deg)
Tiago Peixoto's avatar
Tiago Peixoto committed
128
129
//==============================================================================
GraphInterface::avg_corr_t
130
GraphInterface::GetAverageNearestNeighboursCorrelation(deg_t origin_deg, deg_t neighbours_deg ) const
Tiago Peixoto's avatar
Tiago Peixoto committed
131
132
133
134
135
136
{
    GraphInterface::avg_corr_t avg_corr;

    try 
    {
	typedef mpl::vector<in_degreeS,out_degreeS,total_degreeS,scalarS> degrees;
137
	mpl::for_each<degrees>(choose_average_nearest_neighbours_correlation<degrees>(*this, origin_deg, neighbours_deg, avg_corr));
Tiago Peixoto's avatar
Tiago Peixoto committed
138
139
140
141
142
143
144
145
    }
    catch (dynamic_get_failure &e)
    {
	throw GraphException("error getting scalar property: " + string(e.what()));
    }

    return avg_corr;
}