ceph/src/boost/libs/graph/include/boost/graph/page_rank.hpp

   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/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 <boost/graph/overloading.hpp>
  19 #include <vector>
  20
  21 namespace boost { namespace graph {
  22
  23 struct n_iterations
  24 {
  25   explicit n_iterations(std::size_t n) : n(n) { }
  26
  27   template<typename RankMap, typename Graph>
  28   bool
  29   operator()(const RankMap&, const Graph&)
  30   {
  31     return n-- == 0;
  32   }
  33
  34  private:
  35   std::size_t n;
  36 };
  37
  38 namespace detail {
  39   template<typename Graph, typename RankMap, typename RankMap2>
  40   void page_rank_step(const Graph& g, RankMap from_rank, RankMap2 to_rank,
  41                       typename property_traits<RankMap>::value_type damping,
  42                       incidence_graph_tag)
  43   {
  44     typedef typename property_traits<RankMap>::value_type rank_type;
  45
  46     // Set new rank maps
  47     BGL_FORALL_VERTICES_T(v, g, Graph) put(to_rank, v, rank_type(1 - damping));
  48
  49     BGL_FORALL_VERTICES_T(u, g, Graph) {
  50       rank_type u_rank_out = damping * get(from_rank, u) / out_degree(u, g);
  51       BGL_FORALL_ADJ_T(u, v, g, Graph)
  52         put(to_rank, v, get(to_rank, v) + u_rank_out);
  53     }
  54   }
  55
  56   template<typename Graph, typename RankMap, typename RankMap2>
  57   void page_rank_step(const Graph& g, RankMap from_rank, RankMap2 to_rank,
  58                       typename property_traits<RankMap>::value_type damping,
  59                       bidirectional_graph_tag)
  60   {
  61     typedef typename property_traits<RankMap>::value_type damping_type;
  62     BGL_FORALL_VERTICES_T(v, g, Graph) {
  63       typename property_traits<RankMap>::value_type rank(0);
  64       BGL_FORALL_INEDGES_T(v, e, g, Graph)
  65         rank += get(from_rank, source(e, g)) / out_degree(source(e, g), g);
  66       put(to_rank, v, (damping_type(1) - damping) + damping * rank);
  67     }
  68   }
  69 } // end namespace detail
  70
  71 template<typename Graph, typename RankMap, typename Done, typename RankMap2>
  72 void
  73 page_rank(const Graph& g, RankMap rank_map, Done done,
  74           typename property_traits<RankMap>::value_type damping,
  75           typename graph_traits<Graph>::vertices_size_type n,
  76           RankMap2 rank_map2
  77           BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, vertex_list_graph_tag))
  78 {
  79   typedef typename property_traits<RankMap>::value_type rank_type;
  80
  81   rank_type initial_rank = rank_type(rank_type(1) / n);
  82   BGL_FORALL_VERTICES_T(v, g, Graph) put(rank_map, v, initial_rank);
  83
  84   bool to_map_2 = true;
  85   while ((to_map_2 && !done(rank_map, g)) ||
  86          (!to_map_2 && !done(rank_map2, g))) {
  87     typedef typename graph_traits<Graph>::traversal_category category;
  88
  89     if (to_map_2) {
  90       detail::page_rank_step(g, rank_map, rank_map2, damping, category());
  91     } else {
  92       detail::page_rank_step(g, rank_map2, rank_map, damping, category());
  93     }
  94     to_map_2 = !to_map_2;
  95   }
  96
  97   if (!to_map_2) {
  98     BGL_FORALL_VERTICES_T(v, g, Graph) put(rank_map, v, get(rank_map2, v));
  99   }
 100 }
 101
 102 template<typename Graph, typename RankMap, typename Done>
 103 void
 104 page_rank(const Graph& g, RankMap rank_map, Done done,
 105           typename property_traits<RankMap>::value_type damping,
 106           typename graph_traits<Graph>::vertices_size_type n)
 107 {
 108   typedef typename property_traits<RankMap>::value_type rank_type;
 109
 110   std::vector<rank_type> ranks2(num_vertices(g));
 111   page_rank(g, rank_map, done, damping, n,
 112             make_iterator_property_map(ranks2.begin(), get(vertex_index, g)));
 113 }
 114
 115 template<typename Graph, typename RankMap, typename Done>
 116 inline void
 117 page_rank(const Graph& g, RankMap rank_map, Done done,
 118           typename property_traits<RankMap>::value_type damping = 0.85)
 119 {
 120   page_rank(g, rank_map, done, damping, num_vertices(g));
 121 }
 122
 123 template<typename Graph, typename RankMap>
 124 inline void
 125 page_rank(const Graph& g, RankMap rank_map)
 126 {
 127   page_rank(g, rank_map, n_iterations(20));
 128 }
 129
 130 // TBD: this could be _much_ more efficient, using a queue to store
 131 // the vertices that should be reprocessed and keeping track of which
 132 // vertices are in the queue with a property map. Baah, this only
 133 // applies when we have a bidirectional graph.
 134 template<typename MutableGraph>
 135 void
 136 remove_dangling_links(MutableGraph& g
 137                       BOOST_GRAPH_ENABLE_IF_MODELS_PARM(MutableGraph,
 138                                                         vertex_list_graph_tag))
 139 {
 140   typename graph_traits<MutableGraph>::vertices_size_type old_n;
 141   do {
 142     old_n = num_vertices(g);
 143
 144     typename graph_traits<MutableGraph>::vertex_iterator vi, vi_end;
 145     for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; /* in loop */) {
 146       typename graph_traits<MutableGraph>::vertex_descriptor v = *vi++;
 147       if (out_degree(v, g) == 0) {
 148         clear_vertex(v, g);
 149         remove_vertex(v, g);
 150       }
 151     }
 152   } while (num_vertices(g) < old_n);
 153 }
 154
 155 } } // end namespace boost::graph
 156
 157 #ifdef BOOST_GRAPH_USE_MPI
 158 #  include <boost/graph/distributed/page_rank.hpp>
 159 #endif
 160
 161 #endif // BOOST_GRAPH_PAGE_RANK_HPP