// Copyright 2004 The Trustees of Indiana University. // Copyright 2002 Brad King and Douglas Gregor // Use, modification and distribution is subject to 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 #include #include #include #include #include namespace boost { namespace graph { struct n_iterations { explicit n_iterations(std::size_t n) : n(n) { } template bool operator()(const RankMap&, const Graph&) { return n-- == 0; } private: std::size_t n; }; namespace { // keyword rank_map; keyword num_active_vertices; } namespace detail { template void page_rank_step(const Graph& g, RankMap from_rank, RankMap2 to_rank, incidence_graph_tag) { typedef typename property_traits::value_type rank_type; // Set new rank maps // TBD: for distributed graphs, will need to clear out the cached // values for all of the remote vertices so that the first // get(to_rank, v) returns zero. BGL_FORALL_VERTICES_T(v, g, Graph) put(to_rank, v, rank_type(0)); BGL_FORALL_VERTICES_T(u, g, Graph) { rank_type u_rank_out = 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 void page_rank_step(const Graph& g, RankMap from_rank, RankMap2 to_rank, bidirectional_graph_tag) { // TBD: for distributed graphs, this isn't such a good idea // because we won't always have accurate rank data for the source // vertices. Thus, the IncidenceGraph version is better for // distributed incidence graphs. BGL_FORALL_VERTICES_T(v, g, Graph) { typename property_traits::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, rank); } } template void page_rank_impl(const Graph& g, RankMap rank_map, Terminate terminate, typename graph_traits::vertices_size_type n, RankMap2 rank_map2) { typedef typename property_traits::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 && !terminate(rank_map, g)) || (!to_map_2 && !terminate(rank_map2, g))) { typedef typename graph_traits::traversal_category category; if (to_map_2) detail::page_rank_step(g, rank_map, rank_map2, category()); else detail::page_rank_step(g, rank_map2, rank_map, 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)); } } struct page_rank_keywords : boost::keywords { }; template class vector_property_map_builder { typedef typename property_map::const_type index_map_type; public: typedef vector_property_map result_type; vector_property_map_builder(const Graph& g) : g(g) { } result_type operator()() const { return make_vector_property_map(get(vertex_index, g)); } private: const Graph& g; }; template void page_rank(const Graph& g, RankMap rank_map, const Params& p) { typedef typename property_traits::value_type rank_type; detail::page_rank_impl (g, rank_map, p[terminate | n_iterations(20)], p[num_active_vertices | num_vertices(g)], p[rank_map2 || vector_property_map_builder(g)]); } } template void page_rank(const Graph& g, RankMap rank_map) { detail::page_rank(g, rank_map, detail::page_rank_keywords()()); } template void page_rank(const Graph& g, RankMap rank_map, const T0& a0) { detail::page_rank(g, rank_map, detail::page_rank_keywords()(a0)); } template void page_rank(const Graph& g, RankMap rank_map, const T0& a0, const T1& a1) { detail::page_rank(g, rank_map, detail::page_rank_keywords()(a0, a1)); } template void page_rank(const Graph& g, RankMap rank_map, const T0& a0, const T1& a1, const T2& a2) { detail::page_rank(g, rank_map, detail::page_rank_keywords()(a0, a1, a2)); } template void page_rank(const Graph& g, RankMap rank_map, const bgl_named_params& params) { detail::page_rank(g, rank_map, params.to_named_params_list()); } // 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. template void remove_dangling_links(MutableGraph& g) { typename graph_traits::vertices_size_type old_n; do { old_n = num_vertices(g); typename graph_traits::vertex_iterator vi, vi_end; for (tie(vi, vi_end) = vertices(g); vi != vi_end; /* in loop */) { typename graph_traits::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 #endif // BOOST_GRAPH_PAGE_RANK_HPP