190 lines
13 KiB
HTML
190 lines
13 KiB
HTML
<?xml version="1.0" encoding="utf-8" ?>
|
|
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
|
|
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
|
|
<head>
|
|
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
|
|
<meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/" />
|
|
<title>Parallel BGL Connected Components</title>
|
|
<link rel="stylesheet" href="../../../../rst.css" type="text/css" />
|
|
</head>
|
|
<body>
|
|
<div class="document" id="logo-connected-components">
|
|
<h1 class="title"><a class="reference external" href="http://www.osl.iu.edu/research/pbgl"><img align="middle" alt="Parallel BGL" class="align-middle" src="pbgl-logo.png" /></a> Connected Components</h1>
|
|
|
|
<!-- 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) -->
|
|
<pre class="literal-block">
|
|
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);
|
|
}
|
|
</pre>
|
|
<p>The <tt class="docutils literal"><span class="pre">strong_components()</span></tt> function computes the strongly connected
|
|
components of a directed graph. The distributed strong components
|
|
algorithm uses the <a class="reference external" href="http://www.boost.org/libs/graph/doc/strong_components.html">sequential strong components</a> algorithm to
|
|
identify components local to a processor. The distributed portion of
|
|
the algorithm is built on the <a class="reference external" href="breadth_first_search.html">distributed breadth first search</a>
|
|
algorithm and is based on the work of Fleischer, Hendrickson, and
|
|
Pinar <a class="citation-reference" href="#fhp00" id="id1">[FHP00]</a>. The interface is a superset of the interface to the
|
|
BGL <a class="reference external" href="http://www.boost.org/libs/graph/doc/strong_components.html">sequential strong components</a> algorithm. The number of
|
|
strongly-connected components in the graph is returned to all
|
|
processes.</p>
|
|
<p>The distributed strong components algorithm works on both <tt class="docutils literal"><span class="pre">directed</span></tt>
|
|
and <tt class="docutils literal"><span class="pre">bidirectional</span></tt> 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.</p>
|
|
<div class="contents topic" id="contents">
|
|
<p class="topic-title first">Contents</p>
|
|
<ul class="simple">
|
|
<li><a class="reference internal" href="#where-defined" id="id2">Where Defined</a></li>
|
|
<li><a class="reference internal" href="#parameters" id="id3">Parameters</a></li>
|
|
<li><a class="reference internal" href="#complexity" id="id4">Complexity</a></li>
|
|
<li><a class="reference internal" href="#algorithm-description" id="id5">Algorithm Description</a></li>
|
|
<li><a class="reference internal" href="#bibliography" id="id6">Bibliography</a></li>
|
|
</ul>
|
|
</div>
|
|
<div class="section" id="where-defined">
|
|
<h1><a class="toc-backref" href="#id2">Where Defined</a></h1>
|
|
<p><<tt class="docutils literal"><span class="pre">boost/graph/distributed/strong_components.hpp</span></tt>></p>
|
|
<p>also accessible from</p>
|
|
<p><<tt class="docutils literal"><span class="pre">boost/graph/strong_components.hpp</span></tt>></p>
|
|
</div>
|
|
<div class="section" id="parameters">
|
|
<h1><a class="toc-backref" href="#id3">Parameters</a></h1>
|
|
<dl class="docutils">
|
|
<dt>IN: <tt class="docutils literal"><span class="pre">const</span> <span class="pre">Graph&</span> <span class="pre">g</span></tt></dt>
|
|
<dd>The graph type must be a model of <a class="reference external" href="DistributedGraph.html">Distributed Graph</a>. The graph
|
|
type must also model the <a class="reference external" href="http://www.boost.org/libs/graph/doc/IncidenceGraph.html">Incidence Graph</a> and be directed.</dd>
|
|
<dt>OUT: <tt class="docutils literal"><span class="pre">ComponentMap</span> <span class="pre">c</span></tt></dt>
|
|
<dd>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
|
|
<tt class="docutils literal"><span class="pre">ComponentMap</span></tt> type must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a>. The
|
|
value type must be the <tt class="docutils literal"><span class="pre">vertices_size_type</span></tt> of the graph. The key
|
|
type must be the graph's vertex descriptor type.</dd>
|
|
<dt>UTIL: <tt class="docutils literal"><span class="pre">VertexComponentMap</span> <span class="pre">r</span></tt></dt>
|
|
<dd>The algorithm computes a mapping from each vertex to the
|
|
representative of the strong component, stored in this property map.
|
|
The <tt class="docutils literal"><span class="pre">VertexComponentMap</span></tt> type must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a>.
|
|
The value and key types must be the vertex descriptor of the graph.</dd>
|
|
<dt>IN: <tt class="docutils literal"><span class="pre">const</span> <span class="pre">ReverseGraph&</span> <span class="pre">gr</span></tt></dt>
|
|
<dd><p class="first">The reverse (or transpose) graph of <tt class="docutils literal"><span class="pre">g</span></tt>, such that for each
|
|
directed edge <em>(u, v)</em> in <tt class="docutils literal"><span class="pre">g</span></tt> there exists a directed edge
|
|
<em>(fr(v), fr(u))</em> in <tt class="docutils literal"><span class="pre">gr</span></tt> and for each edge <em>(v', u')</em> in <em>gr</em>
|
|
there exists an edge <em>(rf(u'), rf(v'))</em> in <tt class="docutils literal"><span class="pre">g</span></tt>. The functions
|
|
<em>fr</em> and <em>rf</em> 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 <tt class="docutils literal"><span class="pre">Graph</span></tt> type, but the types need not be the same.</p>
|
|
<p class="last"><strong>Default</strong>: Either a <tt class="docutils literal"><span class="pre">reverse_graph</span></tt> adaptor over the original
|
|
graph (if the graph type is bidirectional, i.e., models the
|
|
<a class="reference external" href="http://www.boost.org/libs/graph/doc/BidirectionalGraph.html">Bidirectional Graph</a> concept) or a <a class="reference external" href="distributed_adjacency_list.html">distributed adjacency list</a>
|
|
constructed from the input graph.</p>
|
|
</dd>
|
|
<dt>IN: <tt class="docutils literal"><span class="pre">IsoMapFR</span> <span class="pre">fr</span></tt></dt>
|
|
<dd><p class="first">A property map that maps from vertices in the input graph <tt class="docutils literal"><span class="pre">g</span></tt> to
|
|
vertices in the reversed graph <tt class="docutils literal"><span class="pre">gr</span></tt>. The type <tt class="docutils literal"><span class="pre">IsoMapFR</span></tt> must
|
|
model the <a class="reference external" href="http://www.boost.org/libs/property_map/ReadablePropertyMap.html">Readable Property Map</a> concept and have the graph's
|
|
vertex descriptor as its key type and the reverse graph's vertex
|
|
descriptor as its value type.</p>
|
|
<p class="last"><strong>Default</strong>: An identity property map (if the graph type is
|
|
bidirectional) or a distributed <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> (if the
|
|
graph type is directed).</p>
|
|
</dd>
|
|
<dt>IN: <tt class="docutils literal"><span class="pre">IsoMapRF</span> <span class="pre">rf</span></tt></dt>
|
|
<dd><p class="first">A property map that maps from vertices in the reversed graph <tt class="docutils literal"><span class="pre">gr</span></tt>
|
|
to vertices in the input graph <tt class="docutils literal"><span class="pre">g</span></tt>. The type <tt class="docutils literal"><span class="pre">IsoMapRF</span></tt> must
|
|
model the <a class="reference external" href="http://www.boost.org/libs/property_map/ReadablePropertyMap.html">Readable Property Map</a> concept and have the reverse
|
|
graph's vertex descriptor as its key type and the graph's vertex
|
|
descriptor as its value type.</p>
|
|
<p class="last"><strong>Default</strong>: An identity property map (if the graph type is
|
|
bidirectional) or a distributed <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> (if the
|
|
graph type is directed).</p>
|
|
</dd>
|
|
</dl>
|
|
</div>
|
|
<div class="section" id="complexity">
|
|
<h1><a class="toc-backref" href="#id4">Complexity</a></h1>
|
|
<p>The local phase of the algorithm is <em>O(V + E)</em>. The parallel phase of
|
|
the algorithm requires at most <em>O(V)</em> supersteps each containing two
|
|
breadth first searches which are <em>O(V + E)</em> each.</p>
|
|
</div>
|
|
<div class="section" id="algorithm-description">
|
|
<h1><a class="toc-backref" href="#id5">Algorithm Description</a></h1>
|
|
<p>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.</p>
|
|
<p>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 <a class="reference external" href="breadth_first_search.html">distributed breadth first search</a>
|
|
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 <tt class="docutils literal"><span class="pre">breadth_first_search()</span></tt> with a different starting
|
|
vertex, and if necessary inserting additional vertices into the
|
|
<tt class="docutils literal"><span class="pre">distributed</span> <span class="pre">queue</span></tt> used for breadth first search before invoking
|
|
the algorithm. A second <a class="reference external" href="breadth_first_search.html">distributed breadth first search</a> 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.</p>
|
|
<p>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.</p>
|
|
</div>
|
|
<div class="section" id="bibliography">
|
|
<h1><a class="toc-backref" href="#id6">Bibliography</a></h1>
|
|
<table class="docutils citation" frame="void" id="fhp00" rules="none">
|
|
<colgroup><col class="label" /><col /></colgroup>
|
|
<tbody valign="top">
|
|
<tr><td class="label"><a class="fn-backref" href="#id1">[FHP00]</a></td><td>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.</td></tr>
|
|
</tbody>
|
|
</table>
|
|
<hr class="docutils" />
|
|
<p>Copyright (C) 2004, 2005 The Trustees of Indiana University.</p>
|
|
<p>Authors: Nick Edmonds, Douglas Gregor, and Andrew Lumsdaine</p>
|
|
<!-- -->
|
|
</div>
|
|
</div>
|
|
<div class="footer">
|
|
<hr class="footer" />
|
|
Generated on: 2009-05-31 00:21 UTC.
|
|
Generated by <a class="reference external" href="http://docutils.sourceforge.net/">Docutils</a> from <a class="reference external" href="http://docutils.sourceforge.net/rst.html">reStructuredText</a> source.
|
|
|
|
</div>
|
|
</body>
|
|
</html>
|