ceph/src/boost/libs/graph_parallel/doc/html/strong_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 template&lt;typename Graph, typename ComponentMap&gt;
  20 inline typename property_traits&lt;ComponentMap&gt;::value_type
  21 strong_components( const Graph&amp; g, ComponentMap c);
  22
  23 namespace graph {
  24   template&lt;typename Graph, typename VertexComponentMap&gt;
  25   void
  26   fleischer_hendrickson_pinar_strong_components(const Graph&amp; g, VertexComponentMap r);
  27
  28   template&lt;typename Graph, typename ReverseGraph,
  29            typename ComponentMap, typename IsoMapFR, typename IsoMapRF&gt;
  30   inline typename property_traits&lt;ComponentMap&gt;::value_type
  31   fleischer_hendrickson_pinar_strong_components(const Graph&amp; g,
  32                                                 ComponentMap c,
  33                                                 const ReverseGraph&amp; gr,
  34                                                 IsoMapFR fr, IsoMapRF rf);
  35 }
  36 </pre>
  37 <p>The <tt class="docutils literal"><span class="pre">strong_components()</span></tt> function computes the strongly connected
  38 components of a directed graph.  The distributed strong components
  39 algorithm uses the <a class="reference external" href="http://www.boost.org/libs/graph/doc/strong_components.html">sequential strong components</a> algorithm to
  40 identify components local to a processor.  The distributed portion of
  41 the algorithm is built on the <a class="reference external" href="breadth_first_search.html">distributed breadth first search</a>
  42 algorithm and is based on the work of Fleischer, Hendrickson, and
  43 Pinar <a class="citation-reference" href="#fhp00" id="id1">[FHP00]</a>. The interface is a superset of the interface to the
  44 BGL <a class="reference external" href="http://www.boost.org/libs/graph/doc/strong_components.html">sequential strong components</a> algorithm. The number of
  45 strongly-connected components in the graph is returned to all
  46 processes.</p>
  47 <p>The distributed strong components algorithm works on both <tt class="docutils literal"><span class="pre">directed</span></tt>
  48 and <tt class="docutils literal"><span class="pre">bidirectional</span></tt> graphs.  In the bidirectional case, a reverse
  49 graph adapter is used to produce the required reverse graph.  In
  50 the directed case, a separate graph is constructed in which all the
  51 edges are reversed.</p>
  52 <div class="contents topic" id="contents">
  53 <p class="topic-title first">Contents</p>
  54 <ul class="simple">
  55 <li><a class="reference internal" href="#where-defined" id="id2">Where Defined</a></li>
  56 <li><a class="reference internal" href="#parameters" id="id3">Parameters</a></li>
  57 <li><a class="reference internal" href="#complexity" id="id4">Complexity</a></li>
  58 <li><a class="reference internal" href="#algorithm-description" id="id5">Algorithm Description</a></li>
  59 <li><a class="reference internal" href="#bibliography" id="id6">Bibliography</a></li>
  60 </ul>
  61 </div>
  62 <div class="section" id="where-defined">
  63 <h1><a class="toc-backref" href="#id2">Where Defined</a></h1>
  64 <p>&lt;<tt class="docutils literal"><span class="pre">boost/graph/distributed/strong_components.hpp</span></tt>&gt;</p>
  65 <p>also accessible from</p>
  66 <p>&lt;<tt class="docutils literal"><span class="pre">boost/graph/strong_components.hpp</span></tt>&gt;</p>
  67 </div>
  68 <div class="section" id="parameters">
  69 <h1><a class="toc-backref" href="#id3">Parameters</a></h1>
  70 <dl class="docutils">
  71 <dt>IN:  <tt class="docutils literal"><span class="pre">const</span> <span class="pre">Graph&amp;</span> <span class="pre">g</span></tt></dt>
  72 <dd>The graph type must be a model of <a class="reference external" href="DistributedGraph.html">Distributed Graph</a>.  The graph
  73 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>
  74 <dt>OUT:  <tt class="docutils literal"><span class="pre">ComponentMap</span> <span class="pre">c</span></tt></dt>
  75 <dd>The algorithm computes how many strongly connected components are in the
  76 graph, and assigns each component an integer label.  The algorithm
  77 then records to which component each vertex in the graph belongs by
  78 recording the component number in the component property map.  The
  79 <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
  80 value type must be the <tt class="docutils literal"><span class="pre">vertices_size_type</span></tt> of the graph.  The key
  81 type must be the graph's vertex descriptor type.</dd>
  82 <dt>UTIL:  <tt class="docutils literal"><span class="pre">VertexComponentMap</span> <span class="pre">r</span></tt></dt>
  83 <dd>The algorithm computes a mapping from each vertex to the
  84 representative of the strong component, stored in this property map.
  85 The <tt class="docutils literal"><span class="pre">VertexComponentMap</span></tt> type must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a>.
  86 The value and key types must be the vertex descriptor of the graph.</dd>
  87 <dt>IN: <tt class="docutils literal"><span class="pre">const</span> <span class="pre">ReverseGraph&amp;</span> <span class="pre">gr</span></tt></dt>
  88 <dd><p class="first">The reverse (or transpose) graph of <tt class="docutils literal"><span class="pre">g</span></tt>, such that for each
  89 directed edge <em>(u, v)</em> in <tt class="docutils literal"><span class="pre">g</span></tt> there exists a directed edge
  90 <em>(fr(v), fr(u))</em> in <tt class="docutils literal"><span class="pre">gr</span></tt> and for each edge <em>(v', u')</em> in <em>gr</em>
  91 there exists an edge <em>(rf(u'), rf(v'))</em> in <tt class="docutils literal"><span class="pre">g</span></tt>. The functions
  92 <em>fr</em> and <em>rf</em> map from vertices in the graph to the reverse graph
  93 and vice-verse, and are represented as property map arguments. The
  94 concept requirements on this graph type are equivalent to those on
  95 the <tt class="docutils literal"><span class="pre">Graph</span></tt> type, but the types need not be the same.</p>
  96 <p class="last"><strong>Default</strong>: Either a <tt class="docutils literal"><span class="pre">reverse_graph</span></tt> adaptor over the original
  97 graph (if the graph type is bidirectional, i.e., models the
  98 <a class="reference external" href="http://www.boost.org/libs/graph/doc/BidirectionalGraph.html">Bidirectional Graph</a> concept) or a <a class="reference external" href="distributed_adjacency_list.html">distributed adjacency list</a>
  99 constructed from the input graph.</p>
 100 </dd>
 101 <dt>IN: <tt class="docutils literal"><span class="pre">IsoMapFR</span> <span class="pre">fr</span></tt></dt>
 102 <dd><p class="first">A property map that maps from vertices in the input graph <tt class="docutils literal"><span class="pre">g</span></tt> to
 103 vertices in the reversed graph <tt class="docutils literal"><span class="pre">gr</span></tt>. The type <tt class="docutils literal"><span class="pre">IsoMapFR</span></tt> must
 104 model the <a class="reference external" href="http://www.boost.org/libs/property_map/ReadablePropertyMap.html">Readable Property Map</a> concept and have the graph's
 105 vertex descriptor as its key type and the reverse graph's vertex
 106 descriptor as its value type.</p>
 107 <p class="last"><strong>Default</strong>: An identity property map (if the graph type is
 108 bidirectional) or a distributed <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> (if the
 109 graph type is directed).</p>
 110 </dd>
 111 <dt>IN: <tt class="docutils literal"><span class="pre">IsoMapRF</span> <span class="pre">rf</span></tt></dt>
 112 <dd><p class="first">A property map that maps from vertices in the reversed graph <tt class="docutils literal"><span class="pre">gr</span></tt>
 113 to vertices in the input graph <tt class="docutils literal"><span class="pre">g</span></tt>. The type <tt class="docutils literal"><span class="pre">IsoMapRF</span></tt> must
 114 model the <a class="reference external" href="http://www.boost.org/libs/property_map/ReadablePropertyMap.html">Readable Property Map</a> concept and have the reverse
 115 graph's vertex descriptor as its key type and the graph's vertex
 116 descriptor as its value type.</p>
 117 <p class="last"><strong>Default</strong>: An identity property map (if the graph type is
 118 bidirectional) or a distributed <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> (if the
 119 graph type is directed).</p>
 120 </dd>
 121 </dl>
 122 </div>
 123 <div class="section" id="complexity">
 124 <h1><a class="toc-backref" href="#id4">Complexity</a></h1>
 125 <p>The local phase of the algorithm is <em>O(V + E)</em>.  The parallel phase of
 126 the algorithm requires at most <em>O(V)</em> supersteps each containing two
 127 breadth first searches which are <em>O(V + E)</em> each.</p>
 128 </div>
 129 <div class="section" id="algorithm-description">
 130 <h1><a class="toc-backref" href="#id5">Algorithm Description</a></h1>
 131 <p>Prior to executing the sequential phase of the algorithm, each process
 132 identifies any completely local strong components which it labels and
 133 removes from the vertex set considered in the parallel phase of the
 134 algorithm.</p>
 135 <p>The parallel phase of the distributed strong components algorithm
 136 consists of series of supersteps.  Each superstep starts with one
 137 or more vertex sets which are guaranteed to completely contain
 138 any remaining strong components.  A <a class="reference external" href="breadth_first_search.html">distributed breadth first search</a>
 139 is performed starting from the first vertex in each vertex set.
 140 All of these breadth first searches are performed in parallel by having
 141 each processor call <tt class="docutils literal"><span class="pre">breadth_first_search()</span></tt> with a different starting
 142 vertex, and if necessary inserting additional vertices into the
 143 <tt class="docutils literal"><span class="pre">distributed</span> <span class="pre">queue</span></tt> used for breadth first search before invoking
 144 the algorithm.  A second <a class="reference external" href="breadth_first_search.html">distributed breadth first search</a> is
 145 performed on the reverse graph in the same fashion.  For each initial
 146 vertex set, the successor set (the vertices reached in the forward
 147 breadth first search), and the predecessor set (the vertices reached
 148 in the backward breadth first search) is computed.  The intersection
 149 of the predecessor and successor sets form a strongly connected
 150 component which is labeled as such.  The remaining vertices in the
 151 initial vertex set are partitioned into three subsets each guaranteed
 152 to completely contain any remaining strong components.  These three sets
 153 are the vertices in the predecessor set not contained in the identified
 154 strongly connected component, the vertices in the successor set not
 155 in the strongly connected component, and the remaing vertices in the
 156 initial vertex set not in the predecessor or successor sets.  Once
 157 new vertex sets are identified, the algorithm begins a new superstep.
 158 The algorithm halts when no vertices remain.</p>
 159 <p>To boost performance in sparse graphs when identifying small components,
 160 when less than a given portion of the initial number of vertices
 161 remain in active vertex sets, a filtered graph adapter is used
 162 to limit the graph seen by the breadth first search algorithm to the
 163 active vertices.</p>
 164 </div>
 165 <div class="section" id="bibliography">
 166 <h1><a class="toc-backref" href="#id6">Bibliography</a></h1>
 167 <table class="docutils citation" frame="void" id="fhp00" rules="none">
 168 <colgroup><col class="label" /><col /></colgroup>
 169 <tbody valign="top">
 170 <tr><td class="label"><a class="fn-backref" href="#id1">[FHP00]</a></td><td>Lisa Fleischer, Bruce Hendrickson, and Ali Pinar. On
 171 Identifying Strongly Connected Components in Parallel. In Parallel and
 172 Distributed Processing (IPDPS), volume 1800 of Lecture Notes in
 173 Computer Science, pages 505--511, 2000. Springer.</td></tr>
 174 </tbody>
 175 </table>
 176 <hr class="docutils" />
 177 <p>Copyright (C) 2004, 2005 The Trustees of Indiana University.</p>
 178 <p>Authors: Nick Edmonds, Douglas Gregor, and Andrew Lumsdaine</p>
 179 <!--  -->
 180 </div>
 181 </div>
 182 <div class="footer">
 183 <hr class="footer" />
 184 Generated on: 2009-05-31 00:21 UTC.
 185 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.
 186
 187 </div>
 188 </body>
 189 </html>