<?xml version="1.0" encoding="utf-8" ?> <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"> <head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> <meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/" /> <title>Parallel BGL s-t Connectivity</title> <link rel="stylesheet" href="../../../../rst.css" type="text/css" /> </head> <body> <div class="document" id="logo-s-t-connectivity"> <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> <!-- Copyright (C) 2004-2009 The Trustees of Indiana University. Use, modification and distribution is subject to the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) --> <pre class="literal-block"> namespace graph { namespace distributed { template<typename DistributedGraph, typename ColorMap> inline bool st_connected(const DistributedGraph& g, typename graph_traits<DistributedGraph>::vertex_descriptor s, typename graph_traits<DistributedGraph>::vertex_descriptor t, ColorMap color) template<typename DistributedGraph> inline bool st_connected(const DistributedGraph& g, typename graph_traits<DistributedGraph>::vertex_descriptor s, typename graph_traits<DistributedGraph>::vertex_descriptor t) template<typename DistributedGraph, typename ColorMap, typename OwnerMap> bool st_connected(const DistributedGraph& g, typename graph_traits<DistributedGraph>::vertex_descriptor s, typename graph_traits<DistributedGraph>::vertex_descriptor t, ColorMap color, OwnerMap owner) } } </pre> <p>The <tt class="docutils literal"><span class="pre">st_connected()</span></tt> function determines whether there exists a path 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 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> <p>This algorithm is currently <em>level-synchronized</em>, meaning that all vertices in a given level of the search tree will be processed (potentially in parallel) before any vertices from a successive level in the tree are processed. This is not necessary for the correctness of the algorithm but rather is an implementation detail. This algorithm could be rewritten fully-asynchronously using triggers which would remove the level-synchronized behavior.</p> <div class="contents topic" id="contents"> <p class="topic-title first">Contents</p> <ul class="simple"> <li><a class="reference internal" href="#where-defined" id="id1">Where Defined</a></li> <li><a class="reference internal" href="#parameters" id="id2">Parameters</a></li> <li><a class="reference internal" href="#complexity" id="id3">Complexity</a></li> <li><a class="reference internal" href="#algorithm-description" id="id4">Algorithm Description</a></li> </ul> </div> <div class="section" id="where-defined"> <h1><a class="toc-backref" href="#id1">Where Defined</a></h1> <p><<tt class="docutils literal"><span class="pre">boost/graph/distributed/st_connected.hpp</span></tt>></p> </div> <div class="section" id="parameters"> <h1><a class="toc-backref" href="#id2">Parameters</a></h1> <dl class="docutils"> <dt>IN: <tt class="docutils literal"><span class="pre">const</span> <span class="pre">DistributedGraph&</span> <span class="pre">g</span></tt></dt> <dd>The graph type must be a model of <a class="reference external" href="DistributedGraph.html">Distributed Graph</a>. The graph type must also model the <a class="reference external" href="http://www.boost.org/libs/graph/doc/IncidenceGraph.html">Incidence Graph</a>.</dd> </dl> <p>IN: <tt class="docutils literal"><span class="pre">vertex_descriptor</span> <span class="pre">s</span></tt></p> <p>IN: <tt class="docutils literal"><span class="pre">vertex_descriptor</span> <span class="pre">t</span></tt></p> <dl class="docutils"> <dt>UTIL/OUT: <tt class="docutils literal"><span class="pre">color_map(ColorMap</span> <span class="pre">color)</span></tt></dt> <dd>The color map must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a> with the same process group as the graph <tt class="docutils literal"><span class="pre">g</span></tt> whose colors must monotonically darken (white -> gray/green -> black). The default value is a distributed <tt class="docutils literal"><span class="pre">two_bit_color_map</span></tt>.</dd> <dt>IN: <tt class="docutils literal"><span class="pre">OwnerMap</span> <span class="pre">owner</span></tt></dt> <dd>The owner map must map from vertices to the process that owns them as described in the <a class="reference external" href="GlobalDescriptor.html">GlobalDescriptor</a> concept.</dd> <dt>OUT: <tt class="docutils literal"><span class="pre">bool</span></tt></dt> <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 found, and false otherwise.</dd> </dl> </div> <div class="section" id="complexity"> <h1><a class="toc-backref" href="#id3">Complexity</a></h1> <p>This algorithm performs <em>O(V + E)</em> work in <em>d/2 + 1</em> BSP supersteps, 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 supersteps, <em>O(E)</em> messages of constant size will be transmitted.</p> </div> <div class="section" id="algorithm-description"> <h1><a class="toc-backref" href="#id4">Algorithm Description</a></h1> <p>The algorithm consists of two simultaneous breadth-first traversals 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 queue for both traversals with the traversal from <tt class="docutils literal"><span class="pre">s</span></tt> being denoted 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> being denoted by a <tt class="docutils literal"><span class="pre">green</span></tt> entry. The traversal method is similar to breadth-first search except that no visitor event points are called. When any process detects a collision in the two traversals (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), it signals all processes to terminate on the next superstep and all processes return <tt class="docutils literal"><span class="pre">true</span></tt>. If the queues on all processes are empty and no collision is detected then all processes terminate and return <tt class="docutils literal"><span class="pre">false</span></tt>.</p> <hr class="docutils" /> <p>Copyright (C) 2009 The Trustees of Indiana University.</p> <p>Authors: Nick Edmonds and Andrew Lumsdaine</p> </div> </div> <div class="footer"> <hr class="footer" /> Generated on: 2009-05-31 00:21 UTC. 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. </div> </body> </html>