114 lines
4.3 KiB
ReStructuredText
114 lines
4.3 KiB
ReStructuredText
.. 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 |