epoc32/include/stdapis/boost/graph/page_rank.hpp
author William Roberts <williamr@symbian.org>
Tue, 16 Mar 2010 16:12:26 +0000
branchSymbian2
changeset 2 2fe1408b6811
permissions -rw-r--r--
Final list of Symbian^2 public API header files
williamr@2
     1
// Copyright 2004-5 The Trustees of Indiana University.
williamr@2
     2
// Copyright 2002 Brad King and Douglas Gregor
williamr@2
     3
williamr@2
     4
// Distributed under the Boost Software License, Version 1.0.
williamr@2
     5
// (See accompanying file LICENSE_1_0.txt or copy at
williamr@2
     6
// http://www.boost.org/LICENSE_1_0.txt)
williamr@2
     7
williamr@2
     8
//  Authors: Douglas Gregor
williamr@2
     9
//           Andrew Lumsdaine
williamr@2
    10
williamr@2
    11
#ifndef BOOST_GRAPH_PAGE_RANK_HPP
williamr@2
    12
#define BOOST_GRAPH_PAGE_RANK_HPP
williamr@2
    13
williamr@2
    14
#include <boost/property_map.hpp>
williamr@2
    15
#include <boost/graph/graph_traits.hpp>
williamr@2
    16
#include <boost/graph/properties.hpp>
williamr@2
    17
#include <boost/graph/iteration_macros.hpp>
williamr@2
    18
#include <vector>
williamr@2
    19
williamr@2
    20
