williamr@2: // Copyright 2004-5 The Trustees of Indiana University.
williamr@2: // Copyright 2002 Brad King and Douglas Gregor
williamr@2: 
williamr@2: // Distributed under the Boost Software License, Version 1.0.
williamr@2: // (See accompanying file LICENSE_1_0.txt or copy at
williamr@2: // http://www.boost.org/LICENSE_1_0.txt)
williamr@2: 
williamr@2: //  Authors: Douglas Gregor
williamr@2: //           Andrew Lumsdaine
williamr@2: 
williamr@2: #ifndef BOOST_GRAPH_PAGE_RANK_HPP
williamr@2: #define BOOST_GRAPH_PAGE_RANK_HPP
williamr@2: 
williamr@2: #include <boost/property_map.hpp>
williamr@2: #include <boost/graph/graph_traits.hpp>
williamr@2: #include <boost/graph/properties.hpp>
williamr@2: #include <boost/graph/iteration_macros.hpp>
williamr@2: #include <vector>
williamr@2: 
williamr@2: namespace boost { namespace graph {
williamr@2: 
williamr@2: struct n_iterations
williamr@2: {
williamr@2:   explicit n_iterations(std::size_t n) : n(n) { }
williamr@2: 
williamr@2:   template<typename RankMap, typename Graph>
williamr@2:   bool 
williamr@2:   operator()(const RankMap&, const Graph&)
williamr@2:   {
williamr@2:     return n-- == 0;
williamr@2:   }
williamr@2: 
williamr@2:  private:
williamr@2:   std::size_t n;
williamr@2: };
williamr@2: 
williamr@2: namespace detail {
williamr@2:   template<typename Graph, typename RankMap, typename RankMap2>
williamr@2:   void page_rank_step(const Graph& g, RankMap from_rank, RankMap2 to_rank,
williamr@2:                       typename property_traits<RankMap>::value_type damping,
williamr@2:                       incidence_graph_tag)
williamr@2:   {
williamr@2:     typedef typename property_traits<RankMap>::value_type rank_type;
williamr@2: 
williamr@2:     // Set new rank maps 
williamr@2:     BGL_FORALL_VERTICES_T(v, g, Graph) put(to_rank, v, rank_type(1 - damping));
williamr@2: 
williamr@2:     BGL_FORALL_VERTICES_T(u, g, Graph) {
williamr@2:       rank_type u_rank_out = damping * get(from_rank, u) / out_degree(u, g);
williamr@2:       BGL_FORALL_ADJ_T(u, v, g, Graph)
williamr@2:         put(to_rank, v, get(to_rank, v) + u_rank_out);
williamr@2:     }
williamr@2:   }
williamr@2: 
williamr@2:   template<typename Graph, typename RankMap, typename RankMap2>
williamr@2:   void page_rank_step(const Graph& g, RankMap from_rank, RankMap2 to_rank,
williamr@2:                       typename property_traits<RankMap>::value_type damping,
williamr@2:                       bidirectional_graph_tag)
williamr@2:   {
williamr@2:     typedef typename property_traits<RankMap>::value_type damping_type;
williamr@2:     BGL_FORALL_VERTICES_T(v, g, Graph) {
williamr@2:       typename property_traits<RankMap>::value_type rank(0);
williamr@2:       BGL_FORALL_INEDGES_T(v, e, g, Graph)
williamr@2:         rank += get(from_rank, source(e, g)) / out_degree(source(e, g), g);
williamr@2:       put(to_rank, v, (damping_type(1) - damping) + damping * rank);
williamr@2:     }
williamr@2:   }
williamr@2: } // end namespace detail
williamr@2: 
williamr@2: template<typename Graph, typename RankMap, typename Done, typename RankMap2>
williamr@2: void
williamr@2: page_rank(const Graph& g, RankMap rank_map, Done done, 
williamr@2:           typename property_traits<RankMap>::value_type damping,
williamr@2:           typename graph_traits<Graph>::vertices_size_type n,
williamr@2:           RankMap2 rank_map2)
williamr@2: {
williamr@2:   typedef typename property_traits<RankMap>::value_type rank_type;
williamr@2: 
williamr@2:   rank_type initial_rank = rank_type(rank_type(1) / n);
williamr@2:   BGL_FORALL_VERTICES_T(v, g, Graph) put(rank_map, v, initial_rank);
williamr@2: 
williamr@2:   bool to_map_2 = true;
williamr@2:   while ((to_map_2 && !done(rank_map, g)) ||
williamr@2:          (!to_map_2 && !done(rank_map2, g))) {
williamr@2:     typedef typename graph_traits<Graph>::traversal_category category;
williamr@2: 
williamr@2:     if (to_map_2) {
williamr@2:       detail::page_rank_step(g, rank_map, rank_map2, damping, category());
williamr@2:     } else {
williamr@2:       detail::page_rank_step(g, rank_map2, rank_map, damping, category());
williamr@2:     }
williamr@2:     to_map_2 = !to_map_2;
williamr@2:   }
williamr@2: 
williamr@2:   if (!to_map_2) {
williamr@2:     BGL_FORALL_VERTICES_T(v, g, Graph) put(rank_map, v, get(rank_map2, v));
williamr@2:   }
williamr@2: }
williamr@2: 
williamr@2: template<typename Graph, typename RankMap, typename Done>
williamr@2: void
williamr@2: page_rank(const Graph& g, RankMap rank_map, Done done, 
williamr@2:           typename property_traits<RankMap>::value_type damping,
williamr@2:           typename graph_traits<Graph>::vertices_size_type n)
williamr@2: {
williamr@2:   typedef typename property_traits<RankMap>::value_type rank_type;
williamr@2: 
williamr@2:   std::vector<rank_type> ranks2(num_vertices(g));
williamr@2:   page_rank(g, rank_map, done, damping, n,
williamr@2:             make_iterator_property_map(ranks2.begin(), get(vertex_index, g)));
williamr@2: }
williamr@2: 
williamr@2: template<typename Graph, typename RankMap, typename Done>
williamr@2: inline void
williamr@2: page_rank(const Graph& g, RankMap rank_map, Done done, 
williamr@2:           typename property_traits<RankMap>::value_type damping = 0.85)
williamr@2: {
williamr@2:   page_rank(g, rank_map, done, damping, num_vertices(g));
williamr@2: }
williamr@2: 
williamr@2: template<typename Graph, typename RankMap>
williamr@2: inline void
williamr@2: page_rank(const Graph& g, RankMap rank_map)
williamr@2: {
williamr@2:   page_rank(g, rank_map, n_iterations(20));
williamr@2: }
williamr@2: 
williamr@2: // TBD: this could be _much_ more efficient, using a queue to store
williamr@2: // the vertices that should be reprocessed and keeping track of which
williamr@2: // vertices are in the queue with a property map. Baah, this only
williamr@2: // applies when we have a bidirectional graph.
williamr@2: template<typename MutableGraph>
williamr@2: void
williamr@2: remove_dangling_links(MutableGraph& g)
williamr@2: {
williamr@2:   typename graph_traits<MutableGraph>::vertices_size_type old_n;
williamr@2:   do {
williamr@2:     old_n = num_vertices(g);
williamr@2: 
williamr@2:     typename graph_traits<MutableGraph>::vertex_iterator vi, vi_end;
williamr@2:     for (tie(vi, vi_end) = vertices(g); vi != vi_end; /* in loop */) {
williamr@2:       typename graph_traits<MutableGraph>::vertex_descriptor v = *vi++;
williamr@2:       if (out_degree(v, g) == 0) {
williamr@2:         clear_vertex(v, g);
williamr@2:         remove_vertex(v, g);
williamr@2:       }
williamr@2:     }
williamr@2:   } while (num_vertices(g) < old_n);
williamr@2: }
williamr@2: 
williamr@2: } } // end namespace boost::graph
williamr@2: 
williamr@2: #endif // BOOST_GRAPH_PAGE_RANK_HPP