// Copyright 2004-5 The Trustees of Indiana University.

 // Copyright 2002 Brad King and Douglas Gregor

 // Distributed under the Boost Software License, Version 1.0.

 // (See accompanying file LICENSE_1_0.txt or copy at

 // http://www.boost.org/LICENSE_1_0.txt)

 //  Authors: Douglas Gregor

 //           Andrew Lumsdaine

 #ifndef BOOST_GRAPH_PAGE_RANK_HPP

 #define BOOST_GRAPH_PAGE_RANK_HPP

 #include <boost/property_map.hpp>

 #include <boost/graph/graph_traits.hpp>

 #include <boost/graph/properties.hpp>

 #include <boost/graph/iteration_macros.hpp>

 #include <vector>

 namespace boost { namespace graph {

 struct n_iterations

 {

   explicit n_iterations(std::size_t n) : n(n) { }

   template<typename RankMap, typename Graph>

   bool 

   operator()(const RankMap&, const Graph&)

   {

     return n-- == 0;

   }

  private:

   std::size_t n;

 };

 namespace detail {

   template<typename Graph, typename RankMap, typename RankMap2>

   void page_rank_step(const Graph& g, RankMap from_rank, RankMap2 to_rank,

                       typename property_traits<RankMap>::value_type damping,

                       incidence_graph_tag)

   {

     typedef typename property_traits<RankMap>::value_type rank_type;

     // Set new rank maps 

     BGL_FORALL_VERTICES_T(v, g, Graph) put(to_rank, v, rank_type(1 - damping));

     BGL_FORALL_VERTICES_T(u, g, Graph) {

       rank_type u_rank_out = damping * get(from_rank, u) / out_degree(u, g);

       BGL_FORALL_ADJ_T(u, v, g, Graph)

         put(to_rank, v, get(to_rank, v) + u_rank_out);

     }

   }

   template<typename Graph, typename RankMap, typename RankMap2>

   void page_rank_step(const Graph& g, RankMap from_rank, RankMap2 to_rank,

                       typename property_traits<RankMap>::value_type damping,

                       bidirectional_graph_tag)

   {

     typedef typename property_traits<RankMap>::value_type damping_type;

     BGL_FORALL_VERTICES_T(v, g, Graph) {

       typename property_traits<RankMap>::value_type rank(0);

       BGL_FORALL_INEDGES_T(v, e, g, Graph)

         rank += get(from_rank, source(e, g)) / out_degree(source(e, g), g);

       put(to_rank, v, (damping_type(1) - damping) + damping * rank);

     }

   }

 } // end namespace detail

 template<typename Graph, typename RankMap, typename Done, typename RankMap2>

 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)

 {

   typedef typename property_traits<RankMap>::value_type rank_type;

   rank_type initial_rank = rank_type(rank_type(1) / n);

   BGL_FORALL_VERTICES_T(v, g, Graph) put(rank_map, v, initial_rank);

   bool to_map_2 = true;

   while ((to_map_2 && !done(rank_map, g)) ||

          (!to_map_2 && !done(rank_map2, g))) {

     typedef typename graph_traits<Graph>::traversal_category category;

     if (to_map_2) {

       detail::page_rank_step(g, rank_map, rank_map2, damping, category());

     } else {

       detail::page_rank_step(g, rank_map2, rank_map, damping, category());

     }

     to_map_2 = !to_map_2;

   }

   if (!to_map_2) {

     BGL_FORALL_VERTICES_T(v, g, Graph) put(rank_map, v, get(rank_map2, v));

   }

 }

 template<typename Graph, typename RankMap, typename Done>

 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)

 {

   typedef typename property_traits<RankMap>::value_type rank_type;

   std::vector<rank_type> ranks2(num_vertices(g));

   page_rank(g, rank_map, done, damping, n,

             make_iterator_property_map(ranks2.begin(), get(vertex_index, g)));

 }

 template<typename Graph, typename RankMap, typename Done>

 inline void

 page_rank(const Graph& g, RankMap rank_map, Done done, 

           typename property_traits<RankMap>::value_type damping = 0.85)

 {

   page_rank(g, rank_map, done, damping, num_vertices(g));

 }

 template<typename Graph, typename RankMap>

 inline void

 page_rank(const Graph& g, RankMap rank_map)

 {

   page_rank(g, rank_map, n_iterations(20));

 }

 // TBD: this could be _much_ more efficient, using a queue to store

 // the vertices that should be reprocessed and keeping track of which

 // vertices are in the queue with a property map. Baah, this only

 // applies when we have a bidirectional graph.

 template<typename MutableGraph>

 void

 remove_dangling_links(MutableGraph& g)

 {

   typename graph_traits<MutableGraph>::vertices_size_type old_n;

   do {

     old_n = num_vertices(g);

     typename graph_traits<MutableGraph>::vertex_iterator vi, vi_end;

     for (tie(vi, vi_end) = vertices(g); vi != vi_end; /* in loop */) {

       typename graph_traits<MutableGraph>::vertex_descriptor v = *vi++;

       if (out_degree(v, g) == 0) {

         clear_vertex(v, g);

         remove_vertex(v, g);

       }

     }

   } while (num_vertices(g) < old_n);

 }

 } } // end namespace boost::graph

 #endif // BOOST_GRAPH_PAGE_RANK_HPP