ceph/src/boost/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.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 Minimum Spanning Tree</title>
   8 <link rel="stylesheet" href="../../../../rst.css" type="text/css" />
   9 </head>
  10 <body>
  11 <div class="document" id="logo-minimum-spanning-tree">
  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> Minimum Spanning Tree</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 <p>The Parallel BGL contains four <a class="reference external" href="http://www.boost.org/libs/graph/doc/graph_theory_review.html#sec:minimum-spanning-tree">minimum spanning tree</a> (MST)
  19 algorithms <a class="citation-reference" href="#dg98" id="id1">[DG98]</a> for use on undirected, weighted, distributed
  20 graphs. The graphs need not be connected: each algorithm will compute
  21 a minimum spanning forest (MSF) when provided with a disconnected
  22 graph.</p>
  23 <p>The interface to each of the four algorithms is similar to the
  24 implementation of 'Kruskal's algorithm'_ in the sequential BGL. Each
  25 accepts, at a minimum, a graph, a weight map, and an output
  26 iterator. The edges of the MST (or MSF) will be output via the output
  27 iterator on process 0: other processes may receive edges on their
  28 output iterators, but the set may not be complete, depending on the
  29 algorithm. The algorithm parameters are documented together, because
  30 they do not vary greatly. See the section <a class="reference internal" href="#selecting-an-mst-algorithm">Selecting an MST
  31 algorithm</a> for advice on algorithm selection.</p>
  32 <p>The graph itself must model the <a class="reference external" href="http://www.boost.org/libs/graph/doc/VertexListGraph.html">Vertex List Graph</a> concept and the
  33 Distributed Edge List Graph concept. Since the most common
  34 distributed graph structure, the <a class="reference external" href="distributed_adjacency_list.html">distributed adjacency list</a>, only
  35 models the Distributed Vertex List Graph concept, it may only be used
  36 with these algorithms when wrapped in a suitable adaptor, such as the
  37 <a class="reference external" href="vertex_list_adaptor.html">vertex_list_adaptor</a>.</p>
  38 <div class="contents topic" id="contents">
  39 <p class="topic-title first">Contents</p>
  40 <ul class="simple">
  41 <li><a class="reference internal" href="#where-defined" id="id12">Where Defined</a></li>
  42 <li><a class="reference internal" href="#parameters" id="id13">Parameters</a></li>
  43 <li><a class="reference internal" href="#dense-boruvka-minimum-spanning-tree" id="id14"><tt class="docutils literal"><span class="pre">dense_boruvka_minimum_spanning_tree</span></tt></a><ul>
  44 <li><a class="reference internal" href="#description" id="id15">Description</a></li>
  45 <li><a class="reference internal" href="#complexity" id="id16">Complexity</a></li>
  46 <li><a class="reference internal" href="#performance" id="id17">Performance</a></li>
  47 </ul>
  48 </li>
  49 <li><a class="reference internal" href="#merge-local-minimum-spanning-trees" id="id18"><tt class="docutils literal"><span class="pre">merge_local_minimum_spanning_trees</span></tt></a><ul>
  50 <li><a class="reference internal" href="#id2" id="id19">Description</a></li>
  51 <li><a class="reference internal" href="#id3" id="id20">Complexity</a></li>
  52 <li><a class="reference internal" href="#id4" id="id21">Performance</a></li>
  53 </ul>
  54 </li>
  55 <li><a class="reference internal" href="#boruvka-then-merge" id="id22"><tt class="docutils literal"><span class="pre">boruvka_then_merge</span></tt></a><ul>
  56 <li><a class="reference internal" href="#id5" id="id23">Description</a></li>
  57 <li><a class="reference internal" href="#id6" id="id24">Complexity</a></li>
  58 <li><a class="reference internal" href="#id7" id="id25">Performance</a></li>
  59 </ul>
  60 </li>
  61 <li><a class="reference internal" href="#boruvka-mixed-merge" id="id26"><tt class="docutils literal"><span class="pre">boruvka_mixed_merge</span></tt></a><ul>
  62 <li><a class="reference internal" href="#id8" id="id27">Description</a></li>
  63 <li><a class="reference internal" href="#id9" id="id28">Complexity</a></li>
  64 <li><a class="reference internal" href="#id10" id="id29">Performance</a></li>
  65 </ul>
  66 </li>
  67 <li><a class="reference internal" href="#selecting-an-mst-algorithm" id="id30">Selecting an MST algorithm</a><ul>
  68 <li><a class="reference internal" href="#performance-on-sparse-graphs" id="id31">Performance on Sparse Graphs</a></li>
  69 <li><a class="reference internal" href="#performance-on-dense-graphs" id="id32">Performance on Dense Graphs</a></li>
  70 </ul>
  71 </li>
  72 </ul>
  73 </div>
  74 <div class="section" id="where-defined">
  75 <h1><a class="toc-backref" href="#id12">Where Defined</a></h1>
  76 <p>&lt;<tt class="docutils literal"><span class="pre">boost/graph/distributed/dehne_gotz_min_spanning_tree.hpp</span></tt>&gt;</p>
  77 </div>
  78 <div class="section" id="parameters">
  79 <h1><a class="toc-backref" href="#id13">Parameters</a></h1>
  80 <dl class="docutils">
  81 <dt>IN: <tt class="docutils literal"><span class="pre">Graph&amp;</span> <span class="pre">g</span></tt></dt>
  82 <dd>The graph type must be a model of <a class="reference external" href="http://www.boost.org/libs/graph/doc/VertexListGraph.html">Vertex List Graph</a> and
  83 <a class="reference external" href="DistributedEdgeListGraph.html">Distributed Edge List Graph</a>.</dd>
  84 <dt>IN/OUT: <tt class="docutils literal"><span class="pre">WeightMap</span> <span class="pre">weight</span></tt></dt>
  85 <dd>The weight map must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a> and a <a class="reference external" href="http://www.boost.org/libs/property_map/ReadablePropertyMap.html">Readable
  86 Property Map</a> whose key type is the edge descriptor of the graph
  87 and whose value type is numerical.</dd>
  88 <dt>IN/OUT: <tt class="docutils literal"><span class="pre">OutputIterator</span> <span class="pre">out</span></tt></dt>
  89 <dd>The output iterator through which the edges of the MSF will be
  90 written. Must be capable of accepting edge descriptors for output.</dd>
  91 <dt>IN: <tt class="docutils literal"><span class="pre">VertexIndexMap</span> <span class="pre">index</span></tt></dt>
  92 <dd><p class="first">A mapping from vertex descriptors to indices in the range <em>[0,
  93 num_vertices(g))</em>. This must be a <a class="reference external" href="http://www.boost.org/libs/property_map/ReadablePropertyMap.html">Readable Property Map</a> whose
  94 key type is a vertex descriptor and whose value type is an integral
  95 type, typically the <tt class="docutils literal"><span class="pre">vertices_size_type</span></tt> of the graph.</p>
  96 <p class="last"><strong>Default:</strong> <tt class="docutils literal"><span class="pre">get(vertex_index,</span> <span class="pre">g)</span></tt></p>
  97 </dd>
  98 <dt>IN/UTIL: <tt class="docutils literal"><span class="pre">RankMap</span> <span class="pre">rank_map</span></tt></dt>
  99 <dd><p class="first">Stores the rank of each vertex, which is used for maintaining
 100 union-find data structures. This must be a <a class="reference external" href="http://www.boost.org/libs/property_map/ReadWritePropertyMap.html">Read/Write Property Map</a>
 101 whose key type is a vertex descriptor and whose value type is an
 102 integral type.</p>
 103 <p class="last"><strong>Default:</strong> An <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> built from an STL vector
 104 of the <tt class="docutils literal"><span class="pre">vertices_size_type</span></tt> of the graph and the vertex index map.</p>
 105 </dd>
 106 <dt>IN/UTIL: <tt class="docutils literal"><span class="pre">ParentMap</span> <span class="pre">parent_map</span></tt></dt>
 107 <dd><p class="first">Stores the parent (representative) of each vertex, which is used for
 108 maintaining union-find data structures. This must be a <a class="reference external" href="http://www.boost.org/libs/property_map/ReadWritePropertyMap.html">Read/Write
 109 Property Map</a> whose key type is a vertex descriptor and whose value
 110 type is also a vertex descriptor.</p>
 111 <p class="last"><strong>Default:</strong> An <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> built from an STL vector
 112 of the <tt class="docutils literal"><span class="pre">vertex_descriptor</span></tt> of the graph and the vertex index map.</p>
 113 </dd>
 114 <dt>IN/UTIL: <tt class="docutils literal"><span class="pre">SupervertexMap</span> <span class="pre">supervertex_map</span></tt></dt>
 115 <dd><p class="first">Stores the supervertex index of each vertex, which is used for
 116 maintaining the supervertex list data structures. This must be a
 117 <a class="reference external" href="http://www.boost.org/libs/property_map/ReadWritePropertyMap.html">Read/Write Property Map</a> whose key type is a vertex descriptor and
 118 whose value type is an integral type.</p>
 119 <p class="last"><strong>Default:</strong> An <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> built from an STL vector
 120 of the <tt class="docutils literal"><span class="pre">vertices_size_type</span></tt> of the graph and the vertex index map.</p>
 121 </dd>
 122 </dl>
 123 </div>
 124 <div class="section" id="dense-boruvka-minimum-spanning-tree">
 125 <h1><a class="toc-backref" href="#id14"><tt class="docutils literal"><span class="pre">dense_boruvka_minimum_spanning_tree</span></tt></a></h1>
 126 <pre class="literal-block">
 127 namespace graph {
 128   template&lt;typename Graph, typename WeightMap, typename OutputIterator,
 129            typename VertexIndexMap, typename RankMap, typename ParentMap,
 130            typename SupervertexMap&gt;
 131   OutputIterator
 132   dense_boruvka_minimum_spanning_tree(const Graph&amp; g, WeightMap weight_map,
 133                                     OutputIterator out,
 134                                     VertexIndexMap index,
 135                                     RankMap rank_map, ParentMap parent_map,
 136                                     SupervertexMap supervertex_map);
 137
 138   template&lt;typename Graph, typename WeightMap, typename OutputIterator,
 139            typename VertexIndex&gt;
 140   OutputIterator
 141   dense_boruvka_minimum_spanning_tree(const Graph&amp; g, WeightMap weight_map,
 142                                     OutputIterator out, VertexIndex index);
 143
 144   template&lt;typename Graph, typename WeightMap, typename OutputIterator&gt;
 145   OutputIterator
 146   dense_boruvka_minimum_spanning_tree(const Graph&amp; g, WeightMap weight_map,
 147                                     OutputIterator out);
 148 }
 149 </pre>
 150 <div class="section" id="description">
 151 <h2><a class="toc-backref" href="#id15">Description</a></h2>
 152 <p>The dense Boruvka distributed minimum spanning tree algorithm is a
 153 direct parallelization of the sequential MST algorithm by
 154 Boruvka. The algorithm first creates a <em>supervertex</em> out of each
 155 vertex. Then, in each iteration, it finds the smallest-weight edge
 156 incident to each vertex, collapses supervertices along these edges,
 157 and removals all self loops. The only difference between the
 158 sequential and parallel algorithms is that the parallel algorithm
 159 performs an all-reduce operation so that all processes have the
 160 global minimum set of edges.</p>
 161 <p>Unlike the other three algorithms, this algorithm emits the complete
 162 list of edges in the minimum spanning forest via the output iterator
 163 on all processes. It may therefore be more useful than the others
 164 when parallelizing sequential BGL programs.</p>
 165 </div>
 166 <div class="section" id="complexity">
 167 <h2><a class="toc-backref" href="#id16">Complexity</a></h2>
 168 <p>The distributed algorithm requires <em>O(log n)</em> BSP supersteps, each of
 169 which requires <em>O(m/p + n)</em> time and <em>O(n)</em> communication per
 170 process.</p>
 171 </div>
 172 <div class="section" id="performance">
 173 <h2><a class="toc-backref" href="#id17">Performance</a></h2>
 174 <p>The following charts illustrate the performance of this algorithm on
 175 various random graphs. We see that the algorithm scales well up to 64
 176 or 128 processors, depending on the type of graph, for dense
 177 graphs. However, for sparse graphs performance tapers off as the
 178 number of processors surpases <em>m/n</em>, i.e., the average degree (which
 179 is 30 for this graph). This behavior is expected from the algorithm.</p>
 180 <img align="left" alt="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_5.png" class="align-left" src="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_5.png" />
 181 <img alt="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_5_speedup_1.png" src="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_5_speedup_1.png" />
 182 <img align="left" alt="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_5.png" class="align-left" src="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_5.png" />
 183 <img alt="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_5_speedup_1.png" src="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_5_speedup_1.png" />
 184 </div>
 185 </div>
 186 <div class="section" id="merge-local-minimum-spanning-trees">
 187 <h1><a class="toc-backref" href="#id18"><tt class="docutils literal"><span class="pre">merge_local_minimum_spanning_trees</span></tt></a></h1>
 188 <pre class="literal-block">
 189 namespace graph {
 190   template&lt;typename Graph, typename WeightMap, typename OutputIterator,
 191            typename VertexIndexMap&gt;
 192   OutputIterator
 193   merge_local_minimum_spanning_trees(const Graph&amp; g, WeightMap weight,
 194                                      OutputIterator out,
 195                                      VertexIndexMap index);
 196
 197   template&lt;typename Graph, typename WeightMap, typename OutputIterator&gt;
 198   inline OutputIterator
 199   merge_local_minimum_spanning_trees(const Graph&amp; g, WeightMap weight,
 200                                      OutputIterator out);
 201 }
 202 </pre>
 203 <div class="section" id="id2">
 204 <h2><a class="toc-backref" href="#id19">Description</a></h2>
 205 <p>The merging local MSTs algorithm operates by computing minimum
 206 spanning forests from the edges stored on each process. Then the
 207 processes merge their edge lists along a tree. The child nodes cease
 208 participating in the computation, but the parent nodes recompute MSFs
 209 from the newly acquired edges. In the final round, the root of the
 210 tree computes the global MSFs, having received candidate edges from
 211 every other process via the tree.</p>
 212 </div>
 213 <div class="section" id="id3">
 214 <h2><a class="toc-backref" href="#id20">Complexity</a></h2>
 215 <p>This algorithm requires <em>O(log_D p)</em> BSP supersteps (where <em>D</em> is the
 216 number of children in the tree, and is currently fixed at 3). Each
 217 superstep requires <em>O((m/p) log (m/p) + n)</em> time and <em>O(m/p)</em>
 218 communication per process.</p>
 219 </div>
 220 <div class="section" id="id4">
 221 <h2><a class="toc-backref" href="#id21">Performance</a></h2>
 222 <p>The following charts illustrate the performance of this algorithm on
 223 various random graphs. The algorithm only scales well for very dense
 224 graphs, where most of the work is performed in the initial stage and
 225 there is very little work in the later stages.</p>
 226 <img align="left" alt="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_6.png" class="align-left" src="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_6.png" />
 227 <img alt="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_6_speedup_1.png" src="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_6_speedup_1.png" />
 228 <img align="left" alt="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_6.png" class="align-left" src="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_6.png" />
 229 <img alt="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_6_speedup_1.png" src="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_6_speedup_1.png" />
 230 </div>
 231 </div>
 232 <div class="section" id="boruvka-then-merge">
 233 <h1><a class="toc-backref" href="#id22"><tt class="docutils literal"><span class="pre">boruvka_then_merge</span></tt></a></h1>
 234 <pre class="literal-block">
 235 namespace graph {
 236   template&lt;typename Graph, typename WeightMap, typename OutputIterator,
 237            typename VertexIndexMap, typename RankMap, typename ParentMap,
 238            typename SupervertexMap&gt;
 239   OutputIterator
 240   boruvka_then_merge(const Graph&amp; g, WeightMap weight, OutputIterator out,
 241                      VertexIndexMap index, RankMap rank_map,
 242                      ParentMap parent_map, SupervertexMap
 243                      supervertex_map);
 244
 245   template&lt;typename Graph, typename WeightMap, typename OutputIterator,
 246            typename VertexIndexMap&gt;
 247   inline OutputIterator
 248   boruvka_then_merge(const Graph&amp; g, WeightMap weight, OutputIterator out,
 249                       VertexIndexMap index);
 250
 251   template&lt;typename Graph, typename WeightMap, typename OutputIterator&gt;
 252   inline OutputIterator
 253   boruvka_then_merge(const Graph&amp; g, WeightMap weight, OutputIterator out);
 254 }
 255 </pre>
 256 <div class="section" id="id5">
 257 <h2><a class="toc-backref" href="#id23">Description</a></h2>
 258 <p>This algorithm applies both Boruvka steps and local MSF merging steps
 259 together to achieve better asymptotic performance than either
 260 algorithm alone. It first executes Boruvka steps until only <em>n/(log_d
 261 p)^2</em> supervertices remain, then completes the MSF computation by
 262 performing local MSF merging on the remaining edges and
 263 supervertices.</p>
 264 </div>
 265 <div class="section" id="id6">
 266 <h2><a class="toc-backref" href="#id24">Complexity</a></h2>
 267 <p>This algorithm requires <em>log_D p</em> + <em>log log_D p</em> BSP supersteps. The
 268 time required by each superstep depends on the type of superstep
 269 being performed; see the distributed Boruvka or merging local MSFS
 270 algorithms for details.</p>
 271 </div>
 272 <div class="section" id="id7">
 273 <h2><a class="toc-backref" href="#id25">Performance</a></h2>
 274 <p>The following charts illustrate the performance of this algorithm on
 275 various random graphs. We see that the algorithm scales well up to 64
 276 or 128 processors, depending on the type of graph, for dense
 277 graphs. However, for sparse graphs performance tapers off as the
 278 number of processors surpases <em>m/n</em>, i.e., the average degree (which
 279 is 30 for this graph). This behavior is expected from the algorithm.</p>
 280 <img align="left" alt="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_7.png" class="align-left" src="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_7.png" />
 281 <img alt="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_7_speedup_1.png" src="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_7_speedup_1.png" />
 282 <img align="left" alt="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_7.png" class="align-left" src="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_7.png" />
 283 <img alt="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_7_speedup_1.png" src="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_7_speedup_1.png" />
 284 </div>
 285 </div>
 286 <div class="section" id="boruvka-mixed-merge">
 287 <h1><a class="toc-backref" href="#id26"><tt class="docutils literal"><span class="pre">boruvka_mixed_merge</span></tt></a></h1>
 288 <pre class="literal-block">
 289 namespace {
 290   template&lt;typename Graph, typename WeightMap, typename OutputIterator,
 291            typename VertexIndexMap, typename RankMap, typename ParentMap,
 292            typename SupervertexMap&gt;
 293   OutputIterator
 294   boruvka_mixed_merge(const Graph&amp; g, WeightMap weight, OutputIterator out,
 295                       VertexIndexMap index, RankMap rank_map,
 296                       ParentMap parent_map, SupervertexMap
 297                       supervertex_map);
 298
 299   template&lt;typename Graph, typename WeightMap, typename OutputIterator,
 300            typename VertexIndexMap&gt;
 301   inline OutputIterator
 302   boruvka_mixed_merge(const Graph&amp; g, WeightMap weight, OutputIterator out,
 303                       VertexIndexMap index);
 304
 305   template&lt;typename Graph, typename WeightMap, typename OutputIterator&gt;
 306   inline OutputIterator
 307   boruvka_mixed_merge(const Graph&amp; g, WeightMap weight, OutputIterator out);
 308 }
 309 </pre>
 310 <div class="section" id="id8">
 311 <h2><a class="toc-backref" href="#id27">Description</a></h2>
 312 <p>This algorithm applies both Boruvka steps and local MSF merging steps
 313 together to achieve better asymptotic performance than either method
 314 alone. In each iteration, the algorithm first performs a Boruvka step
 315 and then merges the local MSFs computed based on the supervertex
 316 graph.</p>
 317 </div>
 318 <div class="section" id="id9">
 319 <h2><a class="toc-backref" href="#id28">Complexity</a></h2>
 320 <p>This algorithm requires <em>log_D p</em> BSP supersteps. The
 321 time required by each superstep depends on the type of superstep
 322 being performed; see the distributed Boruvka or merging local MSFS
 323 algorithms for details. However, the algorithm is
 324 communication-optional (requiring <em>O(n)</em> communication overall) when
 325 the graph is sufficiently dense, i.e., <em>m/n &gt;= p</em>.</p>
 326 </div>
 327 <div class="section" id="id10">
 328 <h2><a class="toc-backref" href="#id29">Performance</a></h2>
 329 <p>The following charts illustrate the performance of this algorithm on
 330 various random graphs. We see that the algorithm scales well up to 64
 331 or 128 processors, depending on the type of graph, for dense
 332 graphs. However, for sparse graphs performance tapers off as the
 333 number of processors surpases <em>m/n</em>, i.e., the average degree (which
 334 is 30 for this graph). This behavior is expected from the algorithm.</p>
 335 <img align="left" alt="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_8.png" class="align-left" src="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_8.png" />
 336 <img alt="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_8_speedup_1.png" src="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_8_speedup_1.png" />
 337 <img align="left" alt="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_8.png" class="align-left" src="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_8.png" />
 338 <img alt="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_8_speedup_1.png" src="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_8_speedup_1.png" />
 339 </div>
 340 </div>
 341 <div class="section" id="selecting-an-mst-algorithm">
 342 <h1><a class="toc-backref" href="#id30">Selecting an MST algorithm</a></h1>
 343 <p>Dehne and Gotz reported <a class="citation-reference" href="#dg98" id="id11">[DG98]</a> mixed results when evaluating these
 344 four algorithms. No particular algorithm was clearly better than the
 345 others in all cases. However, the asymptotically best algorithm
 346 (<tt class="docutils literal"><span class="pre">boruvka_mixed_merge</span></tt>) seemed to perform more poorly in their tests
 347 than the other merging-based algorithms. The following performance
 348 charts illustrate the performance of these four minimum spanning tree
 349 implementations.</p>
 350 <p>Overall, <tt class="docutils literal"><span class="pre">dense_boruvka_minimum_spanning_tree</span></tt> gives the most
 351 consistent performance and scalability for the graphs we
 352 tested. Additionally, it may be more suitable for sequential programs
 353 that are being parallelized, because it emits complete MSF edge lists
 354 via the output iterators in every process.</p>
 355 <div class="section" id="performance-on-sparse-graphs">
 356 <h2><a class="toc-backref" href="#id31">Performance on Sparse Graphs</a></h2>
 357 <img align="left" alt="chart_php_generator_ER_dataset_TimeSparse_columns_5_6_7_8.png" class="align-left" src="chart_php_generator_ER_dataset_TimeSparse_columns_5_6_7_8.png" />
 358 <img alt="chart_php_generator_ER_dataset_TimeSparse_columns_5_6_7_8_speedup_1.png" src="chart_php_generator_ER_dataset_TimeSparse_columns_5_6_7_8_speedup_1.png" />
 359 <img align="left" alt="chart_php_generator_SF_dataset_TimeSparse_columns_5_6_7_8.png" class="align-left" src="chart_php_generator_SF_dataset_TimeSparse_columns_5_6_7_8.png" />
 360 <img alt="chart_php_generator_SF_dataset_TimeSparse_columns_5_6_7_8_speedup_1.png" src="chart_php_generator_SF_dataset_TimeSparse_columns_5_6_7_8_speedup_1.png" />
 361 <img align="left" alt="chart_php_generator_SW_dataset_TimeSparse_columns_5_6_7_8.png" class="align-left" src="chart_php_generator_SW_dataset_TimeSparse_columns_5_6_7_8.png" />
 362 <img alt="chart_php_generator_SW_dataset_TimeSparse_columns_5_6_7_8_speedup_1.png" src="chart_php_generator_SW_dataset_TimeSparse_columns_5_6_7_8_speedup_1.png" />
 363 </div>
 364 <div class="section" id="performance-on-dense-graphs">
 365 <h2><a class="toc-backref" href="#id32">Performance on Dense Graphs</a></h2>
 366 <img align="left" alt="chart_php_generator_ER_dataset_TimeDense_columns_5_6_7_8.png" class="align-left" src="chart_php_generator_ER_dataset_TimeDense_columns_5_6_7_8.png" />
 367 <img alt="chart_php_generator_ER_dataset_TimeDense_columns_5_6_7_8_speedup_1.png" src="chart_php_generator_ER_dataset_TimeDense_columns_5_6_7_8_speedup_1.png" />
 368 <img align="left" alt="chart_php_generator_SF_dataset_TimeDense_columns_5_6_7_8.png" class="align-left" src="chart_php_generator_SF_dataset_TimeDense_columns_5_6_7_8.png" />
 369 <img alt="chart_php_generator_SF_dataset_TimeDense_columns_5_6_7_8_speedup_1.png" src="chart_php_generator_SF_dataset_TimeDense_columns_5_6_7_8_speedup_1.png" />
 370 <img align="left" alt="chart_php_generator_SW_dataset_TimeDense_columns_5_6_7_8.png" class="align-left" src="chart_php_generator_SW_dataset_TimeDense_columns_5_6_7_8.png" />
 371 <img alt="chart_php_generator_SW_dataset_TimeDense_columns_5_6_7_8_speedup_1.png" src="chart_php_generator_SW_dataset_TimeDense_columns_5_6_7_8_speedup_1.png" />
 372 <hr class="docutils" />
 373 <p>Copyright (C) 2004 The Trustees of Indiana University.</p>
 374 <p>Authors: Douglas Gregor and Andrew Lumsdaine</p>
 375 <table class="docutils citation" frame="void" id="dg98" rules="none">
 376 <colgroup><col class="label" /><col /></colgroup>
 377 <tbody valign="top">
 378 <tr><td class="label">[DG98]</td><td><em>(<a class="fn-backref" href="#id1">1</a>, <a class="fn-backref" href="#id11">2</a>)</em> Frank Dehne and Silvia Gotz. <em>Practical Parallel Algorithms
 379 for Minimum Spanning Trees</em>. In Symposium on Reliable Distributed Systems,
 380 pages 366--371, 1998.</td></tr>
 381 </tbody>
 382 </table>
 383 </div>
 384 </div>
 385 </div>
 386 <div class="footer">
 387 <hr class="footer" />
 388 Generated on: 2009-05-31 00:21 UTC.
 389 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.
 390
 391 </div>
 392 </body>
 393 </html>