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