graph_absolute_trust.hh 6.68 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
// graph-tool -- a general graph modification and manipulation thingy
//
// Copyright (C) 2007  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 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/>.

#ifndef GRAPH_ABSOLUTE_TRUST_HH
#define GRAPH_ABSOLUTE_TRUST_HH

#include "graph.hh"
#include "graph_filtering.hh"
#include "graph_util.hh"

Tiago Peixoto's avatar
Tiago Peixoto committed
25
#include <tr1/unordered_set>
26
27
28
29
#include <tr1/tuple>
#include <algorithm>

#include "minmax.hh"
Tiago Peixoto's avatar
Tiago Peixoto committed
30

31
32
#include <iostream>

Tiago Peixoto's avatar
Tiago Peixoto committed
33
34
35
36
namespace graph_tool
{
using namespace std;
using namespace boost;
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
using std::tr1::get;
using std::tr1::tuple;

template <class Path>
struct path_cmp
{
    path_cmp(vector<Path>& paths): _paths(paths) {}
    vector<Path>& _paths;

    typedef size_t first_argument_type;
    typedef size_t second_argument_type;
    typedef bool result_type;
    inline bool operator()(size_t a, size_t b)
    {
        if (get<0>(_paths[a]).first == get<0>(_paths[b]).first)
            return get<1>(_paths[a]).size() > get<1>(_paths[b]).size();
        return get<0>(_paths[a]).first < get<0>(_paths[b]).first;
    }
};
Tiago Peixoto's avatar
Tiago Peixoto committed
56

57
struct get_absolute_trust
Tiago Peixoto's avatar
Tiago Peixoto committed
58
{
59
    template <class Graph, class VertexIndex, class TrustMap,
Tiago Peixoto's avatar
Tiago Peixoto committed
60
              class InferredTrustMap>
61
    void operator()(Graph& g, VertexIndex vertex_index, int64_t source,
62
63
                    TrustMap c, InferredTrustMap t, size_t n_paths,
                    double epsilon, bool reversed) const
Tiago Peixoto's avatar
Tiago Peixoto committed
64
    {
65
        typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
Tiago Peixoto's avatar
Tiago Peixoto committed
66
67
68
69
        typedef typename property_traits<TrustMap>::value_type c_type;
        typedef typename property_traits<InferredTrustMap>::value_type
            ::value_type t_type;

70
71
        typedef tuple<pair<t_type, t_type>, tr1::unordered_set<vertex_t>,
                      size_t > path_t;
Tiago Peixoto's avatar
Tiago Peixoto committed
72

73
        double delta = epsilon+1;
Tiago Peixoto's avatar
Tiago Peixoto committed
74
        int i, N = num_vertices(g);
75
        #pragma omp parallel for default(shared) private(i) schedule(dynamic)
76
77
        for (i = (source == -1) ? 0 : source;
             i < ((source == -1) ? N : source + 1); ++i)
Tiago Peixoto's avatar
Tiago Peixoto committed
78
        {
79
            vertex_t v = vertex(i, g);
Tiago Peixoto's avatar
Tiago Peixoto committed
80
81
82
            if (v == graph_traits<Graph>::null_vertex())
                continue;

83
84
85
86
87
88
89
90
91
92
            // path priority queue
            vector<path_t> paths(1);
            vector<size_t> free_indexes;
            typedef double_priority_queue<size_t, path_cmp<path_t> > queue_t;
            queue_t queue = queue_t(path_cmp<path_t>(paths));

            get<0>(paths.back()).first = get<0>(paths.back()).second = 1;
            get<1>(paths.back()).insert(v);
            get<2>(paths.back()) = vertex_index[v];
            queue.push(0);
93

94
95
96
97
98
99
            t[v].resize(num_vertices(g));
            unchecked_vector_property_map<t_type, VertexIndex>
                sum_weight(vertex_index, num_vertices(g));

            size_t count = 1;
            while (!queue.empty())
Tiago Peixoto's avatar
Tiago Peixoto committed
100
            {
101
102
103
                size_t pi = queue.top();
                queue.pop_top();
                vertex_t w = vertex(get<2>(paths[pi]), g);
Tiago Peixoto's avatar
Tiago Peixoto committed
104

105
106
                typename graph_traits<Graph>::out_edge_iterator e, e_end;
                for (tie(e, e_end) = out_edges(w, g); e != e_end; ++e)
Tiago Peixoto's avatar
Tiago Peixoto committed
107
                {
108
109
110
                    vertex_t a = target(*e, g);
                    // no loops
                    if (get<1>(paths[pi]).find(a) == get<1>(paths[pi]).end())
Tiago Peixoto's avatar
Tiago Peixoto committed
111
                    {
112
113
114
115
116
                        // new path;  only follow non-zero paths
                        t_type old = (sum_weight[a] > 0) ?
                            t[v][a]/sum_weight[a] : 0;
                        if (c[*e] > 0 || (reversed &&
                                          get<1>(paths[pi]).size() == 1))
Tiago Peixoto's avatar
Tiago Peixoto committed
117
                        {
118
119
                            size_t npi;
                            if (free_indexes.empty())
120
                            {
121
122
123
124
125
126
127
128
                                paths.push_back(paths[pi]); // clone last path
                                npi = paths.size()-1;
                            }
                            else
                            {
                                npi = free_indexes.back();
                                free_indexes.pop_back();
                                paths[npi] = paths[pi];
129
                            }
130

131
132
                            path_t& np = paths[npi];
                            if (!reversed)
133
                            {
134
135
                                get<0>(np).second = get<0>(np).first;
                                get<0>(np).first *= c[*e];
136
137
138
                            }
                            else
                            {
139
140
141
                                if (get<1>(np).size() > 1)
                                    get<0>(np).second *= c[*e];
                                get<0>(np).first *= c[*e];
142
                            }
143
144
                            get<1>(np).insert(a);
                            get<2>(np) = vertex_index[a];
145

146
147
148
149
                            t[v][a] += get<0>(np).first*get<0>(np).second;
                            sum_weight[a] += get<0>(np).second;
                            queue.push(npi);
                            if (n_paths > 0 && queue.size() > n_paths)
150
                            {
151
152
153
                                size_t bi = queue.bottom();
                                queue.pop_bottom();
                                free_indexes.push_back(bi);
154
                            }
Tiago Peixoto's avatar
Tiago Peixoto committed
155
                        }
156
157
158
159
160
161
                        else
                        {
                            sum_weight[a] +=  get<0>(paths[pi]).first;
                        }
                        if (sum_weight[a] > 0)
                            delta += abs(old-t[v][a]/sum_weight[a]);
Tiago Peixoto's avatar
Tiago Peixoto committed
162
163
                    }
                }
164
                free_indexes.push_back(pi);
Tiago Peixoto's avatar
Tiago Peixoto committed
165

166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
                if ((count % N) == 0)
                {
                    if (delta < epsilon)
                        break;
                    else
                        delta = 0;
                }
                count++;
            }

            typename graph_traits<Graph>::vertex_iterator w, w_end;
            for (tie(w, w_end) = vertices(g); w != w_end; ++w)
            {
                if (sum_weight[*w] > 0)
                    t[v][*w] /= sum_weight[*w];
            }
Tiago Peixoto's avatar
Tiago Peixoto committed
182
183
184
185
186
187
188
        }
    }
};

}

#endif