boost/graph/page_rank.hpp

0001 // Copyright 2004-5 The Trustees of Indiana University.
0002 // Copyright 2002 Brad King and Douglas Gregor
0003
0004 // Distributed under the Boost Software License, Version 1.0.
0005 // (See accompanying file LICENSE_1_0.txt or copy at
0006 // http://www.boost.org/LICENSE_1_0.txt)
0007
0008 //  Authors: Douglas Gregor
0009 //           Andrew Lumsdaine
0010
0011 #ifndef BOOST_GRAPH_PAGE_RANK_HPP
0012 #define BOOST_GRAPH_PAGE_RANK_HPP
0013
0014 #include <boost/property_map/property_map.hpp>
0015 #include <boost/graph/graph_traits.hpp>
0016 #include <boost/graph/properties.hpp>
0017 #include <boost/graph/iteration_macros.hpp>
0018 #include <boost/graph/overloading.hpp>
0019 #include <boost/graph/detail/mpi_include.hpp>
0020 #include <vector>
0021
0022 namespace boost
0023 {
0024 namespace graph
0025 {
0026
0027     struct n_iterations
0028     {
0029         explicit n_iterations(std::size_t n) : n(n) {}
0030
0031         template < typename RankMap, typename Graph >
0032         bool operator()(const RankMap&, const Graph&)
0033         {
0034             return n-- == 0;
0035         }
0036
0037     private:
0038         std::size_t n;
0039     };
0040
0041     namespace detail
0042     {
0043         template < typename Graph, typename RankMap, typename RankMap2 >
0044         void page_rank_step(const Graph& g, RankMap from_rank, RankMap2 to_rank,
0045             typename property_traits< RankMap >::value_type damping,
0046             incidence_graph_tag)
0047         {
0048             typedef typename property_traits< RankMap >::value_type rank_type;
0049
0050             // Set new rank maps
0051             BGL_FORALL_VERTICES_T(v, g, Graph)
0052             put(to_rank, v, rank_type(1 - damping));
0053
0054             BGL_FORALL_VERTICES_T(u, g, Graph)
0055             {
0056                 rank_type u_rank_out
0057                     = damping * get(from_rank, u) / out_degree(u, g);
0058                 BGL_FORALL_ADJ_T(u, v, g, Graph)
0059                 put(to_rank, v, get(to_rank, v) + u_rank_out);
0060             }
0061         }
0062
0063         template < typename Graph, typename RankMap, typename RankMap2 >
0064         void page_rank_step(const Graph& g, RankMap from_rank, RankMap2 to_rank,
0065             typename property_traits< RankMap >::value_type damping,
0066             bidirectional_graph_tag)
0067         {
0068             typedef
0069                 typename property_traits< RankMap >::value_type damping_type;
0070             BGL_FORALL_VERTICES_T(v, g, Graph)
0071             {
0072                 typename property_traits< RankMap >::value_type rank(0);
0073                 BGL_FORALL_INEDGES_T(v, e, g, Graph)
0074                 rank += get(from_rank, source(e, g))
0075                     / out_degree(source(e, g), g);
0076                 put(to_rank, v, (damping_type(1) - damping) + damping * rank);
0077             }
0078         }
0079     } // end namespace detail
0080
0081     template < typename Graph, typename RankMap, typename Done,
0082         typename RankMap2 >
0083     void page_rank(const Graph& g, RankMap rank_map, Done done,
0084         typename property_traits< RankMap >::value_type damping,
0085         typename graph_traits< Graph >::vertices_size_type n,
0086         RankMap2 rank_map2 BOOST_GRAPH_ENABLE_IF_MODELS_PARM(
0087             Graph, vertex_list_graph_tag))
0088     {
0089         typedef typename property_traits< RankMap >::value_type rank_type;
0090
0091         rank_type initial_rank = rank_type(rank_type(1) / n);
0092         BGL_FORALL_VERTICES_T(v, g, Graph) put(rank_map, v, initial_rank);
0093
0094         bool to_map_2 = true;
0095         while ((to_map_2 && !done(rank_map, g))
0096             || (!to_map_2 && !done(rank_map2, g)))
0097         {
0098             typedef typename graph_traits< Graph >::traversal_category category;
0099
0100             if (to_map_2)
0101             {
0102                 detail::page_rank_step(
0103                     g, rank_map, rank_map2, damping, category());
0104             }
0105             else
0106             {
0107                 detail::page_rank_step(
0108                     g, rank_map2, rank_map, damping, category());
0109             }
0110             to_map_2 = !to_map_2;
0111         }
0112
0113         if (!to_map_2)
0114         {
0115             BGL_FORALL_VERTICES_T(v, g, Graph)
0116             put(rank_map, v, get(rank_map2, v));
0117         }
0118     }
0119
0120     template < typename Graph, typename RankMap, typename Done >
0121     void page_rank(const Graph& g, RankMap rank_map, Done done,
0122         typename property_traits< RankMap >::value_type damping,
0123         typename graph_traits< Graph >::vertices_size_type n)
0124     {
0125         typedef typename property_traits< RankMap >::value_type rank_type;
0126
0127         std::vector< rank_type > ranks2(num_vertices(g));
0128         page_rank(g, rank_map, done, damping, n,
0129             make_iterator_property_map(ranks2.begin(), get(vertex_index, g)));
0130     }
0131
0132     template < typename Graph, typename RankMap, typename Done >
0133     inline void page_rank(const Graph& g, RankMap rank_map, Done done,
0134         typename property_traits< RankMap >::value_type damping = 0.85)
0135     {
0136         page_rank(g, rank_map, done, damping, num_vertices(g));
0137     }
0138
0139     template < typename Graph, typename RankMap >
0140     inline void page_rank(const Graph& g, RankMap rank_map)
0141     {
0142         page_rank(g, rank_map, n_iterations(20));
0143     }
0144
0145     // TBD: this could be _much_ more efficient, using a queue to store
0146     // the vertices that should be reprocessed and keeping track of which
0147     // vertices are in the queue with a property map. Baah, this only
0148     // applies when we have a bidirectional graph.
0149     template < typename MutableGraph >
0150     void remove_dangling_links(
0151         MutableGraph& g BOOST_GRAPH_ENABLE_IF_MODELS_PARM(
0152             MutableGraph, vertex_list_graph_tag))
0153     {
0154         typename graph_traits< MutableGraph >::vertices_size_type old_n;
0155         do
0156         {
0157             old_n = num_vertices(g);
0158
0159             typename graph_traits< MutableGraph >::vertex_iterator vi, vi_end;
0160             for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end;
0161                 /* in loop */)
0162             {
0163                 typename graph_traits< MutableGraph >::vertex_descriptor v
0164                     = *vi++;
0165                 if (out_degree(v, g) == 0)
0166                 {
0167                     clear_vertex(v, g);
0168                     remove_vertex(v, g);
0169                 }
0170             }
0171         } while (num_vertices(g) < old_n);
0172     }
0173
0174 }
0175 } // end namespace boost::graph
0176
0177 #include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/page_rank.hpp>)
0178
0179 #endif // BOOST_GRAPH_PAGE_RANK_HPP