Subject: [Boost-commit] svn:boost r53365 - trunk/libs/graph_parallel/doc
From: ngedmond_at_[hidden]
Date: 2009-05-28 18:00:33
Author: ngedmond
Date: 2009-05-28 18:00:33 EDT (Thu, 28 May 2009)
New Revision: 53365
URL: http://svn.boost.org/trac/boost/changeset/53365
Log:
Added documentation for st_connected() algorithm
Text files modified:
trunk/libs/graph_parallel/doc/st_connected.rst | 94 ++++++++++++++++++++++++++++++++++++++++
1 files changed, 94 insertions(+), 0 deletions(-)
Modified: trunk/libs/graph_parallel/doc/st_connected.rst
==============================================================================
--- trunk/libs/graph_parallel/doc/st_connected.rst (original)
+++ trunk/libs/graph_parallel/doc/st_connected.rst 2009-05-28 18:00:33 EDT (Thu, 28 May 2009)
@@ -7,6 +7,95 @@
|Logo| s-t Connectivity
===========================
+::
+
+ 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)
+ } }
+
+The ``st_connected()`` function determines whether there exists a path
+from ``s`` to ``t`` in a graph ``g``. If a path exists the function
+returns ``true``, otherwise it returns ``false``.
+
+This algorithm is currently *level-synchronized*, 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.
+
+.. contents::
+
+Where Defined
+-------------
+<``boost/graph/distributed/st_connected.hpp``>
+
+Parameters
+----------
+
+IN: ``const DistributedGraph& g``
+ The graph type must be a model of `Distributed Graph`_. The graph
+ type must also model the `Incidence Graph`_ and be directed.
+
+IN: ``vertex_descriptor s``
+
+IN: ``vertex_descriptor t``
+
+UTIL/OUT: ``color_map(ColorMap color)``
+ The color map must be a `Distributed Property Map`_ with the same
+ process group as the graph ``g`` whose colors must monotonically
+ darken (white -> gray/green -> black). The default value is a
+ distributed ``two_bit_color_map``.
+
+IN: ``OwnerMap owner``
+ The owner map must map from vertices to the process that owns them
+ as described in the `GlobalDescriptor`_ concept.
+
+OUT: ``bool``
+ The algorithm returns ``true`` if a path from ``s`` to ``t`` is
+ found, and false otherwise.
+
+Complexity
+----------
+
+This algorithm performs *O(V + E)* work in *d/2 + 1* BSP supersteps,
+where *d* is the shortest distance from ``s`` to ``t``. Over all
+supersteps, *O(E)* messages of constant size will be transmitted.
+
+Algorithm Description
+---------------------
+
+The algorithm consists of two simultaneous breadth-first traversals
+from ``s`` and ``t`` respectively. The algorithm utilizes a single
+queue for both traversals with the traversal from ``s`` being denoted
+by a ``gray`` entry in the color map and the traversal from ``t``
+being denoted by a ``green`` 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 ``gray`` vertex to ``green`` or vice-versa),
+it signals all processes to terminate on the next superstep and all
+processes return ``true``. If the queues on all processes are empty
+and no collision is detected then all processes terminate and return
+``false``.
-----------------------------------------------------------------------------
@@ -18,3 +107,8 @@
:align: middle
:alt: Parallel BGL
:target: http://www.osl.iu.edu/research/pbgl
+
+.. _Distributed Graph: DistributedGraph.html
+.. _Incidence Graph: http://www.boost.org/libs/graph/doc/IncidenceGraph.html
+.. _Distributed Property Map: distributed_property_map.html
+.. _GlobalDescriptor: GlobalDescriptor.html
\ No newline at end of file