123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119 |
- <?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>
|