1.. Copyright (C) 2004-2009 The Trustees of Indiana University. 2 Use, modification and distribution is subject to the Boost Software 3 License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 4 http://www.boost.org/LICENSE_1_0.txt) 5 6=========================================== 7|Logo| Connected Components Parallel Search 8=========================================== 9 10:: 11 12 namespace graph { namespace distributed { 13 template<typename Graph, typename ComponentMap> 14 typename property_traits<ComponentMap>::value_type 15 connected_components_ps(const Graph& g, ComponentMap c) 16 } } 17 18The ``connected_components_ps()`` function computes the connected 19components of a graph by performing a breadth-first search from 20several sources in parallel while recording and eventually resolving 21the collisions. 22 23.. contents:: 24 25Where Defined 26------------- 27<``boost/graph/distributed/connected_components_parallel_search.hpp``> 28 29Parameters 30---------- 31 32IN: ``const Graph& g`` 33 The graph type must be a model of `Distributed Graph`_. The graph 34 type must also model the `Incidence Graph`_ and be directed. 35 36OUT: ``ComponentMap c`` 37 The algorithm computes how many connected components are in the 38 graph, and assigns each component an integer label. The algorithm 39 then records to which component each vertex in the graph belongs by 40 recording the component number in the component property map. The 41 ``ComponentMap`` type must be a `Distributed Property Map`_. The 42 value type must be the ``vertices_size_type`` of the graph. The key 43 type must be the graph's vertex descriptor type. 44 45Complexity 46---------- 47 48*O(PN^2 + VNP)* work, in *O(N + V)* time, where N is the 49number of mappings and V is the number of local vertices. 50 51Algorithm Description 52--------------------- 53 54Every *N* th nodes starts a parallel search from the first vertex in 55their local vertex list during the first superstep (the other nodes 56remain idle during the first superstep to reduce the number of 57conflicts in numbering the components). At each superstep, all new 58component mappings from remote nodes are handled. If there is no work 59from remote updates, a new vertex is removed from the local list and 60added to the work queue. 61 62Components are allocated from the ``component_value_allocator`` 63object, which ensures that a given component number is unique in the 64system, currently by using the rank and number of processes to stride 65allocations. 66 67When two components are discovered to actually be the same component, 68a collision is recorded. The lower component number is prefered in 69the resolution, so component numbering resolution is consistent. 70After the search has exhausted all vertices in the graph, the mapping 71is shared with all processes and they independently resolve the 72comonent mapping. This phase can likely be significantly sped up if a 73clever algorithm for the reduction can be found. 74 75----------------------------------------------------------------------------- 76 77Copyright (C) 2009 The Trustees of Indiana University. 78 79Authors: Brian Barrett, Douglas Gregor, and Andrew Lumsdaine 80 81.. |Logo| image:: pbgl-logo.png 82 :align: middle 83 :alt: Parallel BGL 84 :target: http://www.osl.iu.edu/research/pbgl 85 86.. _Distributed Graph: DistributedGraph.html 87.. _Distributed Property Map: distributed_property_map.html 88.. _Incidence Graph: http://www.boost.org/libs/graph/doc/IncidenceGraph.html 89
