source: NonGTP/Boost/boost/graph/page_rank.hpp @ 857

Revision 857, 5.0 KB checked in by igarcia, 19 years ago (diff)
RevLine 
[857]1// Copyright 2004-5 The Trustees of Indiana University.
2// Copyright 2002 Brad King and Douglas Gregor
3
4// Use, modification and distribution is subject to the Boost Software
5// License, Version 1.0. (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
20namespace boost { namespace graph {
21
22struct 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
37namespace 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
70template<typename Graph, typename RankMap, typename Done, typename RankMap2>
71void
72page_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
100template<typename Graph, typename RankMap, typename Done>
101void
102page_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
113template<typename Graph, typename RankMap, typename Done>
114inline void
115page_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
121template<typename Graph, typename RankMap>
122inline void
123page_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.
132template<typename MutableGraph>
133void
134remove_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
Note: See TracBrowser for help on using the repository browser.