graph_reciprocity.cc 2.32 KB
Newer Older
1
2
// graph-tool -- a general graph modification and manipulation thingy
//
Tiago Peixoto's avatar
Tiago Peixoto committed
3
// Copyright (C) 2006-2013 Tiago de Paula Peixoto <tiago@skewed.de>
4
5
6
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
Tiago Peixoto's avatar
Tiago Peixoto committed
7
// as published by the Free Software Foundation; either version 3
8
9
10
11
12
13
14
15
// 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
16
17
// along with this program. If not, see <http://www.gnu.org/licenses/>.

18
19
20
21
22
23
24
25
26
27
28
29
30

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

using namespace std;
using namespace boost;
using namespace graph_tool;

struct get_reciprocity
{
    template <class Graph>
Tiago Peixoto's avatar
Tiago Peixoto committed
31
    void operator()(const Graph& g, double& reciprocity) const
32
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
33
        size_t L = 0, Lbd = 0;
34

35
        int i, NV = num_vertices(g);
36
        #pragma omp parallel for default(shared) private(i) reduction(+:L,Lbd) \
37
            schedule(static, 100)
38
        for (i = 0; i < NV; ++i)
39
        {
40
41
42
            typename graph_traits<Graph>::vertex_descriptor v = vertex(i, g);
            if (v == graph_traits<Graph>::null_vertex())
                continue;
43

44
45
46
47
            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)
            {
Tiago Peixoto's avatar
Tiago Peixoto committed
48
49
                typename graph_traits<Graph>::vertex_descriptor t;
                t = target(*e, g);
50

51
52
                typename graph_traits<Graph>::adjacency_iterator a, a_end;
                for (tie(a, a_end) = adjacent_vertices(t, g); a != a_end; ++a)
Tiago Peixoto's avatar
Tiago Peixoto committed
53
54
55
56
57
                    if (*a == v)
                    {
                        Lbd += 1;
                        break;
                    }
58
59
60
61
                L++;
            }
        }

Tiago Peixoto's avatar
Tiago Peixoto committed
62
        reciprocity = Lbd / double(L);
63
64
65
    }
};

Tiago Peixoto's avatar
Tiago Peixoto committed
66
double reciprocity(GraphInterface& gi)
67
68
{
    double reciprocity;
Tiago Peixoto's avatar
Tiago Peixoto committed
69
70
    run_action<>()(gi, bind<void>(get_reciprocity(), _1,
                                  ref(reciprocity)))();
71
72
    return reciprocity;
}