[ceph.git] / ceph / src / boost / libs / graph_parallel / doc / html / connected_components_parallel_search.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 Parallel Search</title>
<link rel="stylesheet" href="../../../../rst.css" type="text/css" />
</head>
<body>
<div class="document" id="logo-connected-components-parallel-search">
<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>

<!-- Copyright (C) 2004-2009 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 { namespace distributed {
  template&lt;typename Graph, typename ComponentMap&gt;
  typename property_traits&lt;ComponentMap&gt;::value_type
  connected_components_ps(const Graph&amp; g, ComponentMap c)
} }
</pre>
<p>The <tt class="docutils literal"><span class="pre">connected_components_ps()</span></tt> function computes the connected
components of a graph by performing a breadth-first search from
several sources in parallel while recording and eventually resolving
the collisions.</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="#algorithm-description" id="id4">Algorithm Description</a></li>
</ul>
</div>
<div class="section" id="where-defined">
<h1><a class="toc-backref" href="#id1">Where Defined</a></h1>
<p>&lt;<tt class="docutils literal"><span class="pre">boost/graph/distributed/connected_components_parallel_search.hpp</span></tt>&gt;</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">const</span> <span class="pre">Graph&amp;</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 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>
</dl>
</div>
<div class="section" id="complexity">
<h1><a class="toc-backref" href="#id3">Complexity</a></h1>
<p><em>O(PN^2 + VNP)</em> work, in <em>O(N + V)</em> time, where N is the
number of mappings and V is the number of local vertices.</p>
</div>
<div class="section" id="algorithm-description">
<h1><a class="toc-backref" href="#id4">Algorithm Description</a></h1>
<p>Every <em>N</em> th nodes starts a parallel search from the first vertex in
their local vertex list during the first superstep (the other nodes
remain idle during the first superstep to reduce the number of
conflicts in numbering the components).  At each superstep, all new
component mappings from remote nodes are handled.  If there is no work
from remote updates, a new vertex is removed from the local list and
added to the work queue.</p>
<p>Components are allocated from the <tt class="docutils literal"><span class="pre">component_value_allocator</span></tt>
object, which ensures that a given component number is unique in the
system, currently by using the rank and number of processes to stride
allocations.</p>
<p>When two components are discovered to actually be the same component,
a collision is recorded.  The lower component number is prefered in
the resolution, so component numbering resolution is consistent.
After the search has exhausted all vertices in the graph, the mapping
is shared with all processes and they independently resolve the
comonent mapping.  This phase can likely be significantly sped up if a
clever algorithm for the reduction can be found.</p>
<hr class="docutils" />
<p>Copyright (C) 2009 The Trustees of Indiana University.</p>
<p>Authors: Brian Barrett, 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>
Commit	Line	Data
7c673cae FG	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.
	15	Use, modification and distribution is subject to the Boost Software
	16	License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
	17	http://www.boost.org/LICENSE_1_0.txt) -->
	18	<pre class="literal-block">
	19	namespace 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
	26	components of a graph by performing a breadth-first search from
	27	several sources in parallel while recording and eventually resolving
	28	the 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
	47	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>
	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
	50	graph, and assigns each component an integer label. The algorithm
	51	then records to which component each vertex in the graph belongs by
	52	recording 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
	54	value type must be the <tt class="docutils literal"><span class="pre">vertices_size_type</span></tt> of the graph. The key
	55	type 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
	61	number 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
66	their local vertex list during the first superstep (the other nodes
67	remain idle during the first superstep to reduce the number of
68	conflicts in numbering the components). At each superstep, all new
69	component mappings from remote nodes are handled. If there is no work
70	from remote updates, a new vertex is removed from the local list and
71	added to the work queue.</p>
72	<p>Components are allocated from the <tt class="docutils literal"><span class="pre">component_value_allocator</span></tt>
73	object, which ensures that a given component number is unique in the
74	system, currently by using the rank and number of processes to stride
75	allocations.</p>
76	<p>When two components are discovered to actually be the same component,
77	a collision is recorded. The lower component number is prefered in
78	the resolution, so component numbering resolution is consistent.
79	After the search has exhausted all vertices in the graph, the mapping
80	is shared with all processes and they independently resolve the
81	comonent mapping. This phase can likely be significantly sped up if a
82	clever 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" />
90	Generated on: 2009-05-31 00:21 UTC.
91	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.
92
93	</div>
94	</body>
95	</html>