ceph/src/boost/libs/graph_parallel/doc/html/st_connected.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 s-t Connectivity</title>
   8 <link rel="stylesheet" href="../../../../rst.css" type="text/css" />
   9 </head>
  10 <body>
  11 <div class="document" id="logo-s-t-connectivity">
  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> s-t Connectivity</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&lt;typename DistributedGraph, typename ColorMap&gt;
  21   inline bool
  22   st_connected(const DistributedGraph&amp; g,
  23                typename graph_traits&lt;DistributedGraph&gt;::vertex_descriptor s,
  24                typename graph_traits&lt;DistributedGraph&gt;::vertex_descriptor t,
  25                ColorMap color)
  26
  27   template&lt;typename DistributedGraph&gt;
  28   inline bool
  29   st_connected(const DistributedGraph&amp; g,
  30                typename graph_traits&lt;DistributedGraph&gt;::vertex_descriptor s,
  31                typename graph_traits&lt;DistributedGraph&gt;::vertex_descriptor t)
  32
  33   template&lt;typename DistributedGraph, typename ColorMap, typename OwnerMap&gt;
  34   bool
  35   st_connected(const DistributedGraph&amp; g,
  36                typename graph_traits&lt;DistributedGraph&gt;::vertex_descriptor s,
  37                typename graph_traits&lt;DistributedGraph&gt;::vertex_descriptor t,
  38                ColorMap color, OwnerMap owner)
  39 } }
  40 </pre>
  41 <p>The <tt class="docutils literal"><span class="pre">st_connected()</span></tt> function determines whether there exists a path
  42 from <tt class="docutils literal"><span class="pre">s</span></tt> to <tt class="docutils literal"><span class="pre">t</span></tt> in a graph <tt class="docutils literal"><span class="pre">g</span></tt>.  If a path exists the function
  43 returns <tt class="docutils literal"><span class="pre">true</span></tt>, otherwise it returns <tt class="docutils literal"><span class="pre">false</span></tt>.</p>
  44 <p>This algorithm is currently <em>level-synchronized</em>, meaning that all
  45 vertices in a given level of the search tree will be processed
  46 (potentially in parallel) before any vertices from a successive level
  47 in the tree are processed.  This is not necessary for the correctness
  48 of the algorithm but rather is an implementation detail.  This
  49 algorithm could be rewritten fully-asynchronously using triggers which
  50 would remove the level-synchronized behavior.</p>
  51 <div class="contents topic" id="contents">
  52 <p class="topic-title first">Contents</p>
  53 <ul class="simple">
  54 <li><a class="reference internal" href="#where-defined" id="id1">Where Defined</a></li>
  55 <li><a class="reference internal" href="#parameters" id="id2">Parameters</a></li>
  56 <li><a class="reference internal" href="#complexity" id="id3">Complexity</a></li>
  57 <li><a class="reference internal" href="#algorithm-description" id="id4">Algorithm Description</a></li>
  58 </ul>
  59 </div>
  60 <div class="section" id="where-defined">
  61 <h1><a class="toc-backref" href="#id1">Where Defined</a></h1>
  62 <p>&lt;<tt class="docutils literal"><span class="pre">boost/graph/distributed/st_connected.hpp</span></tt>&gt;</p>
  63 </div>
  64 <div class="section" id="parameters">
  65 <h1><a class="toc-backref" href="#id2">Parameters</a></h1>
  66 <dl class="docutils">
  67 <dt>IN:  <tt class="docutils literal"><span class="pre">const</span> <span class="pre">DistributedGraph&amp;</span> <span class="pre">g</span></tt></dt>
  68 <dd>The graph type must be a model of <a class="reference external" href="DistributedGraph.html">Distributed Graph</a>.  The graph
  69 type must also model the <a class="reference external" href="http://www.boost.org/libs/graph/doc/IncidenceGraph.html">Incidence Graph</a>.</dd>
  70 </dl>
  71 <p>IN:  <tt class="docutils literal"><span class="pre">vertex_descriptor</span> <span class="pre">s</span></tt></p>
  72 <p>IN:  <tt class="docutils literal"><span class="pre">vertex_descriptor</span> <span class="pre">t</span></tt></p>
  73 <dl class="docutils">
  74 <dt>UTIL/OUT: <tt class="docutils literal"><span class="pre">color_map(ColorMap</span> <span class="pre">color)</span></tt></dt>
  75 <dd>The color map must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a> with the same
  76 process group as the graph <tt class="docutils literal"><span class="pre">g</span></tt> whose colors must monotonically
  77 darken (white -&gt; gray/green -&gt; black). The default value is a
  78 distributed <tt class="docutils literal"><span class="pre">two_bit_color_map</span></tt>.</dd>
  79 <dt>IN:  <tt class="docutils literal"><span class="pre">OwnerMap</span> <span class="pre">owner</span></tt></dt>
  80 <dd>The owner map must map from vertices to the process that owns them
  81 as described in the <a class="reference external" href="GlobalDescriptor.html">GlobalDescriptor</a> concept.</dd>
  82 <dt>OUT:  <tt class="docutils literal"><span class="pre">bool</span></tt></dt>
  83 <dd>The algorithm returns <tt class="docutils literal"><span class="pre">true</span></tt> if a path from <tt class="docutils literal"><span class="pre">s</span></tt> to <tt class="docutils literal"><span class="pre">t</span></tt> is
  84 found, and false otherwise.</dd>
  85 </dl>
  86 </div>
  87 <div class="section" id="complexity">
  88 <h1><a class="toc-backref" href="#id3">Complexity</a></h1>
  89 <p>This algorithm performs <em>O(V + E)</em> work in <em>d/2 + 1</em> BSP supersteps,
  90 where <em>d</em> is the shortest distance from <tt class="docutils literal"><span class="pre">s</span></tt> to <tt class="docutils literal"><span class="pre">t</span></tt>. Over all
  91 supersteps, <em>O(E)</em> messages of constant size will be transmitted.</p>
  92 </div>
  93 <div class="section" id="algorithm-description">
  94 <h1><a class="toc-backref" href="#id4">Algorithm Description</a></h1>
  95 <p>The algorithm consists of two simultaneous breadth-first traversals
  96 from <tt class="docutils literal"><span class="pre">s</span></tt> and <tt class="docutils literal"><span class="pre">t</span></tt> respectively.  The algorithm utilizes a single
  97 queue for both traversals with the traversal from <tt class="docutils literal"><span class="pre">s</span></tt> being denoted
  98 by a <tt class="docutils literal"><span class="pre">gray</span></tt> entry in the color map and the traversal from <tt class="docutils literal"><span class="pre">t</span></tt>
  99 being denoted by a <tt class="docutils literal"><span class="pre">green</span></tt> entry.  The traversal method is similar
 100 to breadth-first search except that no visitor event points are
 101 called.  When any process detects a collision in the two traversals
 102 (by attempting to set a <tt class="docutils literal"><span class="pre">gray</span></tt> vertex to <tt class="docutils literal"><span class="pre">green</span></tt> or vice-versa),
 103 it signals all processes to terminate on the next superstep and all
 104 processes return <tt class="docutils literal"><span class="pre">true</span></tt>.  If the queues on all processes are empty
 105 and no collision is detected then all processes terminate and return
 106 <tt class="docutils literal"><span class="pre">false</span></tt>.</p>
 107 <hr class="docutils" />
 108 <p>Copyright (C) 2009 The Trustees of Indiana University.</p>
 109 <p>Authors: Nick Edmonds and Andrew Lumsdaine</p>
 110 </div>
 111 </div>
 112 <div class="footer">
 113 <hr class="footer" />
 114 Generated on: 2009-05-31 00:21 UTC.
 115 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.
 116
 117 </div>
 118 </body>
 119 </html>