epoc32/include/stdapis/boost/graph/page_rank.hpp
branchSymbian2
changeset 2 2fe1408b6811
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/epoc32/include/stdapis/boost/graph/page_rank.hpp	Tue Mar 16 16:12:26 2010 +0000
     1.3 @@ -0,0 +1,153 @@
     1.4 +// Copyright 2004-5 The Trustees of Indiana University.
     1.5 +// Copyright 2002 Brad King and Douglas Gregor
     1.6 +
     1.7 +// Distributed under the Boost Software License, Version 1.0.
     1.8 +// (See accompanying file LICENSE_1_0.txt or copy at
     1.9 +// http://www.boost.org/LICENSE_1_0.txt)
    1.10 +
    1.11 +//  Authors: Douglas Gregor
    1.12 +//           Andrew Lumsdaine
    1.13 +
    1.14 +#ifndef BOOST_GRAPH_PAGE_RANK_HPP
    1.15 +#define BOOST_GRAPH_PAGE_RANK_HPP
    1.16 +
    1.17 +#include <boost/property_map.hpp>
    1.18 +#include <boost/graph/graph_traits.hpp>
    1.19 +#include <boost/graph/properties.hpp>
    1.20 +#include <boost/graph/iteration_macros.hpp>
    1.21 +#include <vector>
    1.22 +
    1.23 +namespace boost { namespace graph {
    1.24 +
    1.25 +struct n_iterations
    1.26 +{
    1.27 +  explicit n_iterations(std::size_t n) : n(n) { }
    1.28 +
    1.29 +  template<typename RankMap, typename Graph>
    1.30 +  bool 
    1.31 +  operator()(const RankMap&, const Graph&)
    1.32 +  {
    1.33 +    return n-- == 0;
    1.34 +  }
    1.35 +
    1.36 + private:
    1.37 +  std::size_t n;
    1.38 +};
    1.39 +
    1.40 +namespace detail {
    1.41 +  template<typename Graph, typename RankMap, typename RankMap2>
    1.42 +  void page_rank_step(const Graph& g, RankMap from_rank, RankMap2 to_rank,
    1.43 +                      typename property_traits<RankMap>::value_type damping,
    1.44 +                      incidence_graph_tag)
    1.45 +  {
    1.46 +    typedef typename property_traits<RankMap>::value_type rank_type;
    1.47 +
    1.48 +    // Set new rank maps 
    1.49 +    BGL_FORALL_VERTICES_T(v, g, Graph) put(to_rank, v, rank_type(1 - damping));
    1.50 +
    1.51 +    BGL_FORALL_VERTICES_T(u, g, Graph) {
    1.52 +      rank_type u_rank_out = damping * get(from_rank, u) / out_degree(u, g);
    1.53 +      BGL_FORALL_ADJ_T(u, v, g, Graph)
    1.54 +        put(to_rank, v, get(to_rank, v) + u_rank_out);
    1.55 +    }
    1.56 +  }
    1.57 +
    1.58 +  template<typename Graph, typename RankMap, typename RankMap2>
    1.59 +  void page_rank_step(const Graph& g, RankMap from_rank, RankMap2 to_rank,
    1.60 +                      typename property_traits<RankMap>::value_type damping,
    1.61 +                      bidirectional_graph_tag)
    1.62 +  {
    1.63 +    typedef typename property_traits<RankMap>::value_type damping_type;
    1.64 +    BGL_FORALL_VERTICES_T(v, g, Graph) {
    1.65 +      typename property_traits<RankMap>::value_type rank(0);
    1.66 +      BGL_FORALL_INEDGES_T(v, e, g, Graph)
    1.67 +        rank += get(from_rank, source(e, g)) / out_degree(source(e, g), g);
    1.68 +      put(to_rank, v, (damping_type(1) - damping) + damping * rank);
    1.69 +    }
    1.70 +  }
    1.71 +} // end namespace detail
    1.72 +
    1.73 +template<typename Graph, typename RankMap, typename Done, typename RankMap2>
    1.74 +void
    1.75 +page_rank(const Graph& g, RankMap rank_map, Done done, 
    1.76 +          typename property_traits<RankMap>::value_type damping,
    1.77 +          typename graph_traits<Graph>::vertices_size_type n,
    1.78 +          RankMap2 rank_map2)
    1.79 +{
    1.80 +  typedef typename property_traits<RankMap>::value_type rank_type;
    1.81 +
    1.82 +  rank_type initial_rank = rank_type(rank_type(1) / n);
    1.83 +  BGL_FORALL_VERTICES_T(v, g, Graph) put(rank_map, v, initial_rank);
    1.84 +
    1.85 +  bool to_map_2 = true;
    1.86 +  while ((to_map_2 && !done(rank_map, g)) ||
    1.87 +         (!to_map_2 && !done(rank_map2, g))) {
    1.88 +    typedef typename graph_traits<Graph>::traversal_category category;
    1.89 +
    1.90 +    if (to_map_2) {
    1.91 +      detail::page_rank_step(g, rank_map, rank_map2, damping, category());
    1.92 +    } else {
    1.93 +      detail::page_rank_step(g, rank_map2, rank_map, damping, category());
    1.94 +    }
    1.95 +    to_map_2 = !to_map_2;
    1.96 +  }
    1.97 +
    1.98 +  if (!to_map_2) {
    1.99 +    BGL_FORALL_VERTICES_T(v, g, Graph) put(rank_map, v, get(rank_map2, v));
   1.100 +  }
   1.101 +}
   1.102 +
   1.103 +template<typename Graph, typename RankMap, typename Done>
   1.104 +void
   1.105 +page_rank(const Graph& g, RankMap rank_map, Done done, 
   1.106 +          typename property_traits<RankMap>::value_type damping,
   1.107 +          typename graph_traits<Graph>::vertices_size_type n)
   1.108 +{
   1.109 +  typedef typename property_traits<RankMap>::value_type rank_type;
   1.110 +
   1.111 +  std::vector<rank_type> ranks2(num_vertices(g));
   1.112 +  page_rank(g, rank_map, done, damping, n,
   1.113 +            make_iterator_property_map(ranks2.begin(), get(vertex_index, g)));
   1.114 +}
   1.115 +
   1.116 +template<typename Graph, typename RankMap, typename Done>
   1.117 +inline void
   1.118 +page_rank(const Graph& g, RankMap rank_map, Done done, 
   1.119 +          typename property_traits<RankMap>::value_type damping = 0.85)
   1.120 +{
   1.121 +  page_rank(g, rank_map, done, damping, num_vertices(g));
   1.122 +}
   1.123 +
   1.124 +template<typename Graph, typename RankMap>
   1.125 +inline void
   1.126 +page_rank(const Graph& g, RankMap rank_map)
   1.127 +{
   1.128 +  page_rank(g, rank_map, n_iterations(20));
   1.129 +}
   1.130 +
   1.131 +// TBD: this could be _much_ more efficient, using a queue to store
   1.132 +// the vertices that should be reprocessed and keeping track of which
   1.133 +// vertices are in the queue with a property map. Baah, this only
   1.134 +// applies when we have a bidirectional graph.
   1.135 +template<typename MutableGraph>
   1.136 +void
   1.137 +remove_dangling_links(MutableGraph& g)
   1.138 +{
   1.139 +  typename graph_traits<MutableGraph>::vertices_size_type old_n;
   1.140 +  do {
   1.141 +    old_n = num_vertices(g);
   1.142 +
   1.143 +    typename graph_traits<MutableGraph>::vertex_iterator vi, vi_end;
   1.144 +    for (tie(vi, vi_end) = vertices(g); vi != vi_end; /* in loop */) {
   1.145 +      typename graph_traits<MutableGraph>::vertex_descriptor v = *vi++;
   1.146 +      if (out_degree(v, g) == 0) {
   1.147 +        clear_vertex(v, g);
   1.148 +        remove_vertex(v, g);
   1.149 +      }
   1.150 +    }
   1.151 +  } while (num_vertices(g) < old_n);
   1.152 +}
   1.153 +
   1.154 +} } // end namespace boost::graph
   1.155 +
   1.156 +#endif // BOOST_GRAPH_PAGE_RANK_HPP