--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/ossrv_pub/boost_apis/boost/graph/page_rank.hpp Tue Feb 02 02:01:42 2010 +0200
@@ -0,0 +1,153 @@
+// 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.hpp>
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/properties.hpp>
+#include <boost/graph/iteration_macros.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)
+{
+ 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)
+{
+ 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 (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
+
+#endif // BOOST_GRAPH_PAGE_RANK_HPP