ceph/src/boost/libs/graph_parallel/doc/html/connected_components.html

   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.
  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 {
  20   // Default constructed ParentMap
  21   template&lt;typename Graph, typename ComponentMap, typename ParentMap&gt;
  22   typename property_traits&lt;ComponentMap&gt;::value_type
  23   connected_components( const Graph&amp; g, ComponentMap c);
  24
  25   // User supplied ParentMap
  26   template&lt;typename Graph, typename ComponentMap, typename ParentMap&gt;
  27   typename property_traits&lt;ComponentMap&gt;::value_type
  28   connected_components( const Graph&amp; 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
  32 components of an undirected graph.  The distributed connected
  33 components algorithm uses the sequential version of the connected
  34 components algorithm to compute the connected components of the local
  35 subgraph, then executes the parallel phase of the algorithm.  The
  36 parallel portion of the connected components algorithm is loosely
  37 based on the work of Goddard, Kumar, and Prins. The interface is a
  38 superset of the interface to the BGL <a class="reference external" href="http://www.boost.org/libs/graph/doc/connected_components.html">sequential connected
  39 components</a> algorithm.</p>
  40 <p>Prior to executing the sequential phase of the algorithm, each process
  41 identifies the roots of its local components.  An adjacency list of
  42 all vertices adjacent to members of the component is then constructed
  43 at the root vertex of each component.</p>
  44 <p>The parallel phase of the distributed connected components algorithm
  45 consists of a series of supersteps.  In each superstep, each root
  46 attempts to hook to a member of it's adjacency list by assigning it's
  47 parent pointer to that vertex.  Hooking is restricted to vertices
  48 which are logically less than the current vertex to prevent looping.
  49 Vertices which hook successfully are removed from the list of roots
  50 and placed on another list of completed vertices.  All completed
  51 vertices now execute a pointer jumping step until every completed
  52 vertex has as its parent the root of a component.  This pointer
  53 jumping step may be further optimized by the addition of Cycle
  54 Reduction (CR) rules developed by Johnson and Metaxas, however current
  55 performance evaluations indicate that this would have a negligible
  56 impact on the overall performance of the algorithm.  These CR rules
  57 reduce the number of pointer jumping steps from <em>O(n)</em> to <em>O(log n)</em>.
  58 Following this pointer jumping step, roots which have hooked in this
  59 phase transmit their adjacency list to their new parent.  The
  60 remaining roots receive these edges and execute a pruning step on
  61 their adjacency lists to remove vertices that are now members of their
  62 component.  The parallel phase of the algorithm is complete when no
  63 root successfully hooks.  Once the parallel phase is complete a final
  64 pointer jumping step is performed on all vertices to assign the parent
  65 pointers of the leaves of the initial local subgraph components to
  66 their final parent which has now been determined.</p>
  67 <p>The single largest performance bottleneck in the distributed connected
  68 components algorithm is the effect of poor vertex distribution on the
  69 algorithm.  For sparse graphs with a single large component, many
  70 roots may hook to the same component, resulting in severe load
  71 imbalance at the process owning this component.  Several methods of
  72 modifying the hooking strategy to avoid this behavior have been
  73 implemented 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>&lt;<tt class="docutils literal"><span class="pre">boost/graph/connected_components.hpp</span></tt>&gt;</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&amp;</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
  94 graph, and assigns each component an integer label.  The algorithm
  95 then records to which component each vertex in the graph belongs by
  96 recording 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
  98 value type must be the <tt class="docutils literal"><span class="pre">vertices_size_type</span></tt> of the graph.  The key
  99 type must be the graph's vertex descriptor type. If you do not wish
 100 to compute component numbers, pass <tt class="docutils literal"><span class="pre">dummy_property_map</span></tt> as the
 101 component map and parent information will be provided in the parent
 102 map.</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
 105 parent map will be constructed automatically.  The <tt class="docutils literal"><span class="pre">ParentMap</span></tt> type
 106 must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a>.  The value type and key type
 107 must be the graph's vertex descriptor type.</dd>
 108 <dt>OUT:  <tt class="docutils literal"><span class="pre">property_traits&lt;ComponentMap&gt;::value_type</span></tt></dt>
 109 <dd>The number of components found will be returned as the value type of
 110 the 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
 116 the algorithm requires at most <em>O(d)</em> supersteps where <em>d</em> is the
 117 number of initial roots.  <em>d</em> is at most <em>O(V)</em> but becomes
 118 significantly smaller as <em>E</em> increases.  The pointer jumping phase
 119 within each superstep requires at most <em>O(c)</em> steps on each of the
 120 completed roots where <em>c</em> is the length of the longest cycle.
 121 Application 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
 126 connected components algorithm. It performs well on very sparse and
 127 very dense graphs. However, for cases where the graph has a medium
 128 density with a giant connected component, the algorithm will perform
 129 poorly. This is a known problem with the algorithm and as far as we
 130 know 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" />
 142 Generated on: 2009-05-31 00:22 UTC.
 143 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.
 144
 145 </div>
 146 </body>
 147 </html>