boost_1_45_0/libs/graph_parallel/doc/breadth_first_search.rst

.. Copyright (C) 2004-2008 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| Breadth-First Search
===========================

::

  // named parameter version
  template <class Graph, class P, class T, class R>
  void breadth_first_search(Graph& G, 
    typename graph_traits<Graph>::vertex_descriptor s, 
    const bgl_named_params<P, T, R>& params);

  // non-named parameter version
  template <class Graph, class Buffer, class BFSVisitor, 
            class ColorMap>
  void breadth_first_search(const Graph& g, 
     typename graph_traits<Graph>::vertex_descriptor s, 
     Buffer& Q, BFSVisitor vis, ColorMap color);

The ``breadth_first_search()`` function performs a distributed breadth-first
traversal of a directed or undirected graph. The distributed BFS is
syntactically equivalent to its `sequential counterpart`_, which
provides additional background and discussion. Differences in
semantics are highlighted here, and we refer the reader to the
documentation of the `sequential breadth-first search`_ for the
remainder of the details.

This distributed breadth-first search algorithm implements a
*level-synchronized* breadth-first search, meaning that all vertices
in a given level of the BFS tree will be processed (potentially in
parallel) before any vertices from a successive level in the tree are
processed. Distributed breadth-first search visitors should account
for this behavior, a topic discussed further in `Visitor Event
Points`_. 

.. contents::

Where Defined
-------------
<``boost/graph/breadth_first_search.hpp``>

Parameter Defaults
------------------
All parameters of the `sequential breadth-first search`_ are supported
and have essentially the same meaning. Only differences are documented
here.

IN: ``Graph& g``
  The graph type must be a model of `Distributed Graph`_. 


IN: ``vertex_descriptor s``
  The start vertex must be the same in every process.


IN: ``visitor(BFSVisitor vis)``
  The visitor must be a distributed BFS visitor. The suble differences
  between sequential and distributed BFS visitors are discussed in the
  section `Visitor Event Points`_.

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 -> black). The default value is a distributed
  ``iterator_property_map`` created from a ``std::vector`` of
  ``default_color_type``. 


UTIL: ``buffer(Buffer& Q)``
  The queue must be a distributed queue that passes vertices to their
  owning process. If already-visited vertices should not be visited
  again (as is typical for BFS), the queue must filter duplicates
  itself. The queue controls synchronization within the algorithm: its
  ``empty()`` method must not return ``true`` until all local queues
  are empty. 
  
  **Default:** A ``distributed_queue`` of a ``filtered_queue`` over a
    standard ``boost::queue``. This queue filters out duplicate
    vertices and distributes vertices appropriately.

Complexity
----------
This algorithm performs *O(V + E)* work in *d + 1* BSP supersteps,
where *d* is the diameter of the connected component being
searched. Over all supersteps, *O(E)* messages of constant size will
be transmitted.

Visitor Event Points
--------------------
The `BFS Visitor`_ concept defines 9 event points that will be
triggered by the `sequential breadth-first search`_. The distributed
BFS retains these nine event points, but the sequence of events
triggered and the process in which each event occurs will change
depending on the distribution of the graph. 

``initialize_vertex(s, g)``
  This will be invoked by every process for each local vertex.


``discover_vertex(u, g)``
  This will be invoked each time a process discovers a new vertex
  ``u``. Due to incomplete information in distributed property maps,
  this event may be triggered many times for the same vertex ``u``.


``examine_vertex(u, g)``
  This will be invoked by the process owning the vertex ``u``. If the
  distributed queue prevents duplicates, it will be invoked only
  once for a particular vertex ``u``.


``examine_edge(e, g)``
  This will be invoked by the process owning the source vertex of
  ``e``. If the distributed queue prevents duplicates, it will be
  invoked only once for a particular edge ``e``.


``tree_edge(e, g)``
  Similar to ``examine_edge``, this will be invoked by the process
  owning the source vertex and may be invoked only once. Unlike the
  sequential BFS, this event may be triggered even when the target has
  already been discovered (but by a different process). Thus, some
  ``non_tree_edge`` events in a sequential BFS may become
  ``tree_edge`` in a distributed BFS.


``non_tree_edge(e, g)``
  Some ``non_tree_edge`` events in a sequential BFS may become
  ``tree_edge`` events in a distributed BFS. See the description of
  ``tree_edge`` for additional details.


