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