boost_1_45_0/libs/graph_parallel/doc/tsin_depth_first_visit.rst - nest-learning-thermostat/5.1.5/boost - Git at Google

 .. 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
	.. 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