.. Copyright (C) 2004-2008 The Trustees of Indiana University. Use, modification and distribution is subject to the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

=========================== |Logo| Connected Components

template<typename Graph, typename ComponentMap> inline typename property_traits<ComponentMap>::value_type strong_components( const Graph& g, ComponentMap c);

namespace graph { template<typename Graph, typename VertexComponentMap> void fleischer_hendrickson_pinar_strong_components(const Graph& g, VertexComponentMap r);

template<typename Graph, typename ReverseGraph, 
         typename ComponentMap, typename IsoMapFR, typename IsoMapRF>
inline typename property_traits<ComponentMap>::value_type
fleischer_hendrickson_pinar_strong_components(const Graph& g, 
                                              ComponentMap c,
                                              const ReverseGraph& gr, 
                                              IsoMapFR fr, IsoMapRF rf);

}

The strong_components() function computes the strongly connected components of a directed graph. The distributed strong components algorithm uses the sequential strong components_ algorithm to identify components local to a processor. The distributed portion of the algorithm is built on the distributed breadth first search_ algorithm and is based on the work of Fleischer, Hendrickson, and Pinar [FHP00]. The interface is a superset of the interface to the BGL sequential strong components algorithm. The number of strongly-connected components in the graph is returned to all processes.

The distributed strong components algorithm works on both directed and bidirectional graphs. In the bidirectional case, a reverse graph adapter is used to produce the required reverse graph. In the directed case, a separate graph is constructed in which all the edges are reversed.

.. contents::

Where Defined

<boost/graph/distributed/strong_components.hpp>

also accessible from

<boost/graph/strong_components.hpp>

Parameters

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 strongly 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.

UTIL: VertexComponentMap r The algorithm computes a mapping from each vertex to the representative of the strong component, stored in this property map. The VertexComponentMap type must be a Distributed Property Map_. The value and key types must be the vertex descriptor of the graph.

IN: const ReverseGraph& gr The reverse (or transpose) graph of g, such that for each directed edge (u, v) in g there exists a directed edge (fr(v), fr(u)) in gr and for each edge (v', u') in gr there exists an edge (rf(u'), rf(v')) in g. The functions fr and rf map from vertices in the graph to the reverse graph and vice-verse, and are represented as property map arguments. The concept requirements on this graph type are equivalent to those on the Graph type, but the types need not be the same.

Default: Either a reverse_graph adaptor over the original graph (if the graph type is bidirectional, i.e., models the Bidirectional Graph_ concept) or a distributed adjacency list_ constructed from the input graph.

IN: IsoMapFR fr A property map that maps from vertices in the input graph g to vertices in the reversed graph gr. The type IsoMapFR must model the Readable Property Map_ concept and have the graph's vertex descriptor as its key type and the reverse graph's vertex descriptor as its value type.

Default: An identity property map (if the graph type is bidirectional) or a distributed iterator_property_map (if the graph type is directed).

IN: IsoMapRF rf A property map that maps from vertices in the reversed graph gr to vertices in the input graph g. The type IsoMapRF must model the Readable Property Map_ concept and have the reverse graph's vertex descriptor as its key type and the graph's vertex descriptor as its value type.

Default: An identity property map (if the graph type is bidirectional) or a distributed iterator_property_map (if the graph type is directed).

Complexity

The local phase of the algorithm is O(V + E). The parallel phase of the algorithm requires at most O(V) supersteps each containing two breadth first searches which are O(V + E) each.

Algorithm Description

Prior to executing the sequential phase of the algorithm, each process identifies any completely local strong components which it labels and removes from the vertex set considered in the parallel phase of the algorithm.

The parallel phase of the distributed strong components algorithm consists of series of supersteps. Each superstep starts with one or more vertex sets which are guaranteed to completely contain any remaining strong components. A distributed breadth first search_ is performed starting from the first vertex in each vertex set. All of these breadth first searches are performed in parallel by having each processor call breadth_first_search() with a different starting vertex, and if necessary inserting additional vertices into the distributed queue used for breadth first search before invoking the algorithm. A second distributed breadth first search_ is performed on the reverse graph in the same fashion. For each initial vertex set, the successor set (the vertices reached in the forward breadth first search), and the predecessor set (the vertices reached in the backward breadth first search) is computed. The intersection of the predecessor and successor sets form a strongly connected component which is labeled as such. The remaining vertices in the initial vertex set are partitioned into three subsets each guaranteed to completely contain any remaining strong components. These three sets are the vertices in the predecessor set not contained in the identified strongly connected component, the vertices in the successor set not in the strongly connected component, and the remaing vertices in the initial vertex set not in the predecessor or successor sets. Once new vertex sets are identified, the algorithm begins a new superstep. The algorithm halts when no vertices remain.

To boost performance in sparse graphs when identifying small components, when less than a given portion of the initial number of vertices remain in active vertex sets, a filtered graph adapter is used to limit the graph seen by the breadth first search algorithm to the active vertices.

Bibliography

.. [FHP00] Lisa Fleischer, Bruce Hendrickson, and Ali Pinar. On Identifying Strongly Connected Components in Parallel. In Parallel and Distributed Processing (IPDPS), volume 1800 of Lecture Notes in Computer Science, pages 505--511, 2000. Springer.

Authors: Nick Edmonds, Douglas Gregor, and Andrew Lumsdaine

.. |Logo| image:: pbgl-logo.png :align: middle :alt: Parallel BGL :target: http://www.osl.iu.edu/research/pbgl

.. _Sequential strong components: http://www.boost.org/libs/graph/doc/strong_components.html .. _Distributed breadth first search: breadth_first_search.html .. _Distributed Graph: DistributedGraph.html .. _Distributed Property Map: distributed_property_map.html .. _Incidence Graph: http://www.boost.org/libs/graph/doc/IncidenceGraph.html .. _Bidirectional Graph: http://www.boost.org/libs/graph/doc/BidirectionalGraph.html .. _distributed adjacency list: distributed_adjacency_list.html .. _Readable Property Map: http://www.boost.org/libs/property_map/ReadablePropertyMap.html ..