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 Parallel Search</title> 8<link rel="stylesheet" href="../../../../rst.css" type="text/css" /> 9</head> 10<body> 11<div class="document" id="logo-connected-components-parallel-search"> 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 Parallel Search</h1> 13 14<!-- Copyright (C) 2004-2009 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 { namespace distributed { 20 template<typename Graph, typename ComponentMap> 21 typename property_traits<ComponentMap>::value_type 22 connected_components_ps(const Graph& g, ComponentMap c) 23} } 24</pre> 25<p>The <tt class="docutils literal"><span class="pre">connected_components_ps()</span></tt> function computes the connected 26components of a graph by performing a breadth-first search from 27several sources in parallel while recording and eventually resolving 28the collisions.</p> 29<div class="contents topic" id="contents"> 30<p class="topic-title first">Contents</p> 31<ul class="simple"> 32<li><a class="reference internal" href="#where-defined" id="id1">Where Defined</a></li> 33<li><a class="reference internal" href="#parameters" id="id2">Parameters</a></li> 34<li><a class="reference internal" href="#complexity" id="id3">Complexity</a></li> 35<li><a class="reference internal" href="#algorithm-description" id="id4">Algorithm Description</a></li> 36</ul> 37</div> 38<div class="section" id="where-defined"> 39<h1><a class="toc-backref" href="#id1">Where Defined</a></h1> 40<p><<tt class="docutils literal"><span class="pre">boost/graph/distributed/connected_components_parallel_search.hpp</span></tt>></p> 41</div> 42<div class="section" id="parameters"> 43<h1><a class="toc-backref" href="#id2">Parameters</a></h1> 44<dl class="docutils"> 45<dt>IN: <tt class="docutils literal"><span class="pre">const</span> <span class="pre">Graph&</span> <span class="pre">g</span></tt></dt> 46<dd>The graph type must be a model of <a class="reference external" href="DistributedGraph.html">Distributed Graph</a>. The graph 47type 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> 48<dt>OUT: <tt class="docutils literal"><span class="pre">ComponentMap</span> <span class="pre">c</span></tt></dt> 49<dd>The algorithm computes how many connected components are in the 50graph, and assigns each component an integer label. The algorithm 51then records to which component each vertex in the graph belongs by 52recording the component number in the component property map. The 53<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 54value type must be the <tt class="docutils literal"><span class="pre">vertices_size_type</span></tt> of the graph. The key 55type must be the graph's vertex descriptor type.</dd> 56</dl> 57</div> 58<div class="section" id="complexity"> 59<h1><a class="toc-backref" href="#id3">Complexity</a></h1> 60<p><em>O(PN^2 + VNP)</em> work, in <em>O(N + V)</em> time, where N is the 61number of mappings and V is the number of local vertices.</p> 62</div> 63<div class="section" id="algorithm-description"> 64<h1><a class="toc-backref" href="#id4">Algorithm Description</a></h1> 65<p>Every <em>N</em> th nodes starts a parallel search from the first vertex in 66their local vertex list during the first superstep (the other nodes 67remain idle during the first superstep to reduce the number of 68conflicts in numbering the components). At each superstep, all new 69component mappings from remote nodes are handled. If there is no work 70from remote updates, a new vertex is removed from the local list and 71added to the work queue.</p> 72<p>Components are allocated from the <tt class="docutils literal"><span class="pre">component_value_allocator</span></tt> 73object, which ensures that a given component number is unique in the 74system, currently by using the rank and number of processes to stride 75allocations.</p> 76<p>When two components are discovered to actually be the same component, 77a collision is recorded. The lower component number is prefered in 78the resolution, so component numbering resolution is consistent. 79After the search has exhausted all vertices in the graph, the mapping 80is shared with all processes and they independently resolve the 81comonent mapping. This phase can likely be significantly sped up if a 82clever algorithm for the reduction can be found.</p> 83<hr class="docutils" /> 84<p>Copyright (C) 2009 The Trustees of Indiana University.</p> 85<p>Authors: Brian Barrett, Douglas Gregor, and Andrew Lumsdaine</p> 86</div> 87</div> 88<div class="footer"> 89<hr class="footer" /> 90Generated on: 2009-05-31 00:21 UTC. 91Generated 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. 92 93</div> 94</body> 95</html> 96
