1 // Copyright 2004-5 The Trustees of Indiana University.
2 // Copyright 2002 Brad King and Douglas Gregor
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)
8 // Authors: Douglas Gregor
11 #ifndef BOOST_GRAPH_PAGE_RANK_HPP
12 #define BOOST_GRAPH_PAGE_RANK_HPP
14 #include <boost/property_map.hpp>
15 #include <boost/graph/graph_traits.hpp>
16 #include <boost/graph/properties.hpp>
17 #include <boost/graph/iteration_macros.hpp>
20 namespace boost { namespace graph {
24 explicit n_iterations(std::size_t n) : n(n) { }
26 template<typename RankMap, typename Graph>
28 operator()(const RankMap&, const Graph&)
38 template<typename Graph, typename RankMap, typename RankMap2>
39 void page_rank_step(const Graph& g, RankMap from_rank, RankMap2 to_rank,
40 typename property_traits<RankMap>::value_type damping,
43 typedef typename property_traits<RankMap>::value_type rank_type;
46 BGL_FORALL_VERTICES_T(v, g, Graph) put(to_rank, v, rank_type(1 - damping));
48 BGL_FORALL_VERTICES_T(u, g, Graph) {
49 rank_type u_rank_out = damping * get(from_rank, u) / out_degree(u, g);
50 BGL_FORALL_ADJ_T(u, v, g, Graph)
51 put(to_rank, v, get(to_rank, v) + u_rank_out);
55 template<typename Graph, typename RankMap, typename RankMap2>
56 void page_rank_step(const Graph& g, RankMap from_rank, RankMap2 to_rank,
57 typename property_traits<RankMap>::value_type damping,
58 bidirectional_graph_tag)
60 typedef typename property_traits<RankMap>::value_type damping_type;
61 BGL_FORALL_VERTICES_T(v, g, Graph) {
62 typename property_traits<RankMap>::value_type rank(0);
63 BGL_FORALL_INEDGES_T(v, e, g, Graph)
64 rank += get(from_rank, source(e, g)) / out_degree(source(e, g), g);
65 put(to_rank, v, (damping_type(1) - damping) + damping * rank);
68 } // end namespace detail
70 template<typename Graph, typename RankMap, typename Done, typename RankMap2>
72 page_rank(const Graph& g, RankMap rank_map, Done done,
73 typename property_traits<RankMap>::value_type damping,
74 typename graph_traits<Graph>::vertices_size_type n,
77 typedef typename property_traits<RankMap>::value_type rank_type;
79 rank_type initial_rank = rank_type(rank_type(1) / n);
80 BGL_FORALL_VERTICES_T(v, g, Graph) put(rank_map, v, initial_rank);
83 while ((to_map_2 && !done(rank_map, g)) ||
84 (!to_map_2 && !done(rank_map2, g))) {
85 typedef typename graph_traits<Graph>::traversal_category category;
88 detail::page_rank_step(g, rank_map, rank_map2, damping, category());
90 detail::page_rank_step(g, rank_map2, rank_map, damping, category());
96 BGL_FORALL_VERTICES_T(v, g, Graph) put(rank_map, v, get(rank_map2, v));
100 template<typename Graph, typename RankMap, typename Done>
102 page_rank(const Graph& g, RankMap rank_map, Done done,
103 typename property_traits<RankMap>::value_type damping,
104 typename graph_traits<Graph>::vertices_size_type n)
106 typedef typename property_traits<RankMap>::value_type rank_type;
108 std::vector<rank_type> ranks2(num_vertices(g));
109 page_rank(g, rank_map, done, damping, n,
110 make_iterator_property_map(ranks2.begin(), get(vertex_index, g)));
113 template<typename Graph, typename RankMap, typename Done>
115 page_rank(const Graph& g, RankMap rank_map, Done done,
116 typename property_traits<RankMap>::value_type damping = 0.85)
118 page_rank(g, rank_map, done, damping, num_vertices(g));
121 template<typename Graph, typename RankMap>
123 page_rank(const Graph& g, RankMap rank_map)
125 page_rank(g, rank_map, n_iterations(20));
128 // TBD: this could be _much_ more efficient, using a queue to store
129 // the vertices that should be reprocessed and keeping track of which
130 // vertices are in the queue with a property map. Baah, this only
131 // applies when we have a bidirectional graph.
132 template<typename MutableGraph>
134 remove_dangling_links(MutableGraph& g)
136 typename graph_traits<MutableGraph>::vertices_size_type old_n;
138 old_n = num_vertices(g);
140 typename graph_traits<MutableGraph>::vertex_iterator vi, vi_end;
141 for (tie(vi, vi_end) = vertices(g); vi != vi_end; /* in loop */) {
142 typename graph_traits<MutableGraph>::vertex_descriptor v = *vi++;
143 if (out_degree(v, g) == 0) {
148 } while (num_vertices(g) < old_n);
151 } } // end namespace boost::graph
153 #endif // BOOST_GRAPH_PAGE_RANK_HPP