.. 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 void depth_first_visit(const DistributedGraph& g, typename graph_traits::vertex_descriptor s, DFSVisitor vis); namespace graph { template void tsin_depth_first_visit(const DistributedGraph& g, typename graph_traits::vertex_descriptor s, DFSVisitor vis); template void tsin_depth_first_visit(const DistributedGraph& g, typename graph_traits::vertex_descriptor s, DFSVisitor vis, VertexIndexMap index_map); template void tsin_depth_first_visit(const DistributedGraph& g, typename graph_traits::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