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