1<?xml version="1.0" encoding="utf-8" ?> 2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"> 4<head> 5<meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> 6<meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/" /> 7<title>Parallel BGL Connected Components</title> 8<link rel="stylesheet" href="../../../../rst.css" type="text/css" /> 9</head> 10<body> 11<div class="document" id="logo-connected-components"> 12<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> 13 14<!-- Copyright (C) 2004-2008 The Trustees of Indiana University. 15Use, modification and distribution is subject to the Boost Software 16License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 17http://www.boost.org/LICENSE_1_0.txt) --> 18<pre class="literal-block"> 19namespace graph { 20 // Default constructed ParentMap 21 template<typename Graph, typename ComponentMap, typename ParentMap> 22 typename property_traits<ComponentMap>::value_type 23 connected_components( const Graph& g, ComponentMap c); 24 25 // User supplied ParentMap 26 template<typename Graph, typename ComponentMap, typename ParentMap> 27 typename property_traits<ComponentMap>::value_type 28 connected_components( const Graph& g, ComponentMap c, ParentMap p); 29} 30</pre> 31<p>The <tt class="docutils literal"><span class="pre">connected_components()</span></tt> function computes the connected 32components of an undirected graph. The distributed connected 33components algorithm uses the sequential version of the connected 34components algorithm to compute the connected components of the local 35subgraph, then executes the parallel phase of the algorithm. The 36parallel portion of the connected components algorithm is loosely 37based on the work of Goddard, Kumar, and Prins. The interface is a 38superset of the interface to the BGL <a class="reference external" href="http://www.boost.org/libs/graph/doc/connected_components.html">sequential connected 39components</a> algorithm.</p> 40<p>Prior to executing the sequential phase of the algorithm, each process 41identifies the roots of its local components. An adjacency list of 42all vertices adjacent to members of the component is then constructed 43at the root vertex of each component.</p> 44<p>The parallel phase of the distributed connected components algorithm 45consists of a series of supersteps. In each superstep, each root 46attempts to hook to a member of it's adjacency list by assigning it's 47parent pointer to that vertex. Hooking is restricted to vertices 48which are logically less than the current vertex to prevent looping. 49Vertices which hook successfully are removed from the list of roots 50and placed on another list of completed vertices. All completed 51vertices now execute a pointer jumping step until every completed 52vertex has as its parent the root of a component. This pointer 53jumping step may be further optimized by the addition of Cycle 54Reduction (CR) rules developed by Johnson and Metaxas, however current 55performance evaluations indicate that this would have a negligible 56impact on the overall performance of the algorithm. These CR rules 57reduce the number of pointer jumping steps from <em>O(n)</em> to <em>O(log n)</em>. 58Following this pointer jumping step, roots which have hooked in this 59phase transmit their adjacency list to their new parent. The 60remaining roots receive these edges and execute a pruning step on 61their adjacency lists to remove vertices that are now members of their 62component. The parallel phase of the algorithm is complete when no 63root successfully hooks. Once the parallel phase is complete a final 64pointer jumping step is performed on all vertices to assign the parent 65pointers of the leaves of the initial local subgraph components to 66their final parent which has now been determined.</p> 67<p>The single largest performance bottleneck in the distributed connected 68components algorithm is the effect of poor vertex distribution on the 69algorithm. For sparse graphs with a single large component, many 70roots may hook to the same component, resulting in severe load 71imbalance at the process owning this component. Several methods of 72modifying the hooking strategy to avoid this behavior have been 73implemented but none has been successful as of yet.</p> 74<div class="contents topic" id="contents"> 75<p class="topic-title first">Contents</p> 76<ul class="simple"> 77<li><a class="reference internal" href="#where-defined" id="id1">Where Defined</a></li> 78<li><a class="reference internal" href="#parameters" id="id2">Parameters</a></li> 79<li><a class="reference internal" href="#complexity" id="id3">Complexity</a></li> 80<li><a class="reference internal" href="#performance" id="id4">Performance</a></li> 81</ul> 82</div> 83<div class="section" id="where-defined"> 84<h1><a class="toc-backref" href="#id1">Where Defined</a></h1> 85<p><<tt class="docutils literal"><span class="pre">boost/graph/connected_components.hpp</span></tt>></p> 86</div> 87<div class="section" id="parameters"> 88<h1><a class="toc-backref" href="#id2">Parameters</a></h1> 89<dl class="docutils"> 90<dt>IN: <tt class="docutils literal"><span class="pre">Graph&</span> <span class="pre">g</span></tt></dt> 91<dd>The graph typed must be a model of <a class="reference external" href="DistributedGraph.html">Distributed Graph</a>.</dd> 92<dt>OUT: <tt class="docutils literal"><span class="pre">ComponentMap</span> <span class="pre">c</span></tt></dt> 93<dd>The algorithm computes how many connected components are in the 94graph, and assigns each component an integer label. The algorithm 95then records to which component each vertex in the graph belongs by 96recording the component number in the component property map. The 97<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 98value type must be the <tt class="docutils literal"><span class="pre">vertices_size_type</span></tt> of the graph. The key 99type must be the graph's vertex descriptor type. If you do not wish 100to compute component numbers, pass <tt class="docutils literal"><span class="pre">dummy_property_map</span></tt> as the 101component map and parent information will be provided in the parent 102map.</dd> 103<dt>UTIL: <tt class="docutils literal"><span class="pre">ParentMap</span> <span class="pre">p</span></tt></dt> 104<dd>A parent map may be supplied to the algorithm, if not supplied the 105parent map will be constructed automatically. The <tt class="docutils literal"><span class="pre">ParentMap</span></tt> type 106must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a>. The value type and key type 107must be the graph's vertex descriptor type.</dd> 108<dt>OUT: <tt class="docutils literal"><span class="pre">property_traits<ComponentMap>::value_type</span></tt></dt> 109<dd>The number of components found will be returned as the value type of 110the component map.</dd> 111</dl> 112</div> 113<div class="section" id="complexity"> 114<h1><a class="toc-backref" href="#id3">Complexity</a></h1> 115<p>The local phase of the algorithm is <em>O(V + E)</em>. The parallel phase of 116the algorithm requires at most <em>O(d)</em> supersteps where <em>d</em> is the 117number of initial roots. <em>d</em> is at most <em>O(V)</em> but becomes 118significantly smaller as <em>E</em> increases. The pointer jumping phase 119within each superstep requires at most <em>O(c)</em> steps on each of the 120completed roots where <em>c</em> is the length of the longest cycle. 121Application of CR rules can reduce this to <em>O(log c)</em>.</p> 122</div> 123<div class="section" id="performance"> 124<h1><a class="toc-backref" href="#id4">Performance</a></h1> 125<p>The following charts illustrate the performance of the Parallel BGL 126connected components algorithm. It performs well on very sparse and 127very dense graphs. However, for cases where the graph has a medium 128density with a giant connected component, the algorithm will perform 129poorly. This is a known problem with the algorithm and as far as we 130know all implemented algorithms have this degenerate behavior.</p> 131<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" /> 132<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" /> 133<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" /> 134<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" /> 135<hr class="docutils" /> 136<p>Copyright (C) 2004 The Trustees of Indiana University.</p> 137<p>Authors: Nick Edmonds, Douglas Gregor, and Andrew Lumsdaine</p> 138</div> 139</div> 140<div class="footer"> 141<hr class="footer" /> 142Generated on: 2009-05-31 00:22 UTC. 143Generated 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. 144 145</div> 146</body> 147</html> 148
