Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / page_rank.hpp
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
20 namespace boost { namespace graph {
21
22 struct 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
37 namespace 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
70 template<typename Graph, typename RankMap, typename Done, typename RankMap2>
71 void
72 page_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
100 template<typename Graph, typename RankMap, typename Done>
101 void
102 page_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
113 template<typename Graph, typename RankMap, typename Done>
114 inline void
115 page_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
121 template<typename Graph, typename RankMap>
122 inline void
123 page_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.
132 template<typename MutableGraph>
133 void
134 remove_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