// Copyright 2004 The Trustees of Indiana University.
// Copyright 2002 Brad King and Douglas Gregor

// Use, modification and distribution is subject to 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/named_params.hpp>
#include <boost/property_map.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/vector_property_map.hpp>
#include <boost/graph/iteration_macros.hpp>

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 {
  boost::keyword<struct rank_map_t> rank_map;
  boost::keyword<struct done_t> done;
  boost::keyword<struct num_active_vertices_t> num_active_vertices;
  boost::keyword<struct rank_map2_t> rank_map2;
}

namespace detail {
  template<typename Graph, typename RankMap, typename RankMap2>
  void page_rank_step(const Graph& g, RankMap from_rank, RankMap2 to_rank,
		      incidence_graph_tag)
  {
    typedef typename property_traits<RankMap>::value_type rank_type;

    // Set new rank maps 

    // TBD: for distributed graphs, will need to clear out the cached
    // values for all of the remote vertices so that the first
    // get(to_rank, v) returns zero.
    BGL_FORALL_VERTICES_T(v, g, Graph) put(to_rank, v, rank_type(0));

    BGL_FORALL_VERTICES_T(u, g, Graph) {
      rank_type u_rank_out = 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,
		      bidirectional_graph_tag)
  {
    // TBD: for distributed graphs, this isn't such a good idea
    // because we won't always have accurate rank data for the source
    // vertices. Thus, the IncidenceGraph version is better for
    // distributed incidence graphs.
    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, rank);
    }
  }

  template<typename Graph, typename RankMap, typename Done, typename RankMap2>
  void 
  page_rank_impl(const Graph& g, RankMap rank_map, Done done, 
		 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, category());
      else detail::page_rank_step(g, rank_map2, rank_map, 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));
    }
  }

  struct page_rank_keywords 
    : boost::keywords<detail::graph_t, rank_map_t, done_t, 
		      num_active_vertices_t, rank_map2_t> { };

  template<typename Graph, typename T>
  class vector_property_map_builder
  {
    typedef typename property_map<Graph, vertex_index_t>::const_type
      index_map_type;

  public:
    typedef vector_property_map<T, index_map_type> result_type;

    vector_property_map_builder(const Graph& g) : g(g) { }

    result_type
    operator()() const
    { return make_vector_property_map<T>(get(vertex_index, g)); }

  private:
    const Graph& g;
  };

  template<typename Graph, typename RankMap, typename Params>
  void page_rank(const Graph& g, RankMap rank_map, const Params& p)
  {
    typedef typename property_traits<RankMap>::value_type rank_type;

    detail::page_rank_impl
      (g, 
       rank_map,
       p[done | n_iterations(20)],
       p[num_active_vertices | num_vertices(g)],
       p[rank_map2 
	 || vector_property_map_builder<Graph, rank_type>(g)]);
  }
}

template<typename Graph, typename RankMap>
void 
page_rank(const Graph& g, RankMap rank_map)
{
  detail::page_rank(g, rank_map, detail::page_rank_keywords()());
}

template<typename Graph, typename RankMap, typename T0>
void 
page_rank(const Graph& g, RankMap rank_map, const T0& a0)
{
  detail::page_rank(g, rank_map, detail::page_rank_keywords()(a0));
}

template<typename Graph, typename RankMap, typename T0, typename T1>
void 
page_rank(const Graph& g, RankMap rank_map, const T0& a0, const T1& a1)
{
  detail::page_rank(g, rank_map, detail::page_rank_keywords()(a0, a1));
}

template<typename Graph, typename RankMap, typename T0, typename T1,
	 typename T2>
void 
page_rank(const Graph& g, RankMap rank_map, const T0& a0, const T1& a1,
	  const T2& a2)
{
  detail::page_rank(g, rank_map, detail::page_rank_keywords()(a0, a1, a2));
}

// 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.
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