// 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 |