add subtree-ish sources for 12.0.3

[ceph.git] / ceph / src / boost / libs / graph_parallel / doc / page_rank.rst

.. Copyright (C) 2004-2008 The Trustees of Indiana University.
   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)

===============
|Logo| PageRank
===============

::
  
  namespace graph { 
    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);

    template<typename Graph, typename RankMap>
    inline void
    page_rank(const Graph& g, RankMap rank_map);
  } 
  
The ``page_rank`` algorithm computes the ranking of vertices in a
graph, based on the connectivity of a directed graph [PBMW98]_. The
idea of PageRank is based on a random model of a Web surfer, who
starts a random web page and then either follows a link from that web
page (choosing from the links randomly) or jumps to a completely
different web page (not necessarily linked from the current
page). The PageRank of each page is the probability of the random web
surfer visiting that page.

.. contents::

Where Defined
~~~~~~~~~~~~~
<``boost/graph/distributed/page_rank.hpp``>

also accessible from

<``boost/graph/page_rank.hpp``>

Parameters
~~~~~~~~~~

IN: ``Graph& g``
  The graph type must be a model of `Distributed Vertex List Graph`_ and
  `Distributed Edge List Graph`_. The graph must be directed.

OUT: ``RankMap rank``
  Stores the rank of each vertex. The type ``RankMap`` must model the
  `Read/Write Property Map`_ concept and must be a `distributed
  property map`_. Its key type must be the vertex descriptor of the
  graph type and its value type must be a floating-point or rational
  type. 

IN: ``Done done``
  A function object that determines when the PageRank algorithm
  should complete. It will be passed two parameters, the rank map and
  a reference to the graph, and should return ``true`` when the
  algorithm should terminate.

  **Default**: ``graph::n_iterations(20)``

IN: ``typename property_traits<RankMap>::value_type damping``
  The damping factor is the probability that the Web surfer will
  select an outgoing link from the current page instead of jumping to
  a random page. 

  **Default**: 0.85

Complexity
~~~~~~~~~~
Each iteration of PageRank requires *O((V + E)/p)* time on *p*
processors and performs *O(V)* communication. The number of
iterations is dependent on the input to the algorithm.

Bibliography
------------

.. [PBMW98] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry
  Winograd. The PageRank Citation Ranking: Bringing Order to the
  Web. Technical report, Stanford Digital Library Technologies Project,
  November 1998.

-----------------------------------------------------------------------------

Copyright (C) 2005 The Trustees of Indiana University.

Authors: Douglas Gregor and Andrew Lumsdaine

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

.. _Distributed Vertex List Graph: DistributedVertexListGraph.html
.. _Distributed Edge List Graph: DistributedEdgeListGraph.html
.. _Distributed property map: distributed_property_map.html
.. _Readable Property Map: http://www.boost.org/libs/property_map/ReadablePropertyMap.html
.. _Read/Write Property Map: http://www.boost.org/libs/property_map/ReadWritePropertyMap.html