bump version to 12.2.2-pve1

[ceph.git] / ceph / src / boost / libs / graph_parallel / doc / tsin_depth_first_visit.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| Depth-First Visit
========================

::

  template<typename DistributedGraph, typename DFSVisitor>
  void
  depth_first_visit(const DistributedGraph& g,
                    typename graph_traits<DistributedGraph>::vertex_descriptor s,
                    DFSVisitor vis);

  namespace graph {
    template<typename DistributedGraph, typename DFSVisitor, 
           typename VertexIndexMap>
    void
    tsin_depth_first_visit(const DistributedGraph& g,
                           typename graph_traits<DistributedGraph>::vertex_descriptor s,
                           DFSVisitor vis);

    template<typename DistributedGraph, typename DFSVisitor, 
             typename VertexIndexMap>
    void
    tsin_depth_first_visit(const DistributedGraph& g,
                           typename graph_traits<DistributedGraph>::vertex_descriptor s,
                           DFSVisitor vis, VertexIndexMap index_map);

    template<typename DistributedGraph, typename ColorMap, typename ParentMap,
             typename ExploreMap, typename NextOutEdgeMap, typename DFSVisitor>
    void
    tsin_depth_first_visit(const DistributedGraph& g,
                           typename graph_traits<DistributedGraph>::vertex_descriptor s,
                           DFSVisitor vis, ColorMap color, ParentMap parent, ExploreMap explore, 
                           NextOutEdgeMap next_out_edge);
  } 

The ``depth_first_visit()`` function performs a distributed
depth-first traversal of an undirected graph using Tsin's corrections
[Tsin02]_ to Cidon's algorithm [Cidon88]_. The distributed DFS is
syntactically similar 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 depth-first search`_ for the remainder of the
details. Visitors passed to depth-first search need to account for the
distribution of vertices across processes, because events will be
triggered on certain processes but not others. See the section
`Visitor Event Points`_ for details.

Where Defined
-------------
<``boost/graph/distributed/depth_first_search.hpp``>

also available in 

<``boost/graph/depth_first_search.hpp``>

Parameters
----------

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

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

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

IN: ``VertexIndexMap map``
  A model of `Readable Property Map`_ whose key type is the vertex
  descriptor type of the graph ``g`` and whose value type is an
  integral type. The property map should map from vertices to their
  (local) indices in the range *[0, num_vertices(g))*.

  **Default**: ``get(vertex_index, g)``

UTIL/OUT: ``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). 

  **Default**: A distributed ``iterator_property_map`` created from a
  ``std::vector`` of ``default_color_type``.

UTIL/OUT: ``ParentMap parent``
  The parent map must be a `Distributed Property Map`_ with the same
  process group as the graph ``g`` whose key and values types are the
  same as the vertex descriptor type of the graph ``g``. This
  property map holds the parent of each vertex in the depth-first
  search tree.

  **Default**: A distributed ``iterator_property_map`` created from a
  ``std::vector`` of the vertex descriptor type of the graph.

UTIL: ``ExploreMap explore``
  The explore map must be a `Distributed Property Map`_ with the same
  process group as the graph ``g`` whose key and values types are the
  same as the vertex descriptor type of the graph ``g``. 

  **Default**: A distributed ``iterator_property_map`` created from a
  ``std::vector`` of the vertex descriptor type of the graph.

UTIL: ``NextOutEdgeMap next_out_edge``
  The next out-edge map must be a `Distributed Property Map`_ with the
  same process group as the graph ``g`` whose key type is the vertex
  descriptor of the graph ``g`` and whose value type is the
  ``out_edge_iterator`` type of the graph. It is used internally to
  keep track of the next edge that should be traversed from each
  vertex.

  **Default**: A distributed ``iterator_property_map`` created from a
  ``std::vector`` of the ``out_edge_iterator`` type of the graph.

Complexity
----------
Depth-first search is inherently sequential, so parallel speedup is
very poor. Regardless of the number of processors, the algorithm will
not be faster than *O(V)*; see [Tsin02]_ for more details.

Visitor Event Points
--------------------
The `DFS Visitor`_ concept defines 8 event points that will be
triggered by the `sequential depth-first search`_. The distributed
DFS retains these 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``. 


``examine_vertex(u, g)``
  This will be invoked by the process owning the vertex ``u``. 

``examine_edge(e, g)``
  This will be invoked by the process owning the source vertex of
  ``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. 


``back_edge(e, g)``
  Some edges that would be forward or cross edges in the sequential
  DFS may be detected as back edges by the distributed DFS, so extra
  ``back_edge`` events may be received.

``forward_or_cross_edge(e, g)``
  Some edges that would be forward or cross edges in the sequential
  DFS may be detected as back edges by the distributed DFS, so fewer
  ``forward_or_cross_edge`` events may be received in the distributed
  algorithm than in the sequential case.

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

Making Visitors Safe for Distributed DFS
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The three most important things to remember when updating an existing
DFS visitor for distributed DFS or writing a new distributed DFS
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 DFS, e.g., requiring
   ``back_edge`` and ``forward_or_cross_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. 

Bibliography
------------

.. [Cidon88] Isreal Cidon. Yet another distributed depth-first-search
  algorithm. Information Processing Letters, 26(6):301--305, 1988.


.. [Tsin02] Y. H. Tsin. Some remarks on distributed depth-first
  search. Information Processing Letters, 82(4):173--178, 2002.

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

Copyright (C) 2005 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/depth_first_visit.html
.. _sequential depth-first search: http://www.boost.org/libs/graph/doc/depth_first_visit.html
.. _Distributed Graph: DistributedGraph.html
.. _Immediate Process Group: concepts/ImmediateProcessGroup.html
.. _Distributed Property Map: distributed_property_map.html
.. _DFS Visitor: http://www.boost.org/libs/graph/doc/DFSVisitor.html
.. _Readable Property Map: http://www.boost.org/libs/property_map/ReadablePropertyMap.html