ceph/src/boost/libs/graph_parallel/doc/connected_components_parallel_search.rst

   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
  18 The ``connected_components_ps()`` function computes the connected
  19 components of a graph by performing a breadth-first search from
  20 several sources in parallel while recording and eventually resolving
  21 the collisions.
  22
  23 .. contents::
  24
  25 Where Defined
  26 -------------
  27 <``boost/graph/distributed/connected_components_parallel_search.hpp``>
  28
  29 Parameters
  30 ----------
  31
  32 IN:  ``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
  36 OUT:  ``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
  45 Complexity
  46 ----------
  47
  48 *O(PN^2 + VNP)* work, in *O(N + V)* time, where N is the
  49 number of mappings and V is the number of local vertices.
  50
  51 Algorithm Description
  52 ---------------------
  53
  54 Every *N* th nodes starts a parallel search from the first vertex in
  55 their local vertex list during the first superstep (the other nodes
  56 remain idle during the first superstep to reduce the number of
  57 conflicts in numbering the components).  At each superstep, all new
  58 component mappings from remote nodes are handled.  If there is no work
  59 from remote updates, a new vertex is removed from the local list and
  60 added to the work queue.
  61
  62 Components are allocated from the ``component_value_allocator``
  63 object, which ensures that a given component number is unique in the
  64 system, currently by using the rank and number of processes to stride
  65 allocations.
  66
  67 When two components are discovered to actually be the same component,
  68 a collision is recorded.  The lower component number is prefered in
  69 the resolution, so component numbering resolution is consistent.
  70 After the search has exhausted all vertices in the graph, the mapping
  71 is shared with all processes and they independently resolve the
  72 comonent mapping.  This phase can likely be significantly sped up if a
  73 clever algorithm for the reduction can be found.
  74
  75 -----------------------------------------------------------------------------
  76
  77 Copyright (C) 2009 The Trustees of Indiana University.
  78
  79 Authors: 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