1 // Copyright 2004-5 The Trustees of Indiana University. 2 // Copyright 2002 Brad King and Douglas Gregor 3 4 // Distributed under the Boost Software License, Version 1.0. 5 // (See accompanying file LICENSE_1_0.txt or copy at 6 // http://www.boost.org/LICENSE_1_0.txt) 7 8 // Authors: Douglas Gregor 9 // Andrew Lumsdaine 10 11 #ifndef BOOST_GRAPH_PAGE_RANK_HPP 12 #define BOOST_GRAPH_PAGE_RANK_HPP 13 14 #include <boost/property_map/property_map.hpp> 15 #include <boost/graph/graph_traits.hpp> 16 #include <boost/graph/properties.hpp> 17 #include <boost/graph/iteration_macros.hpp> 18 #include <boost/graph/overloading.hpp> 19 #include <boost/graph/detail/mpi_include.hpp> 20 #include <vector> 21 22 namespace boost 23 { 24 namespace graph 25 { 26 27 struct n_iterations 28 { n_iterationsboost::graph::n_iterations29 explicit n_iterations(std::size_t n) : n(n) {} 30 31 template < typename RankMap, typename Graph > operator ()boost::graph::n_iterations32 bool operator()(const RankMap&, const Graph&) 33 { 34 return n-- == 0; 35 } 36 37 private: 38 std::size_t n; 39 }; 40 41 namespace detail 42 { 43 template < typename Graph, typename RankMap, typename RankMap2 > page_rank_step(const Graph & g,RankMap from_rank,RankMap2 to_rank,typename property_traits<RankMap>::value_type damping,incidence_graph_tag)44 void page_rank_step(const Graph& g, RankMap from_rank, RankMap2 to_rank, 45 typename property_traits< RankMap >::value_type damping, 46 incidence_graph_tag) 47 { 48 typedef typename property_traits< RankMap >::value_type rank_type; 49 50 // Set new rank maps 51 BGL_FORALL_VERTICES_T(v, g, Graph) 52 put(to_rank, v, rank_type(1 - damping)); 53 54 BGL_FORALL_VERTICES_T(u, g, Graph) 55 { 56 rank_type u_rank_out 57 = damping * get(from_rank, u) / out_degree(u, g); 58 BGL_FORALL_ADJ_T(u, v, g, Graph) 59 put(to_rank, v, get(to_rank, v) + u_rank_out); 60 } 61 } 62 63 template < typename Graph, typename RankMap, typename RankMap2 > page_rank_step(const Graph & g,RankMap from_rank,RankMap2 to_rank,typename property_traits<RankMap>::value_type damping,bidirectional_graph_tag)64 void page_rank_step(const Graph& g, RankMap from_rank, RankMap2 to_rank, 65 typename property_traits< RankMap >::value_type damping, 66 bidirectional_graph_tag) 67 { 68 typedef 69 typename property_traits< RankMap >::value_type damping_type; 70 BGL_FORALL_VERTICES_T(v, g, Graph) 71 { 72 typename property_traits< RankMap >::value_type rank(0); 73 BGL_FORALL_INEDGES_T(v, e, g, Graph) 74 rank += get(from_rank, source(e, g)) 75 / out_degree(source(e, g), g); 76 put(to_rank, v, (damping_type(1) - damping) + damping * rank); 77 } 78 } 79 } // end namespace detail 80 81 template < typename Graph, typename RankMap, typename Done, 82 typename RankMap2 > page_rank(const Graph & g,RankMap rank_map,Done done,typename property_traits<RankMap>::value_type damping,typename graph_traits<Graph>::vertices_size_type n,RankMap2 rank_map2 BOOST_GRAPH_ENABLE_IF_MODELS_PARM (Graph,vertex_list_graph_tag))83 void page_rank(const Graph& g, RankMap rank_map, Done done, 84 typename property_traits< RankMap >::value_type damping, 85 typename graph_traits< Graph >::vertices_size_type n, 86 RankMap2 rank_map2 BOOST_GRAPH_ENABLE_IF_MODELS_PARM( 87 Graph, vertex_list_graph_tag)) 88 { 89 typedef typename property_traits< RankMap >::value_type rank_type; 90 91 rank_type initial_rank = rank_type(rank_type(1) / n); 92 BGL_FORALL_VERTICES_T(v, g, Graph) put(rank_map, v, initial_rank); 93 94 bool to_map_2 = true; 95 while ((to_map_2 && !done(rank_map, g)) 96 || (!to_map_2 && !done(rank_map2, g))) 97 { 98 typedef typename graph_traits< Graph >::traversal_category category; 99 100 if (to_map_2) 101 { 102 detail::page_rank_step( 103 g, rank_map, rank_map2, damping, category()); 104 } 105 else 106 { 107 detail::page_rank_step( 108 g, rank_map2, rank_map, damping, category()); 109 } 110 to_map_2 = !to_map_2; 111 } 112 113 if (!to_map_2) 114 { 115 BGL_FORALL_VERTICES_T(v, g, Graph) 116 put(rank_map, v, get(rank_map2, v)); 117 } 118 } 119 120 template < typename Graph, typename RankMap, typename Done > page_rank(const Graph & g,RankMap rank_map,Done done,typename property_traits<RankMap>::value_type damping,typename graph_traits<Graph>::vertices_size_type n)121 void page_rank(const Graph& g, RankMap rank_map, Done done, 122 typename property_traits< RankMap >::value_type damping, 123 typename graph_traits< Graph >::vertices_size_type n) 124 { 125 typedef typename property_traits< RankMap >::value_type rank_type; 126 127 std::vector< rank_type > ranks2(num_vertices(g)); 128 page_rank(g, rank_map, done, damping, n, 129 make_iterator_property_map(ranks2.begin(), get(vertex_index, g))); 130 } 131 132 template < typename Graph, typename RankMap, typename Done > page_rank(const Graph & g,RankMap rank_map,Done done,typename property_traits<RankMap>::value_type damping=0.85)133 inline void page_rank(const Graph& g, RankMap rank_map, Done done, 134 typename property_traits< RankMap >::value_type damping = 0.85) 135 { 136 page_rank(g, rank_map, done, damping, num_vertices(g)); 137 } 138 139 template < typename Graph, typename RankMap > page_rank(const Graph & g,RankMap rank_map)140 inline void page_rank(const Graph& g, RankMap rank_map) 141 { 142 page_rank(g, rank_map, n_iterations(20)); 143 } 144 145 // TBD: this could be _much_ more efficient, using a queue to store 146 // the vertices that should be reprocessed and keeping track of which 147 // vertices are in the queue with a property map. Baah, this only 148 // applies when we have a bidirectional graph. 149 template < typename MutableGraph > remove_dangling_links(MutableGraph & g BOOST_GRAPH_ENABLE_IF_MODELS_PARM (MutableGraph,vertex_list_graph_tag))150 void remove_dangling_links( 151 MutableGraph& g BOOST_GRAPH_ENABLE_IF_MODELS_PARM( 152 MutableGraph, vertex_list_graph_tag)) 153 { 154 typename graph_traits< MutableGraph >::vertices_size_type old_n; 155 do 156 { 157 old_n = num_vertices(g); 158 159 typename graph_traits< MutableGraph >::vertex_iterator vi, vi_end; 160 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; 161 /* in loop */) 162 { 163 typename graph_traits< MutableGraph >::vertex_descriptor v 164 = *vi++; 165 if (out_degree(v, g) == 0) 166 { 167 clear_vertex(v, g); 168 remove_vertex(v, g); 169 } 170 } 171 } while (num_vertices(g) < old_n); 172 } 173 174 } 175 } // end namespace boost::graph 176 177 #include BOOST_GRAPH_MPI_INCLUDE(< boost / graph / distributed / page_rank.hpp >) 178 179 #endif // BOOST_GRAPH_PAGE_RANK_HPP 180