123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190 |
- .. 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.
- -----------------------------------------------------------------------------
- Copyright (C) 2004, 2005 The Trustees of Indiana University.
- 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
- ..
|