1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
|
// Copyright 2004-5 The Trustees of Indiana University.
// Copyright 2002 Brad King and Douglas Gregor
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
// Authors: Douglas Gregor
// Andrew Lumsdaine
#ifndef BOOST_GRAPH_PAGE_RANK_HPP
#define BOOST_GRAPH_PAGE_RANK_HPP
#include <boost/property_map/property_map.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/iteration_macros.hpp>
#include <boost/graph/overloading.hpp>
#include <vector>
namespace boost { namespace graph {
struct n_iterations
{
explicit n_iterations(std::size_t n) : n(n) { }
template<typename RankMap, typename Graph>
bool
operator()(const RankMap&, const Graph&)
{
return n-- == 0;
}
private:
std::size_t n;
};
namespace detail {
template<typename Graph, typename RankMap, typename RankMap2>
void page_rank_step(const Graph& g, RankMap from_rank, RankMap2 to_rank,
typename property_traits<RankMap>::value_type damping,
incidence_graph_tag)
{
typedef typename property_traits<RankMap>::value_type rank_type;
// Set new rank maps
BGL_FORALL_VERTICES_T(v, g, Graph) put(to_rank, v, rank_type(1 - damping));
BGL_FORALL_VERTICES_T(u, g, Graph) {
rank_type u_rank_out = damping * get(from_rank, u) / out_degree(u, g);
BGL_FORALL_ADJ_T(u, v, g, Graph)
put(to_rank, v, get(to_rank, v) + u_rank_out);
}
}
template<typename Graph, typename RankMap, typename RankMap2>
void page_rank_step(const Graph& g, RankMap from_rank, RankMap2 to_rank,
typename property_traits<RankMap>::value_type damping,
bidirectional_graph_tag)
{
typedef typename property_traits<RankMap>::value_type damping_type;
BGL_FORALL_VERTICES_T(v, g, Graph) {
typename property_traits<RankMap>::value_type rank(0);
BGL_FORALL_INEDGES_T(v, e, g, Graph)
rank += get(from_rank, source(e, g)) / out_degree(source(e, g), g);
put(to_rank, v, (damping_type(1) - damping) + damping * rank);
}
}
} // end namespace detail
template<typename Graph, typename RankMap, typename Done, typename RankMap2>
void
page_rank(const Graph& g, RankMap rank_map, Done done,
typename property_traits<RankMap>::value_type damping,
typename graph_traits<Graph>::vertices_size_type n,
RankMap2 rank_map2
BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, vertex_list_graph_tag))
{
typedef typename property_traits<RankMap>::value_type rank_type;
rank_type initial_rank = rank_type(rank_type(1) / n);
BGL_FORALL_VERTICES_T(v, g, Graph) put(rank_map, v, initial_rank);
bool to_map_2 = true;
while ((to_map_2 && !done(rank_map, g)) ||
(!to_map_2 && !done(rank_map2, g))) {
typedef typename graph_traits<Graph>::traversal_category category;
if (to_map_2) {
detail::page_rank_step(g, rank_map, rank_map2, damping, category());
} else {
detail::page_rank_step(g, rank_map2, rank_map, damping, category());
}
to_map_2 = !to_map_2;
}
if (!to_map_2) {
BGL_FORALL_VERTICES_T(v, g, Graph) put(rank_map, v, get(rank_map2, v));
}
}
template<typename Graph, typename RankMap, typename Done>
void
page_rank(const Graph& g, RankMap rank_map, Done done,
typename property_traits<RankMap>::value_type damping,
typename graph_traits<Graph>::vertices_size_type n)
{
typedef typename property_traits<RankMap>::value_type rank_type;
std::vector<rank_type> ranks2(num_vertices(g));
page_rank(g, rank_map, done, damping, n,
make_iterator_property_map(ranks2.begin(), get(vertex_index, g)));
}
template<typename Graph, typename RankMap, typename Done>
inline void
page_rank(const Graph& g, RankMap rank_map, Done done,
typename property_traits<RankMap>::value_type damping = 0.85)
{
page_rank(g, rank_map, done, damping, num_vertices(g));
}
template<typename Graph, typename RankMap>
inline void
page_rank(const Graph& g, RankMap rank_map)
{
page_rank(g, rank_map, n_iterations(20));
}
// TBD: this could be _much_ more efficient, using a queue to store
// the vertices that should be reprocessed and keeping track of which
// vertices are in the queue with a property map. Baah, this only
// applies when we have a bidirectional graph.
template<typename MutableGraph>
void
remove_dangling_links(MutableGraph& g
BOOST_GRAPH_ENABLE_IF_MODELS_PARM(MutableGraph,
vertex_list_graph_tag))
{
typename graph_traits<MutableGraph>::vertices_size_type old_n;
do {
old_n = num_vertices(g);
typename graph_traits<MutableGraph>::vertex_iterator vi, vi_end;
for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; /* in loop */) {
typename graph_traits<MutableGraph>::vertex_descriptor v = *vi++;
if (out_degree(v, g) == 0) {
clear_vertex(v, g);
remove_vertex(v, g);
}
}
} while (num_vertices(g) < old_n);
}
} } // end namespace boost::graph
#ifdef BOOST_GRAPH_USE_MPI
# include <boost/graph/distributed/page_rank.hpp>
#endif
#endif // BOOST_GRAPH_PAGE_RANK_HPP
|
