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

   1 .. Copyright (C) 2004-2008 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
   8 ===========================
   9
  10 ::
  11
  12   template<typename Graph, typename ComponentMap>
  13   inline typename property_traits<ComponentMap>::value_type
  14   strong_components( const Graph& g, ComponentMap c);
  15
  16   namespace graph {
  17     template<typename Graph, typename VertexComponentMap>
  18     void
  19     fleischer_hendrickson_pinar_strong_components(const Graph& g, VertexComponentMap r);
  20
  21     template<typename Graph, typename ReverseGraph,
  22              typename ComponentMap, typename IsoMapFR, typename IsoMapRF>
  23     inline typename property_traits<ComponentMap>::value_type
  24     fleischer_hendrickson_pinar_strong_components(const Graph& g,
  25                                                   ComponentMap c,
  26                                                   const ReverseGraph& gr,
  27                                                   IsoMapFR fr, IsoMapRF rf);
  28   }
  29
  30 The ``strong_components()`` function computes the strongly connected
  31 components of a directed graph.  The distributed strong components
  32 algorithm uses the `sequential strong components`_ algorithm to
  33 identify components local to a processor.  The distributed portion of
  34 the algorithm is built on the `distributed breadth first search`_
  35 algorithm and is based on the work of Fleischer, Hendrickson, and
  36 Pinar [FHP00]_. The interface is a superset of the interface to the
  37 BGL `sequential strong components`_ algorithm. The number of
  38 strongly-connected components in the graph is returned to all
  39 processes.
  40
  41 The distributed strong components algorithm works on both ``directed``
  42 and ``bidirectional`` graphs.  In the bidirectional case, a reverse
  43 graph adapter is used to produce the required reverse graph.  In
  44 the directed case, a separate graph is constructed in which all the
  45 edges are reversed.
  46
  47 .. contents::
  48
  49 Where Defined
  50 -------------
  51 <``boost/graph/distributed/strong_components.hpp``>
  52
  53 also accessible from
  54
  55 <``boost/graph/strong_components.hpp``>
  56
  57 Parameters
  58 ----------
  59
  60 IN:  ``const Graph& g``
  61   The graph type must be a model of `Distributed Graph`_.  The graph
  62   type must also model the `Incidence Graph`_ and be directed.
  63
  64 OUT:  ``ComponentMap c``
  65   The algorithm computes how many strongly connected components are in the
  66   graph, and assigns each component an integer label.  The algorithm
  67   then records to which component each vertex in the graph belongs by
  68   recording the component number in the component property map.  The
  69   ``ComponentMap`` type must be a `Distributed Property Map`_.  The
  70   value type must be the ``vertices_size_type`` of the graph.  The key
  71   type must be the graph's vertex descriptor type.
  72
  73 UTIL:  ``VertexComponentMap r``
  74   The algorithm computes a mapping from each vertex to the
  75   representative of the strong component, stored in this property map.
  76   The ``VertexComponentMap`` type must be a `Distributed Property Map`_.
  77   The value and key types must be the vertex descriptor of the graph.
  78
  79 IN: ``const ReverseGraph& gr``
  80   The reverse (or transpose) graph of ``g``, such that for each
  81   directed edge *(u, v)* in ``g`` there exists a directed edge
  82   *(fr(v), fr(u))* in ``gr`` and for each edge *(v', u')* in *gr*
  83   there exists an edge *(rf(u'), rf(v'))* in ``g``. The functions
  84   *fr* and *rf* map from vertices in the graph to the reverse graph
  85   and vice-verse, and are represented as property map arguments. The
  86   concept requirements on this graph type are equivalent to those on
  87   the ``Graph`` type, but the types need not be the same.
  88
  89   **Default**: Either a ``reverse_graph`` adaptor over the original
  90   graph (if the graph type is bidirectional, i.e., models the
  91   `Bidirectional Graph`_ concept) or a `distributed adjacency list`_
  92   constructed from the input graph.
  93
  94 IN: ``IsoMapFR fr``
  95   A property map that maps from vertices in the input graph ``g`` to
  96   vertices in the reversed graph ``gr``. The type ``IsoMapFR`` must
  97   model the `Readable Property Map`_ concept and have the graph's
  98   vertex descriptor as its key type and the reverse graph's vertex
  99   descriptor as its value type.
 100
 101   **Default**: An identity property map (if the graph type is
 102   bidirectional) or a distributed ``iterator_property_map`` (if the
 103   graph type is directed).
 104
 105 IN: ``IsoMapRF rf``
 106   A property map that maps from vertices in the reversed graph ``gr``
 107   to vertices in the input graph ``g``. The type ``IsoMapRF`` must
 108   model the `Readable Property Map`_ concept and have the reverse
 109   graph's vertex descriptor as its key type and the graph's vertex
 110   descriptor as its value type.
 111
 112   **Default**: An identity property map (if the graph type is
 113   bidirectional) or a distributed ``iterator_property_map`` (if the
 114   graph type is directed).
 115
 116 Complexity
 117 ----------
 118
 119 The local phase of the algorithm is *O(V + E)*.  The parallel phase of
 120 the algorithm requires at most *O(V)* supersteps each containing two
 121 breadth first searches which are *O(V + E)* each.
 122
 123
 124 Algorithm Description
 125 ---------------------
 126
 127 Prior to executing the sequential phase of the algorithm, each process
 128 identifies any completely local strong components which it labels and
 129 removes from the vertex set considered in the parallel phase of the
 130 algorithm.
 131
 132 The parallel phase of the distributed strong components algorithm
 133 consists of series of supersteps.  Each superstep starts with one
 134 or more vertex sets which are guaranteed to completely contain
 135 any remaining strong components.  A `distributed breadth first search`_
 136 is performed starting from the first vertex in each vertex set.
 137 All of these breadth first searches are performed in parallel by having
 138 each processor call ``breadth_first_search()`` with a different starting
 139 vertex, and if necessary inserting additional vertices into the
 140 ``distributed queue`` used for breadth first search before invoking
 141 the algorithm.  A second `distributed breadth first search`_ is
 142 performed on the reverse graph in the same fashion.  For each initial
 143 vertex set, the successor set (the vertices reached in the forward
 144 breadth first search), and the predecessor set (the vertices reached
 145 in the backward breadth first search) is computed.  The intersection
 146 of the predecessor and successor sets form a strongly connected
 147 component which is labeled as such.  The remaining vertices in the
 148 initial vertex set are partitioned into three subsets each guaranteed
 149 to completely contain any remaining strong components.  These three sets
 150 are the vertices in the predecessor set not contained in the identified
 151 strongly connected component, the vertices in the successor set not
 152 in the strongly connected component, and the remaing vertices in the
 153 initial vertex set not in the predecessor or successor sets.  Once
 154 new vertex sets are identified, the algorithm begins a new superstep.
 155 The algorithm halts when no vertices remain.
 156
 157 To boost performance in sparse graphs when identifying small components,
 158 when less than a given portion of the initial number of vertices
 159 remain in active vertex sets, a filtered graph adapter is used
 160 to limit the graph seen by the breadth first search algorithm to the
 161 active vertices.
 162
 163 Bibliography
 164 ------------
 165
 166 .. [FHP00] Lisa Fleischer, Bruce Hendrickson, and Ali Pinar. On
 167   Identifying Strongly Connected Components in Parallel. In Parallel and
 168   Distributed Processing (IPDPS), volume 1800 of Lecture Notes in
 169   Computer Science, pages 505--511, 2000. Springer.
 170
 171 -----------------------------------------------------------------------------
 172
 173 Copyright (C) 2004, 2005 The Trustees of Indiana University.
 174
 175 Authors: Nick Edmonds, Douglas Gregor, and Andrew Lumsdaine
 176
 177 .. |Logo| image:: pbgl-logo.png
 178             :align: middle
 179             :alt: Parallel BGL
 180             :target: http://www.osl.iu.edu/research/pbgl
 181
 182 .. _Sequential strong components: http://www.boost.org/libs/graph/doc/strong_components.html
 183 .. _Distributed breadth first search: breadth_first_search.html
 184 .. _Distributed Graph: DistributedGraph.html
 185 .. _Distributed Property Map: distributed_property_map.html
 186 .. _Incidence Graph: http://www.boost.org/libs/graph/doc/IncidenceGraph.html
 187 .. _Bidirectional Graph: http://www.boost.org/libs/graph/doc/BidirectionalGraph.html
 188 .. _distributed adjacency list: distributed_adjacency_list.html
 189 .. _Readable Property Map: http://www.boost.org/libs/property_map/ReadablePropertyMap.html
 190 ..