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 <vector>
20
21 namespace boost { namespace graph {
22
23 struct n_iterations
24 {
n_iterationsboost::graph::n_iterations25 explicit n_iterations(std::size_t n) : n(n) { }
26
27 template<typename RankMap, typename Graph>
28 bool
operator ()boost::graph::n_iterations29 operator()(const RankMap&, const Graph&)
30 {
31 return n-- == 0;
32 }
33
34 private:
35 std::size_t n;
36 };
37
38 namespace detail {
39 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)40 void page_rank_step(const Graph& g, RankMap from_rank, RankMap2 to_rank,
41 typename property_traits<RankMap>::value_type damping,
42 incidence_graph_tag)
43 {
44 typedef typename property_traits<RankMap>::value_type rank_type;
45
46 // Set new rank maps
47 BGL_FORALL_VERTICES_T(v, g, Graph) put(to_rank, v, rank_type(1 - damping));
48
49 BGL_FORALL_VERTICES_T(u, g, Graph) {
50 rank_type u_rank_out = damping * get(from_rank, u) / out_degree(u, g);
51 BGL_FORALL_ADJ_T(u, v, g, Graph)
52 put(to_rank, v, get(to_rank, v) + u_rank_out);
53 }
54 }
55
56 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)57 void page_rank_step(const Graph& g, RankMap from_rank, RankMap2 to_rank,
58 typename property_traits<RankMap>::value_type damping,
59 bidirectional_graph_tag)
60 {
61 typedef typename property_traits<RankMap>::value_type damping_type;
62 BGL_FORALL_VERTICES_T(v, g, Graph) {
63 typename property_traits<RankMap>::value_type rank(0);
64 BGL_FORALL_INEDGES_T(v, e, g, Graph)
65 rank += get(from_rank, source(e, g)) / out_degree(source(e, g), g);
66 put(to_rank, v, (damping_type(1) - damping) + damping * rank);
67 }
68 }
69 } // end namespace detail
70
71 template<typename Graph, typename RankMap, typename Done, typename RankMap2>
72 void
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))73 page_rank(const Graph& g, RankMap rank_map, Done done,
74 typename property_traits<RankMap>::value_type damping,
75 typename graph_traits<Graph>::vertices_size_type n,
76 RankMap2 rank_map2
77 BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, vertex_list_graph_tag))
78 {
79 typedef typename property_traits<RankMap>::value_type rank_type;
80
81 rank_type initial_rank = rank_type(rank_type(1) / n);
82 BGL_FORALL_VERTICES_T(v, g, Graph) put(rank_map, v, initial_rank);
83
84 bool to_map_2 = true;
85 while ((to_map_2 && !done(rank_map, g)) ||
86 (!to_map_2 && !done(rank_map2, g))) {
87 typedef typename graph_traits<Graph>::traversal_category category;
88
89 if (to_map_2) {
90 detail::page_rank_step(g, rank_map, rank_map2, damping, category());
91 } else {
92 detail::page_rank_step(g, rank_map2, rank_map, damping, category());
93 }
94 to_map_2 = !to_map_2;
95 }
96
97 if (!to_map_2) {
98 BGL_FORALL_VERTICES_T(v, g, Graph) put(rank_map, v, get(rank_map2, v));
99 }
100 }
101
102 template<typename Graph, typename RankMap, typename Done>
103 void
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)104 page_rank(const Graph& g, RankMap rank_map, Done done,
105 typename property_traits<RankMap>::value_type damping,
106 typename graph_traits<Graph>::vertices_size_type n)
107 {
108 typedef typename property_traits<RankMap>::value_type rank_type;
109
110 std::vector<rank_type> ranks2(num_vertices(g));
111 page_rank(g, rank_map, done, damping, n,
112 make_iterator_property_map(ranks2.begin(), get(vertex_index, g)));
113 }
114
115 template<typename Graph, typename RankMap, typename Done>
116 inline void
page_rank(const Graph & g,RankMap rank_map,Done done,typename property_traits<RankMap>::value_type damping=0.85)117 page_rank(const Graph& g, RankMap rank_map, Done done,
118 typename property_traits<RankMap>::value_type damping = 0.85)
119 {
120 page_rank(g, rank_map, done, damping, num_vertices(g));
121 }
122
123 template<typename Graph, typename RankMap>
124 inline void
page_rank(const Graph & g,RankMap rank_map)125 page_rank(const Graph& g, RankMap rank_map)
126 {
127 page_rank(g, rank_map, n_iterations(20));
128 }
129
130 // TBD: this could be _much_ more efficient, using a queue to store
131 // the vertices that should be reprocessed and keeping track of which
132 // vertices are in the queue with a property map. Baah, this only
133 // applies when we have a bidirectional graph.
134 template<typename MutableGraph>
135 void
remove_dangling_links(MutableGraph & g BOOST_GRAPH_ENABLE_IF_MODELS_PARM (MutableGraph,vertex_list_graph_tag))136 remove_dangling_links(MutableGraph& g
137 BOOST_GRAPH_ENABLE_IF_MODELS_PARM(MutableGraph,
138 vertex_list_graph_tag))
139 {
140 typename graph_traits<MutableGraph>::vertices_size_type old_n;
141 do {
142 old_n = num_vertices(g);
143
144 typename graph_traits<MutableGraph>::vertex_iterator vi, vi_end;
145 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; /* in loop */) {
146 typename graph_traits<MutableGraph>::vertex_descriptor v = *vi++;
147 if (out_degree(v, g) == 0) {
148 clear_vertex(v, g);
149 remove_vertex(v, g);
150 }
151 }
152 } while (num_vertices(g) < old_n);
153 }
154
155 } } // end namespace boost::graph
156
157 #ifdef BOOST_GRAPH_USE_MPI
158 # include <boost/graph/distributed/page_rank.hpp>
159 #endif
160
161 #endif // BOOST_GRAPH_PAGE_RANK_HPP
162