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
|