[Boost-commit] svn:boost r53371 - trunk/libs/graph_parallel/doc

Subject: [Boost-commit] svn:boost r53371 - trunk/libs/graph_parallel/doc
From: ngedmond_at_[hidden]
Date: 2009-05-28 19:24:17

Author: ngedmond
Date: 2009-05-28 19:24:16 EDT (Thu, 28 May 2009)
New Revision: 53371
URL: http://svn.boost.org/trac/boost/changeset/53371

Log:
Documented CC parallel search, mostly using comments from the source code 

Text files modified: 
   trunk/libs/graph_parallel/doc/connected_components_parallel_search.rst |    71 +++++++++++++++++++++++++++++++++++++++ 
   1 files changed, 70 insertions(+), 1 deletions(-)

Modified: trunk/libs/graph_parallel/doc/connected_components_parallel_search.rst
==============================================================================
--- trunk/libs/graph_parallel/doc/connected_components_parallel_search.rst	(original)
+++ trunk/libs/graph_parallel/doc/connected_components_parallel_search.rst	2009-05-28 19:24:16 EDT (Thu, 28 May 2009)
@@ -7,13 +7,82 @@
 |Logo| Connected Components Parallel Search
 ===========================================
 
+::
+
+   namespace graph { namespace distributed {
+     template<typename Graph, typename ComponentMap>
+     typename property_traits<ComponentMap>::value_type
+     connected_components_ps(const Graph& g, ComponentMap c)
+   } }
+
+The ``connected_components_ps()`` function computes the connected
+components of a graph by performing a breadth-first search from
+several sources in parallel while recording and eventually resolving
+the collisions.
+
+.. contents::
+
+Where Defined
+-------------
+<``boost/graph/distributed/connected_components_parallel_search.hpp``>
+
+Parameters
+----------
+
+IN:  ``const Graph& g``
+  The graph type must be a model of `Distributed Graph`_.  The graph
+  type must also model the `Incidence Graph`_ and be directed.
+
+OUT:  ``ComponentMap c``
+  The algorithm computes how many connected components are in the
+  graph, and assigns each component an integer label.  The algorithm
+  then records to which component each vertex in the graph belongs by
+  recording the component number in the component property map.  The
+  ``ComponentMap`` type must be a `Distributed Property Map`_.  The
+  value type must be the ``vertices_size_type`` of the graph.  The key
+  type must be the graph's vertex descriptor type.
+
+Complexity
+----------
+
+*O(PN^2 + VNP)* work, in *O(N + V)* time, where N is the
+number of mappings and V is the number of local vertices.
+
+Algorithm Description
+---------------------
+
+Every *N* th nodes starts a parallel search from the first vertex in
+their local vertex list during the first superstep (the other nodes
+remain idle during the first superstep to reduce the number of
+conflicts in numbering the components).  At each superstep, all new
+component mappings from remote nodes are handled.  If there is no work
+from remote updates, a new vertex is removed from the local list and
+added to the work queue.
+
+Components are allocated from the ``component_value_allocator``
+object, which ensures that a given component number is unique in the
+system, currently by using the rank and number of processes to stride
+allocations.
+
+When two components are discovered to actually be the same component,
+a collision is recorded.  The lower component number is prefered in
+the resolution, so component numbering resolution is consistent.
+After the search has exhausted all vertices in the graph, the mapping
+is shared with all processes and they independently resolve the
+comonent mapping.  This phase can likely be significantly sped up if a
+clever algorithm for the reduction can be found.
+
 -----------------------------------------------------------------------------
 
 Copyright (C) 2009 The Trustees of Indiana University.
 
-Authors: Nick Edmonds and Andrew Lumsdaine
+Authors: Brian Barrett, Douglas Gregor, and Andrew Lumsdaine
 
 .. |Logo| image:: pbgl-logo.png
             :align: middle
             :alt: Parallel BGL
             :target: http://www.osl.iu.edu/research/pbgl
+
+.. _Distributed Graph: DistributedGraph.html
+.. _Distributed Property Map: distributed_property_map.html
+.. _Incidence Graph: http://www.boost.org/libs/graph/doc/IncidenceGraph.html