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;
}