.. 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) =========================== |Logo| s-t Connectivity =========================== :: namespace graph { namespace distributed { template inline bool st_connected(const DistributedGraph& g, typename graph_traits::vertex_descriptor s, typename graph_traits::vertex_descriptor t, ColorMap color) template inline bool st_connected(const DistributedGraph& g, typename graph_traits::vertex_descriptor s, typename graph_traits::vertex_descriptor t) template bool st_connected(const DistributedGraph& g, typename graph_traits::vertex_descriptor s, typename graph_traits::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`_. 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``. ----------------------------------------------------------------------------- Copyright (C) 2009 The Trustees of Indiana University. Authors: Nick Edmonds and Andrew Lumsdaine .. |Logo| image:: pbgl-logo.png :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