1.. Copyright (C) 2004-2009 The Trustees of Indiana University. 2 Use, modification and distribution is subject to the Boost Software 3 License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 4 http://www.boost.org/LICENSE_1_0.txt) 5 6=========================== 7|Logo| s-t Connectivity 8=========================== 9 10:: 11 12 namespace graph { namespace distributed { 13 template<typename DistributedGraph, typename ColorMap> 14 inline bool 15 st_connected(const DistributedGraph& g, 16 typename graph_traits<DistributedGraph>::vertex_descriptor s, 17 typename graph_traits<DistributedGraph>::vertex_descriptor t, 18 ColorMap color) 19 20 template<typename DistributedGraph> 21 inline bool 22 st_connected(const DistributedGraph& g, 23 typename graph_traits<DistributedGraph>::vertex_descriptor s, 24 typename graph_traits<DistributedGraph>::vertex_descriptor t) 25 26 template<typename DistributedGraph, typename ColorMap, typename OwnerMap> 27 bool 28 st_connected(const DistributedGraph& g, 29 typename graph_traits<DistributedGraph>::vertex_descriptor s, 30 typename graph_traits<DistributedGraph>::vertex_descriptor t, 31 ColorMap color, OwnerMap owner) 32 } } 33 34The ``st_connected()`` function determines whether there exists a path 35from ``s`` to ``t`` in a graph ``g``. If a path exists the function 36returns ``true``, otherwise it returns ``false``. 37 38This algorithm is currently *level-synchronized*, meaning that all 39vertices in a given level of the search tree will be processed 40(potentially in parallel) before any vertices from a successive level 41in the tree are processed. This is not necessary for the correctness 42of the algorithm but rather is an implementation detail. This 43algorithm could be rewritten fully-asynchronously using triggers which 44would remove the level-synchronized behavior. 45 46.. contents:: 47 48Where Defined 49------------- 50<``boost/graph/distributed/st_connected.hpp``> 51 52Parameters 53---------- 54 55IN: ``const DistributedGraph& g`` 56 The graph type must be a model of `Distributed Graph`_. The graph 57 type must also model the `Incidence Graph`_. 58 59IN: ``vertex_descriptor s`` 60 61IN: ``vertex_descriptor t`` 62 63UTIL/OUT: ``color_map(ColorMap color)`` 64 The color map must be a `Distributed Property Map`_ with the same 65 process group as the graph ``g`` whose colors must monotonically 66 darken (white -> gray/green -> black). The default value is a 67 distributed ``two_bit_color_map``. 68 69IN: ``OwnerMap owner`` 70 The owner map must map from vertices to the process that owns them 71 as described in the `GlobalDescriptor`_ concept. 72 73OUT: ``bool`` 74 The algorithm returns ``true`` if a path from ``s`` to ``t`` is 75 found, and false otherwise. 76 77Complexity 78---------- 79 80This algorithm performs *O(V + E)* work in *d/2 + 1* BSP supersteps, 81where *d* is the shortest distance from ``s`` to ``t``. Over all 82supersteps, *O(E)* messages of constant size will be transmitted. 83 84Algorithm Description 85--------------------- 86 87The algorithm consists of two simultaneous breadth-first traversals 88from ``s`` and ``t`` respectively. The algorithm utilizes a single 89queue for both traversals with the traversal from ``s`` being denoted 90by a ``gray`` entry in the color map and the traversal from ``t`` 91being denoted by a ``green`` entry. The traversal method is similar 92to breadth-first search except that no visitor event points are 93called. When any process detects a collision in the two traversals 94(by attempting to set a ``gray`` vertex to ``green`` or vice-versa), 95it signals all processes to terminate on the next superstep and all 96processes return ``true``. If the queues on all processes are empty 97and no collision is detected then all processes terminate and return 98``false``. 99 100----------------------------------------------------------------------------- 101 102Copyright (C) 2009 The Trustees of Indiana University. 103 104Authors: Nick Edmonds and Andrew Lumsdaine 105 106.. |Logo| image:: pbgl-logo.png 107 :align: middle 108 :alt: Parallel BGL 109 :target: http://www.osl.iu.edu/research/pbgl 110 111.. _Distributed Graph: DistributedGraph.html 112.. _Incidence Graph: http://www.boost.org/libs/graph/doc/IncidenceGraph.html 113.. _Distributed Property Map: distributed_property_map.html 114.. _GlobalDescriptor: GlobalDescriptor.html