namespace boost { namespace graph {
williamr@2
    21
williamr@2
    22
struct n_iterations
williamr@2
    23
{
williamr@2
    24
  explicit n_iterations(std::size_t n) : n(n) { }
williamr@2
    25
williamr@2
    26
  template<typename RankMap, typename Graph>
williamr@2
    27
  bool 
williamr@2
    28
  operator()(const RankMap&, const Graph&)
williamr@2
    29
  {
williamr@2
    30
    return n-- == 0;
williamr@2
    31
  }
williamr@2
    32
williamr@2
    33
 private:
williamr@2
    34
  std::size_t n;
williamr@2
    35
};
williamr@2
    36
williamr@2
    37
namespace detail {
williamr@2
    38
  template<typename Graph, typename RankMap, typename RankMap2>
williamr@2
    39
  void page_rank_step(const Graph& g, RankMap from_rank, RankMap2 to_rank,
williamr@2
    40
                      typename property_traits<RankMap>::value_type damping,
williamr@2
    41
                      incidence_graph_tag)
williamr@2
    42
  {
williamr@2
    43
    typedef typename property_traits<RankMap>::value_type rank_type;
williamr@2
    44
williamr@2
    45
    // Set new rank maps 
williamr@2
    46
    BGL_FORALL_VERTICES_T(v, g, Graph) put(to_rank, v, rank_type(1 - damping));
williamr@2
    47
williamr@2
    48
    BGL_FORALL_VERTICES_T(u, g, Graph) {
williamr@2
    49
      rank_type u_rank_out = damping * get(from_rank, u) / out_degree(u, g);
williamr@2
    50
      BGL_FORALL_ADJ_T(u, v, g, Graph)
williamr@2
    51
        put(to_rank, v, get(to_rank, v) + u_rank_out);
williamr@2
    52
    }
williamr@2
    53
  }
williamr@2
    54
williamr@2
    55
  template<typename Graph, typename RankMap, typename RankMap2>
williamr@2
    56
  void page_rank_step(const Graph& g, RankMap from_rank, RankMap2 to_rank,
williamr@2
    57
                      typename property_traits<RankMap>::value_type damping,
williamr@2
    58
                      bidirectional_graph_tag)
williamr@2
    59
  {
williamr@2
    60
    typedef typename property_traits<RankMap>::value_type damping_type;
williamr@2
    61
    BGL_FORALL_VERTICES_T(v, g, Graph) {
williamr@2
    62
      typename property_traits<RankMap>::value_type rank(0);
williamr@2
    63
      BGL_FORALL_INEDGES_T(v, e, g, Graph)
williamr@2
    64
        rank += get(from_rank, source(e, g)) / out_degree(source(e, g), g);
williamr@2
    65
      put(to_rank, v, (damping_type(1) - damping) + damping * rank);
williamr@2
    66
    }
williamr@2
    67
  }
williamr@2
    68
} // end namespace detail
williamr@2
    69
williamr@2
    70
template<typename Graph, typename RankMap, typename Done, typename RankMap2>
williamr@2
    71
void
williamr@2
    72
page_rank(const Graph& g, RankMap rank_map, Done done, 
williamr@2
    73
          typename property_traits<RankMap>::value_type damping,
williamr@2
    74
          typename graph_traits<Graph>::vertices_size_type n,
williamr@2
    75
          RankMap2 rank_map2)
williamr@2
    76
{
williamr@2
    77
  typedef typename property_traits<RankMap>::value_type rank_type;
williamr@2
    78
williamr@2
    79
  rank_type initial_rank = rank_type(rank_type(1) / n);
williamr@2
    80
  BGL_FORALL_VERTICES_T(v, g, Graph) put(rank_map, v, initial_rank);
williamr@2
    81
williamr@2
    82
  bool to_map_2 = true;
williamr@2
    83
  while ((to_map_2 && !done(rank_map, g)) ||
williamr@2
    84
         (!to_map_2 && !done(rank_map2, g))) {
williamr@2
    85
    typedef typename graph_traits<Graph>::traversal_category category;
williamr@2
    86
williamr@2
    87
    if (to_map_2) {
williamr@2
    88
      detail::page_rank_step(g, rank_map, rank_map2, damping, category());
williamr@2
    89
    } else {
williamr@2
    90
      detail::page_rank_step(g, rank_map2, rank_map, damping, category());
williamr@2
    91
    }
williamr@2
    92
    to_map_2 = !to_map_2;
williamr@2
    93
  }
williamr@2
    94
williamr@2
    95
  if (!to_map_2) {
williamr@2
    96
    BGL_FORALL_VERTICES_T(v, g, Graph) put(rank_map, v, get(rank_map2, v));
williamr@2
    97
  }
williamr@2
    98
}
williamr@2
    99
williamr@2
   100
template<typename Graph, typename RankMap, typename Done>
williamr@2
   101
void
williamr@2
   102
page_rank(const Graph& g, RankMap rank_map, Done done, 
williamr@2
   103
          typename property_traits<RankMap>::value_type damping,
williamr@2
   104
          typename graph_traits<Graph>::vertices_size_type n)
williamr@2
   105
{
williamr@2
   106
  typedef typename property_traits<RankMap>::value_type rank_type;
williamr@2
   107
williamr@2
   108
  std::vector<rank_type> ranks2(num_vertices(g));
williamr@2
   109
  page_rank(g, rank_map, done, damping, n,
williamr@2
   110
            make_iterator_property_map(ranks2.begin(), get(vertex_index, g)));
williamr@2
   111
}
williamr@2
   112
williamr@2
   113
template<typename Graph, typename RankMap, typename Done>
williamr@2
   114
inline void
williamr@2
   115
page_rank(const Graph& g, RankMap rank_map, Done done, 
williamr@2
   116
          typename property_traits<RankMap>::value_type damping = 0.85)
williamr@2
   117
{
williamr@2
   118
  page_rank(g, rank_map, done, damping, num_vertices(g));
williamr@2
   119
}
williamr@2
   120
williamr@2
   121
template<typename Graph, typename RankMap>
williamr@2
   122
inline void
williamr@2
   123
page_rank(const Graph& g, RankMap rank_map)
williamr@2
   124
{
williamr@2
   125
  page_rank(g, rank_map, n_iterations(20));
williamr@2
   126
}
williamr@2
   127
williamr@2
   128
// TBD: this could be _much_ more efficient, using a queue to store
williamr@2
   129
// the vertices that should be reprocessed and keeping track of which
williamr@2
   130
// vertices are in the queue with a property map. Baah, this only
williamr@2
   131
// applies when we have a bidirectional graph.
williamr@2
   132
template<typename MutableGraph>
williamr@2
   133
void
williamr@2
   134
remove_dangling_links(MutableGraph& g)
williamr@2
   135
{
williamr@2
   136
  typename graph_traits<MutableGraph>::vertices_size_type old_n;
williamr@2
   137
  do {
williamr@2
   138
    old_n = num_vertices(g);
williamr@2
   139
williamr@2
   140
    typename graph_traits<MutableGraph>::vertex_iterator vi, vi_end;
williamr@2
   141
    for (tie(vi, vi_end) = vertices(g); vi != vi_end; /* in loop */) {
williamr@2
   142
      typename graph_traits<MutableGraph>::vertex_descriptor v = *vi++;
williamr@2
   143
      if (out_degree(v, g) == 0) {
williamr@2
   144
        clear_vertex(v, g);
williamr@2
   145
        remove_vertex(v, g);
williamr@2
   146
      }
williamr@2
   147
    }
williamr@2
   148
  } while (num_vertices(g) < old_n);
williamr@2
   149
}
williamr@2
   150
williamr@2
   151
} } // end namespace boost::graph
williamr@2
   152
williamr@2
   153
#endif // BOOST_GRAPH_PAGE_RANK_HPP