// graph-tool -- a general graph modification and manipulation thingy // // Copyright (C) 2007-2012 Tiago de Paula Peixoto // // 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 . #ifndef GRAPH_TRUST_TRANSITIVITY_HH #define GRAPH_TRUST_TRANSITIVITY_HH #include "graph.hh" #include "graph_filtering.hh" #include "graph_util.hh" #include #include #include namespace graph_tool { using namespace std; using namespace boost; struct stop_search {}; // exception to be thrown to stop search template class source_counter: public boost::dijkstra_visitor { public: source_counter(SourceMap source_map, WeightMap weight_map, size_t n_sources) : _source_map(source_map), _weight_map(weight_map), _n_sources(n_sources) {} template void examine_vertex(typename graph_traits::vertex_descriptor u, Graph& g) { // stop if all sources are found if (_source_map[u]) { _n_sources--; if (_n_sources == 0) throw stop_search(); } } private: SourceMap _source_map; WeightMap _weight_map; size_t _n_sources; }; struct dist_compare { template bool operator()(const Type1& d1, const Type2& d2) const { return d1 > d2; // we want trust paths with _maximum_ "distance" } }; struct dist_combine { template DistType operator()(const DistType& d, const WeightType& w) const { return d*w; } }; // predicate to filter a single vertex from the graph struct filter_vertex_pred { filter_vertex_pred() {} filter_vertex_pred(size_t v): _v(v) {} template bool operator()(const Vertex& v) const { return v != _v; } size_t _v; }; struct get_trust_transitivity { template void operator()(Graph& g, VertexIndex vertex_index, EdgeIndex edge_index, size_t max_edge_index, int64_t source, int64_t target, TrustMap c, InferredTrustMap t) const { typedef typename graph_traits::vertex_descriptor vertex_t; typedef typename graph_traits::edge_descriptor edge_t; typedef typename property_traits::value_type c_type; typedef typename property_traits::value_type::value_type t_type; int i, N = num_vertices(g); #pragma omp parallel for default(shared) private(i) schedule(dynamic) for (i = 0; i < N; ++i) t[vertex(i, g)].resize((source == -1 && target == -1) ? N : 1); N = (target == -1) ? num_vertices(g) : target + 1; #pragma omp parallel for default(shared) private(i) schedule(dynamic) for (i = (target == -1) ? 0 : target; i < N; ++i) { vertex_t tgt = vertex(i, g); // mark the sources typedef unchecked_vector_property_map source_map_t; source_map_t source_map(vertex_index, num_vertices(g)); typename in_edge_iteratorS::type e, e_end; for (tie(e, e_end) = in_edge_iteratorS::get_edges(tgt, g); e != e_end; ++e) source_map[boost::source(*e,g)] = true; // filter vertex w out of the graph typedef filtered_graph fg_t; fg_t fg(g, boost::keep_all(), filter_vertex_pred(tgt)); // distance map (target weight map) typedef unchecked_vector_property_map dist_map_t; dist_map_t dist_map(vertex_index, num_vertices(g)); if (source != -1) { vertex_t src = vertex(source, g); // compute the targets weights try { size_t k = in_degreeS()(tgt, g); source_counter visitor(source_map, dist_map, k); dijkstra_shortest_paths(fg, src, weight_map(c). vertex_index_map(vertex_index). distance_map(dist_map). distance_compare(dist_compare()). distance_combine(dist_combine()). distance_inf(t_type(0)). distance_zero(t_type(1)). visitor(visitor)); } catch (const stop_search&) {} // compute the target's trust t_type sum_w = 0, avg = 0; for (tie(e, e_end) = in_edge_iteratorS::get_edges(tgt, g); e != e_end; ++e) { t_type weight = dist_map[boost::source(*e,g)]; sum_w += weight; avg += c[*e]*weight*weight; } if (sum_w > 0) t[tgt][0] = avg/sum_w; if (tgt == src) t[tgt][0] = 1.0; } else { typedef typename mpl::if_::type, reverse_graph, fg_t>::type rg_t; rg_t rg(fg); dist_map_t sum_w(vertex_index, num_vertices(g)); int j, N2 = num_vertices(g); for (tie(e, e_end) = in_edge_iteratorS::get_edges(tgt, g); e != e_end; ++e) { // compute the weights to all sources dijkstra_shortest_paths (rg, boost::source(*e, g), weight_map(c). vertex_index_map(vertex_index). distance_map(dist_map). distance_compare(dist_compare()). distance_combine(dist_combine()). distance_inf(t_type(0)). distance_zero(t_type(1))); #pragma omp parallel for default(shared) private(j) \ schedule(dynamic) for (j = 0; j < N2; ++j) { vertex_t src = vertex(j, g); t_type weight = dist_map[src]; sum_w[src] += weight; size_t tidx = (target == -1) ? vertex_index[tgt] : 0; t[src][tidx] += c[*e]*weight*weight; } } #pragma omp parallel for default(shared) private(j) \ schedule(dynamic) for (j = 0; j < N2; ++j) { vertex_t src = vertex(j, g); size_t tidx = (target == -1) ? vertex_index[tgt] : 0; if (sum_w[src] > 0) t[src][tidx] /= sum_w[src]; if (src == tgt) t[src][tidx] = 1.0; } } } } }; } #endif