graph_absolute_trust.hh 7.04 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
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)
    {
51
        if (get<0>(_paths[a]).second == get<0>(_paths[b]).second)
52
            return get<1>(_paths[a]).size() > get<1>(_paths[b]).size();
53
        return get<0>(_paths[a]).second < get<0>(_paths[b]).second;
54
55
    }
};
Tiago Peixoto's avatar
Tiago Peixoto committed
56

57
struct get_absolute_trust
Tiago Peixoto's avatar
Tiago Peixoto committed
58
{
59
60
61
62
    get_absolute_trust(int64_t source, double gamma, size_t n_paths,
                       bool reversed)
        : source(source), gamma(gamma), n_paths(n_paths), reversed(reversed) {}

63
    template <class Graph, class VertexIndex, class EdgeIndex, class TrustMap,
Tiago Peixoto's avatar
Tiago Peixoto committed
64
              class InferredTrustMap>
65
    void operator()(Graph& g, VertexIndex vertex_index, EdgeIndex edge_index,
66
                    size_t max_edge_index, TrustMap c, InferredTrustMap t) const
Tiago Peixoto's avatar
Tiago Peixoto committed
67
    {
68
        typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
69
        typedef typename graph_traits<Graph>::edge_descriptor edge_t;
Tiago Peixoto's avatar
Tiago Peixoto committed
70
        typedef typename property_traits<TrustMap>::value_type c_type;
71
72
        typedef typename property_traits<InferredTrustMap>::value_type::
            value_type t_type;
Tiago Peixoto's avatar
Tiago Peixoto committed
73

74
75
76
        // the path type: the first value is the (trust,weight) pair, the second
        // the set of vertices in the path and the third is the list of edges,
        // in the path sequence.
77
        typedef tuple<pair<t_type, t_type>, tr1::unordered_set<vertex_t>,
78
                      vector<edge_t> > path_t;
Tiago Peixoto's avatar
Tiago Peixoto committed
79

80
        int i, N = (source == -1) ? num_vertices(g) : source + 1;
81
        #pragma omp parallel for default(shared) private(i) schedule(dynamic)
82
        for (i= (source == -1) ? 0 : source; i < N; ++i)
Tiago Peixoto's avatar
Tiago Peixoto committed
83
        {
84
            vertex_t v = vertex(i, g);
85
            t[v].resize(num_vertices(g));
Tiago Peixoto's avatar
Tiago Peixoto committed
86

87
88
89
90
91
92
93
            // path priority queue
            vector<path_t> paths(1);
            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);
            queue.push(0);
94

95
            // this is the queue with paths with maximum weights
96
97
            queue_t final_queue = queue_t(path_cmp<path_t>(paths));

98
99
100
            // sum of weights that lead to a given vertex
            unchecked_vector_property_map<t_type, VertexIndex>
                weight_sum(vertex_index, num_vertices(g));
101
102

            while (!queue.empty())
Tiago Peixoto's avatar
Tiago Peixoto committed
103
            {
104
105
                size_t pi = queue.top();
                queue.pop_top();
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
                vertex_t w;

                // push queue top into final queue
                if (get<2>(paths[pi]).size() > 0)
                {
                    w = target(get<2>(paths[pi]).back(), g);
                    final_queue.push(pi);
                }
                else
                {
                    w = v; // the first path
                }

                // if maximum size is reached, remove the bottom
                if ((n_paths > 0) && (final_queue.size() > n_paths))
                {
                    size_t bi = final_queue.bottom();
                    final_queue.pop_bottom();

125
                    // do not augment if the path is the removed bottom
126
127
128
129
130
                    if (bi == pi)
                        continue;
                }

                // augment paths and put them in the queue
131
132
                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
133
                {
134
135
136
                    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
137
                    {
138
139
140
                        size_t npi;
                        paths.push_back(paths[pi]); // clone last path
                        npi = paths.size()-1;
141

142
                        path_t& np = paths[npi]; // new path
143

144
                        if (!reversed)
145
                        {
146
147
                            // path weight
                            get<0>(np).second = get<0>(np).first;
Tiago Peixoto's avatar
Tiago Peixoto committed
148

149
150
151
152
                            // path value
                            get<0>(np).first *= c[*e];
                        }
                        else
153
                        {
154
155
156
                            if (get<1>(np).size() > 1)
                                get<0>(np).second *= c[*e];
                            get<0>(np).first *= c[*e];
157
                        }
158
159
160
161

                        t_type w = pow(get<0>(np).second, gamma);
                        weight_sum[a] += w;
                        t[v][vertex_index[a]] += w * get<0>(np).first;
162
163
164
165
166
167
168
169
170
171
172
173
174

                        get<1>(np).insert(a);
                        get<2>(np).push_back(*e);

                        // keep following paths only if there is a chance
                        // they will make it into the final queue
                        if ((n_paths > 0 && final_queue.size() < n_paths) ||
                            (final_queue.size() == 0 ||
                             (get<0>(np).second >=
                              get<0>(paths[final_queue.bottom()]).second)))
                            queue.push(npi);
                        else
                            paths.pop_back();
175
                    }
176
177
178
                }
            }

179
180
181
182
            int j, N = num_vertices(g);
            #pragma omp parallel for default(shared) private(j) \
                schedule(dynamic)
            for (j = 0; j < N; ++j)
183
            {
184
                vertex_t w = vertex(j, g);
185
186
187
                if (w == graph_traits<Graph>::null_vertex())
                    continue;
                if (weight_sum[w] > 0)
188
                    t[v][w] /= weight_sum[w];
189
            }
Tiago Peixoto's avatar
Tiago Peixoto committed
190
191
        }
    }
192

193
194
195
196
    int64_t source;
    double gamma;
    size_t n_paths;
    bool reversed;
Tiago Peixoto's avatar
Tiago Peixoto committed
197
198
199
200
201
};

}

#endif