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

     2 // Copyright 2002 Brad King and Douglas Gregor

     3 

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

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

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

     7 

     8 //  Authors: Douglas Gregor

     9 //           Andrew Lumsdaine

    10 

    11 #ifndef BOOST_GRAPH_PAGE_RANK_HPP

    12 #define BOOST_GRAPH_PAGE_RANK_HPP

    13 

    14 #include <boost/property_map.hpp>

    15 #include <boost/graph/graph_traits.hpp>

    16 #include <boost/graph/properties.hpp>

    17 #include <boost/graph/iteration_macros.hpp>

    18 #include <vector>

    19 

    20 namespace boost { namespace graph {

    21 

    22 struct n_iterations

    23 {

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

    25 

    26   template<typename RankMap, typename Graph>

    27   bool 

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

    29   {

    30     return n-- == 0;

    31   }

    32 

    33  private:

    34   std::size_t n;

    35 };

    36 

    37 namespace detail {

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

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

    40                       typename property_traits<RankMap>::value_type damping,

    41                       incidence_graph_tag)

    42   {

    43     typedef typename property_traits<RankMap>::value_type rank_type;

    44 

    45     // Set new rank maps 

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

    47 

    48     BGL_FORALL_VERTICES_T(u, g, Graph) {

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

    50       BGL_FORALL_ADJ_T(u, v, g, Graph)

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

    52     }

    53   }

    54 

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

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

    57                       typename property_traits<RankMap>::value_type damping,

    58                       bidirectional_graph_tag)

    59   {

    60     typedef typename property_traits<RankMap>::value_type damping_type;

    61     BGL_FORALL_VERTICES_T(v, g, Graph) {

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

    63       BGL_FORALL_INEDGES_T(v, e, g, Graph)

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

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

    66     }

    67   }

    68 } // end namespace detail

    69 

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

    71 void

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

    73           typename property_traits<RankMap>::value_type damping,

    74           typename graph_traits<Graph>::vertices_size_type n,

    75           RankMap2 rank_map2)

    76 {

    77   typedef typename property_traits<RankMap>::value_type rank_type;

    78 

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

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

    81 

    82   bool to_map_2 = true;

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

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

    85     typedef typename graph_traits<Graph>::traversal_category category;

    86 

    87     if (to_map_2) {

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

    89     } else {

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

    91     }

    92     to_map_2 = !to_map_2;

    93   }

    94 

    95   if (!to_map_2) {

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

    97   }

    98 }

    99 

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

   101 void

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

   103           typename property_traits<RankMap>::value_type damping,

   104           typename graph_traits<Graph>::vertices_size_type n)

   105 {

   106   typedef typename property_traits<RankMap>::value_type rank_type;

   107 

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

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

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

   111 }

   112 

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

   114 inline void

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

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

   117 {

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

   119 }

   120 

   121 template<typename Graph, typename RankMap>

   122 inline void

   123 page_rank(const Graph& g, RankMap rank_map)

   124 {

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

   126 }

   127 

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

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

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

   131 // applies when we have a bidirectional graph.

   132 template<typename MutableGraph>

   133 void

   134 remove_dangling_links(MutableGraph& g)

   135 {

   136   typename graph_traits<MutableGraph>::vertices_size_type old_n;

   137   do {

   138     old_n = num_vertices(g);

   139 

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

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

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

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

   144         clear_vertex(v, g);

   145         remove_vertex(v, g);

   146       }

   147     }

   148   } while (num_vertices(g) < old_n);

   149 }

   150 

   151 } } // end namespace boost::graph

   152 

   153 #endif // BOOST_GRAPH_PAGE_RANK_HPP