ceph/src/boost/libs/graph_parallel/doc/st_connected.rst

   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
  34 The ``st_connected()`` function determines whether there exists a path
  35 from ``s`` to ``t`` in a graph ``g``.  If a path exists the function
  36 returns ``true``, otherwise it returns ``false``.
  37
  38 This algorithm is currently *level-synchronized*, meaning that all
  39 vertices in a given level of the search tree will be processed
  40 (potentially in parallel) before any vertices from a successive level
  41 in the tree are processed.  This is not necessary for the correctness
  42 of the algorithm but rather is an implementation detail.  This
  43 algorithm could be rewritten fully-asynchronously using triggers which
  44 would remove the level-synchronized behavior.
  45
  46 .. contents::
  47
  48 Where Defined
  49 -------------
  50 <``boost/graph/distributed/st_connected.hpp``>
  51
  52 Parameters
  53 ----------
  54
  55 IN:  ``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
  59 IN:  ``vertex_descriptor s``
  60
  61 IN:  ``vertex_descriptor t``
  62
  63 UTIL/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
  69 IN:  ``OwnerMap owner``
  70   The owner map must map from vertices to the process that owns them
  71   as described in the `GlobalDescriptor`_ concept.
  72
  73 OUT:  ``bool``
  74   The algorithm returns ``true`` if a path from ``s`` to ``t`` is
  75   found, and false otherwise.
  76
  77 Complexity
  78 ----------
  79
  80 This algorithm performs *O(V + E)* work in *d/2 + 1* BSP supersteps,
  81 where *d* is the shortest distance from ``s`` to ``t``. Over all
  82 supersteps, *O(E)* messages of constant size will be transmitted.
  83
  84 Algorithm Description
  85 ---------------------
  86
  87 The algorithm consists of two simultaneous breadth-first traversals
  88 from ``s`` and ``t`` respectively.  The algorithm utilizes a single
  89 queue for both traversals with the traversal from ``s`` being denoted
  90 by a ``gray`` entry in the color map and the traversal from ``t``
  91 being denoted by a ``green`` entry.  The traversal method is similar
  92 to breadth-first search except that no visitor event points are
  93 called.  When any process detects a collision in the two traversals
  94 (by attempting to set a ``gray`` vertex to ``green`` or vice-versa),
  95 it signals all processes to terminate on the next superstep and all
  96 processes return ``true``.  If the queues on all processes are empty
  97 and no collision is detected then all processes terminate and return
  98 ``false``.
  99
 100 -----------------------------------------------------------------------------
 101
 102 Copyright (C) 2009 The Trustees of Indiana University.
 103
 104 Authors: 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