Boost logo

Boost-Commit :

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

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
+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.
+*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
+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
+.. _Distributed Graph: DistributedGraph.html
+.. _Distributed Property Map: distributed_property_map.html
+.. _Incidence Graph:

Boost-Commit list run by bdawes at, david.abrahams at, gregod at, cpdaniel at, john at