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. 15Use, modification and distribution is subject to the Boost Software 16License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 17http://www.boost.org/LICENSE_1_0.txt) --> 18<pre class="literal-block"> 19namespace 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 42from <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 43returns <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 45vertices in a given level of the search tree will be processed 46(potentially in parallel) before any vertices from a successive level 47in the tree are processed. This is not necessary for the correctness 48of the algorithm but rather is an implementation detail. This 49algorithm could be rewritten fully-asynchronously using triggers which 50would 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 69type 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 76process group as the graph <tt class="docutils literal"><span class="pre">g</span></tt> whose colors must monotonically 77darken (white -> gray/green -> black). The default value is a 78distributed <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 81as 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 84found, 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, 90where <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 91supersteps, <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 96from <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 97queue for both traversals with the traversal from <tt class="docutils literal"><span class="pre">s</span></tt> being denoted 98by 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> 99being denoted by a <tt class="docutils literal"><span class="pre">green</span></tt> entry. The traversal method is similar 100to breadth-first search except that no visitor event points are 101called. 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), 103it signals all processes to terminate on the next superstep and all 104processes return <tt class="docutils literal"><span class="pre">true</span></tt>. If the queues on all processes are empty 105and 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" /> 114Generated on: 2009-05-31 00:21 UTC. 115Generated 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
