boost_1_45_0/libs/graph_parallel/doc/st_connected.rst

.. 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<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`_.

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