``gray_target(e, g)``
  As with ``tree_edge`` not knowing when another process has already
  discovered a vertex, ``gray_target`` events may occur in a
  distributed BFS when ``black_target`` events may occur in a
  sequential BFS, due to a lack of information on a given
  processor. The source of edge ``e`` will be local to the process
  executing this event.


``black_target(e, g)``
  See documentation for ``gray_target``


``finish_vertex(e, g)``
  See documentation for ``examine_vertex``.

Making Visitors Safe for Distributed BFS
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The three most important things to remember when updating an existing
BFS visitor for distributed BFS or writing a new distributed BFS
visitor are:

1. Be sure that all state is either entirely local or in a
   distributed data structure (most likely a property map!) using
   the same process group as the graph.

2. Be sure that the visitor doesn't require precise event sequences
   that cannot be guaranteed by distributed BFS, e.g., requiring
   ``tree_edge`` and ``non_tree_edge`` events to be completely
   distinct.

3. Be sure that the visitor can operate on incomplete
   information. This often includes using an appropriate reduction
   operation in a `distributed property map`_ and verifying that
   results written are "better" that what was previously written. 

Distributed BFS Visitor Example
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
To illustrate the differences between sequential and distributed BFS
visitors, we consider a BFS visitor that places the distance from the
source vertex to every other vertex in a property map. The sequential
visitor is very simple::

  template<typename DistanceMap>
  struct bfs_discovery_visitor : bfs_visitor<> 
  {
    bfs_discovery_visitor(DistanceMap distance) : distance(distance) {}

    template<typename Edge, typename Graph>
    void tree_edge(Edge e, const Graph& g)
    {
      std::size_t new_distance = get(distance, source(e, g)) + 1;
      put(distance, target(e, g), new_distance);
    }
    
   private:
    DistanceMap distance;
  };

To revisit this code for distributed BFS, we consider the three points
in the section `Making Visitors Safe for Distributed BFS`_:

1. The distance map will need to become distributed, because the
   distance to each vertex should be stored in the process owning the
   vertex. This is actually a requirement on the user to provide such
   a distributed property map, although in many cases the property map
   will automatically be distributed and no syntactic changes will be
   required. 

2. This visitor *does* require a precise sequence of events that may
   change with a distributed BFS. The extraneous ``tree_edge`` events
   that may occur could result in attempts to put distances into the
   distance map multiple times for a single vertex. We therefore need
   to consider bullet #3.

3. Since multiple distance values may be written for each vertex, we
   must always choose the best value we can find to update the
   distance map. The distributed property map ``distance`` needs to
   resolve distances to the smallest distance it has seen. For
   instance, process 0 may find vertex ``u`` at level 3 but process 1
   finds it at level 5: the distance must remain at 3. To do this, we
   state that the property map's *role* is as a distance map, which
   introduces an appropriate reduction operation::

          set_property_map_role(vertex_distance, distance);

The resulting distributed BFS visitor (which also applies, with no
changes, in the sequential BFS) is very similar to our original
sequential BFS visitor. Note the single-line difference in the
constructor::

  template<typename DistanceMap>
  struct bfs_discovery_visitor : bfs_visitor<> 
  {
    bfs_discovery_visitor(DistanceMap distance) : distance(distance) 
    {
      set_property_map_role(vertex_distance, distance);
    }

    template<typename Edge, typename Graph>
    void tree_edge(Edge e, const Graph& g)
    {
      std::size_t new_distance = get(distance, source(e, g)) + 1;
      put(distance, target(e, g), new_distance);
    }
    
   private:
    DistanceMap distance;
  };


Performance
-----------
The performance of Breadth-First Search is illustrated by the
following charts. Scaling and performance is reasonable for all of the
graphs we have tried. 

.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeSparse&columns=4
  :align: left
.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeSparse&columns=4&speedup=1

.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeDense&columns=4
  :align: left
.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeDense&columns=4&speedup=1

-----------------------------------------------------------------------------

Copyright (C) 2004 The Trustees of Indiana University.

Authors: Douglas Gregor and Andrew Lumsdaine

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

.. _sequential counterpart: http://www.boost.org/libs/graph/doc/breadth_first_search.html
.. _sequential breadth-first search: http://www.boost.org/libs/graph/doc/breadth_first_search.html
.. _Distributed Graph: DistributedGraph.html
.. _Distributed Property Map: distributed_property_map.html
.. _BFS Visitor: http://www.boost.org/libs/graph/doc/BFSVisitor.html