148 lines
9.3 KiB
HTML
148 lines
9.3 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">
|
|
namespace graph {
|
|
// Default constructed ParentMap
|
|
template<typename Graph, typename ComponentMap, typename ParentMap>
|
|
typename property_traits<ComponentMap>::value_type
|
|
connected_components( const Graph& g, ComponentMap c);
|
|
|
|
// User supplied ParentMap
|
|
template<typename Graph, typename ComponentMap, typename ParentMap>
|
|
typename property_traits<ComponentMap>::value_type
|
|
connected_components( const Graph& g, ComponentMap c, ParentMap p);
|
|
}
|
|
</pre>
|
|
<p>The <tt class="docutils literal"><span class="pre">connected_components()</span></tt> function computes the connected
|
|
components of an undirected graph. The distributed connected
|
|
components algorithm uses the sequential version of the connected
|
|
components algorithm to compute the connected components of the local
|
|
subgraph, then executes the parallel phase of the algorithm. The
|
|
parallel portion of the connected components algorithm is loosely
|
|
based on the work of Goddard, Kumar, and Prins. The interface is a
|
|
superset of the interface to the BGL <a class="reference external" href="http://www.boost.org/libs/graph/doc/connected_components.html">sequential connected
|
|
components</a> algorithm.</p>
|
|
<p>Prior to executing the sequential phase of the algorithm, each process
|
|
identifies the roots of its local components. An adjacency list of
|
|
all vertices adjacent to members of the component is then constructed
|
|
at the root vertex of each component.</p>
|
|
<p>The parallel phase of the distributed connected components algorithm
|
|
consists of a series of supersteps. In each superstep, each root
|
|
attempts to hook to a member of it's adjacency list by assigning it's
|
|
parent pointer to that vertex. Hooking is restricted to vertices
|
|
which are logically less than the current vertex to prevent looping.
|
|
Vertices which hook successfully are removed from the list of roots
|
|
and placed on another list of completed vertices. All completed
|
|
vertices now execute a pointer jumping step until every completed
|
|
vertex has as its parent the root of a component. This pointer
|
|
jumping step may be further optimized by the addition of Cycle
|
|
Reduction (CR) rules developed by Johnson and Metaxas, however current
|
|
performance evaluations indicate that this would have a negligible
|
|
impact on the overall performance of the algorithm. These CR rules
|
|
reduce the number of pointer jumping steps from <em>O(n)</em> to <em>O(log n)</em>.
|
|
Following this pointer jumping step, roots which have hooked in this
|
|
phase transmit their adjacency list to their new parent. The
|
|
remaining roots receive these edges and execute a pruning step on
|
|
their adjacency lists to remove vertices that are now members of their
|
|
component. The parallel phase of the algorithm is complete when no
|
|
root successfully hooks. Once the parallel phase is complete a final
|
|
pointer jumping step is performed on all vertices to assign the parent
|
|
pointers of the leaves of the initial local subgraph components to
|
|
their final parent which has now been determined.</p>
|
|
<p>The single largest performance bottleneck in the distributed connected
|
|
components algorithm is the effect of poor vertex distribution on the
|
|
algorithm. For sparse graphs with a single large component, many
|
|
roots may hook to the same component, resulting in severe load
|
|
imbalance at the process owning this component. Several methods of
|
|
modifying the hooking strategy to avoid this behavior have been
|
|
implemented but none has been successful as of yet.</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="id1">Where Defined</a></li>
|
|
<li><a class="reference internal" href="#parameters" id="id2">Parameters</a></li>
|
|
<li><a class="reference internal" href="#complexity" id="id3">Complexity</a></li>
|
|
<li><a class="reference internal" href="#performance" id="id4">Performance</a></li>
|
|
</ul>
|
|
</div>
|
|
<div class="section" id="where-defined">
|
|
<h1><a class="toc-backref" href="#id1">Where Defined</a></h1>
|
|
<p><<tt class="docutils literal"><span class="pre">boost/graph/connected_components.hpp</span></tt>></p>
|
|
</div>
|
|
<div class="section" id="parameters">
|
|
<h1><a class="toc-backref" href="#id2">Parameters</a></h1>
|
|
<dl class="docutils">
|
|
<dt>IN: <tt class="docutils literal"><span class="pre">Graph&</span> <span class="pre">g</span></tt></dt>
|
|
<dd>The graph typed must be a model of <a class="reference external" href="DistributedGraph.html">Distributed Graph</a>.</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 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. If you do not wish
|
|
to compute component numbers, pass <tt class="docutils literal"><span class="pre">dummy_property_map</span></tt> as the
|
|
component map and parent information will be provided in the parent
|
|
map.</dd>
|
|
<dt>UTIL: <tt class="docutils literal"><span class="pre">ParentMap</span> <span class="pre">p</span></tt></dt>
|
|
<dd>A parent map may be supplied to the algorithm, if not supplied the
|
|
parent map will be constructed automatically. The <tt class="docutils literal"><span class="pre">ParentMap</span></tt> type
|
|
must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a>. The value type and key type
|
|
must be the graph's vertex descriptor type.</dd>
|
|
<dt>OUT: <tt class="docutils literal"><span class="pre">property_traits<ComponentMap>::value_type</span></tt></dt>
|
|
<dd>The number of components found will be returned as the value type of
|
|
the component map.</dd>
|
|
</dl>
|
|
</div>
|
|
<div class="section" id="complexity">
|
|
<h1><a class="toc-backref" href="#id3">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(d)</em> supersteps where <em>d</em> is the
|
|
number of initial roots. <em>d</em> is at most <em>O(V)</em> but becomes
|
|
significantly smaller as <em>E</em> increases. The pointer jumping phase
|
|
within each superstep requires at most <em>O(c)</em> steps on each of the
|
|
completed roots where <em>c</em> is the length of the longest cycle.
|
|
Application of CR rules can reduce this to <em>O(log c)</em>.</p>
|
|
</div>
|
|
<div class="section" id="performance">
|
|
<h1><a class="toc-backref" href="#id4">Performance</a></h1>
|
|
<p>The following charts illustrate the performance of the Parallel BGL
|
|
connected components algorithm. It performs well on very sparse and
|
|
very dense graphs. However, for cases where the graph has a medium
|
|
density with a giant connected component, the algorithm will perform
|
|
poorly. This is a known problem with the algorithm and as far as we
|
|
know all implemented algorithms have this degenerate behavior.</p>
|
|
<img align="left" alt="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_9.png" class="align-left" src="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_9.png" />
|
|
<img alt="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_9_speedup_1.png" src="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_9_speedup_1.png" />
|
|
<img align="left" alt="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_9.png" class="align-left" src="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_9.png" />
|
|
<img alt="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_9_speedup_1.png" src="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_9_speedup_1.png" />
|
|
<hr class="docutils" />
|
|
<p>Copyright (C) 2004 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:22 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>
|