/usr/include/boost/graph/page_rank.hpp is in libboost1.46-dev 1.46.1-7ubuntu3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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
|