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 30The ``strong_components()`` function computes the strongly connected 31components of a directed graph. The distributed strong components 32algorithm uses the `sequential strong components`_ algorithm to 33identify components local to a processor. The distributed portion of 34the algorithm is built on the `distributed breadth first search`_ 35algorithm and is based on the work of Fleischer, Hendrickson, and 36Pinar [FHP00]_. The interface is a superset of the interface to the 37BGL `sequential strong components`_ algorithm. The number of 38strongly-connected components in the graph is returned to all 39processes. 40 41The distributed strong components algorithm works on both ``directed`` 42and ``bidirectional`` graphs. In the bidirectional case, a reverse 43graph adapter is used to produce the required reverse graph. In 44the directed case, a separate graph is constructed in which all the 45edges are reversed. 46 47.. contents:: 48 49Where Defined 50------------- 51<``boost/graph/distributed/strong_components.hpp``> 52 53also accessible from 54 55<``boost/graph/strong_components.hpp``> 56 57Parameters 58---------- 59 60IN: ``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 64OUT: ``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 73UTIL: ``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 79IN: ``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 94IN: ``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 105IN: ``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 116Complexity 117---------- 118 119The local phase of the algorithm is *O(V + E)*. The parallel phase of 120the algorithm requires at most *O(V)* supersteps each containing two 121breadth first searches which are *O(V + E)* each. 122 123 124Algorithm Description 125--------------------- 126 127Prior to executing the sequential phase of the algorithm, each process 128identifies any completely local strong components which it labels and 129removes from the vertex set considered in the parallel phase of the 130algorithm. 131 132The parallel phase of the distributed strong components algorithm 133consists of series of supersteps. Each superstep starts with one 134or more vertex sets which are guaranteed to completely contain 135any remaining strong components. A `distributed breadth first search`_ 136is performed starting from the first vertex in each vertex set. 137All of these breadth first searches are performed in parallel by having 138each processor call ``breadth_first_search()`` with a different starting 139vertex, and if necessary inserting additional vertices into the 140``distributed queue`` used for breadth first search before invoking 141the algorithm. A second `distributed breadth first search`_ is 142performed on the reverse graph in the same fashion. For each initial 143vertex set, the successor set (the vertices reached in the forward 144breadth first search), and the predecessor set (the vertices reached 145in the backward breadth first search) is computed. The intersection 146of the predecessor and successor sets form a strongly connected 147component which is labeled as such. The remaining vertices in the 148initial vertex set are partitioned into three subsets each guaranteed 149to completely contain any remaining strong components. These three sets 150are the vertices in the predecessor set not contained in the identified 151strongly connected component, the vertices in the successor set not 152in the strongly connected component, and the remaing vertices in the 153initial vertex set not in the predecessor or successor sets. Once 154new vertex sets are identified, the algorithm begins a new superstep. 155The algorithm halts when no vertices remain. 156 157To boost performance in sparse graphs when identifying small components, 158when less than a given portion of the initial number of vertices 159remain in active vertex sets, a filtered graph adapter is used 160to limit the graph seen by the breadth first search algorithm to the 161active vertices. 162 163Bibliography 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 173Copyright (C) 2004, 2005 The Trustees of Indiana University. 174 175Authors: 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.. 191
