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<typename DistributedGraph, typename ColorMap> 21 inline bool 22 st_connected(const DistributedGraph& g, 23 typename graph_traits<DistributedGraph>::vertex_descriptor s, 24 typename graph_traits<DistributedGraph>::vertex_descriptor t, 25 ColorMap color) 26 27 template<typename DistributedGraph> 28 inline bool 29 st_connected(const DistributedGraph& g, 30 typename graph_traits<DistributedGraph>::vertex_descriptor s, 31 typename graph_traits<DistributedGraph>::vertex_descriptor t) 32 33 template<typename DistributedGraph, typename ColorMap, typename OwnerMap> 34 bool 35 st_connected(const DistributedGraph& g, 36 typename graph_traits<DistributedGraph>::vertex_descriptor s, 37 typename graph_traits<DistributedGraph>::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><<tt class="docutils literal"><span class="pre">boost/graph/distributed/st_connected.hpp</span></tt>></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&</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 -> gray/green -> 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> 120
