123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147 |
- <?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>
|