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