1.. Copyright (C) 2004-2008 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| Depth-First Visit 8======================== 9 10:: 11 12 template<typename DistributedGraph, typename DFSVisitor> 13 void 14 depth_first_visit(const DistributedGraph& g, 15 typename graph_traits<DistributedGraph>::vertex_descriptor s, 16 DFSVisitor vis); 17 18 namespace graph { 19 template<typename DistributedGraph, typename DFSVisitor, 20 typename VertexIndexMap> 21 void 22 tsin_depth_first_visit(const DistributedGraph& g, 23 typename graph_traits<DistributedGraph>::vertex_descriptor s, 24 DFSVisitor vis); 25 26 template<typename DistributedGraph, typename DFSVisitor, 27 typename VertexIndexMap> 28 void 29 tsin_depth_first_visit(const DistributedGraph& g, 30 typename graph_traits<DistributedGraph>::vertex_descriptor s, 31 DFSVisitor vis, VertexIndexMap index_map); 32 33 template<typename DistributedGraph, typename ColorMap, typename ParentMap, 34 typename ExploreMap, typename NextOutEdgeMap, typename DFSVisitor> 35 void 36 tsin_depth_first_visit(const DistributedGraph& g, 37 typename graph_traits<DistributedGraph>::vertex_descriptor s, 38 DFSVisitor vis, ColorMap color, ParentMap parent, ExploreMap explore, 39 NextOutEdgeMap next_out_edge); 40 } 41 42The ``depth_first_visit()`` function performs a distributed 43depth-first traversal of an undirected graph using Tsin's corrections 44[Tsin02]_ to Cidon's algorithm [Cidon88]_. The distributed DFS is 45syntactically similar to its `sequential counterpart`_, which provides 46additional background and discussion. Differences in semantics are 47highlighted here, and we refer the reader to the documentation of the 48`sequential depth-first search`_ for the remainder of the 49details. Visitors passed to depth-first search need to account for the 50distribution of vertices across processes, because events will be 51triggered on certain processes but not others. See the section 52`Visitor Event Points`_ for details. 53 54Where Defined 55------------- 56<``boost/graph/distributed/depth_first_search.hpp``> 57 58also available in 59 60<``boost/graph/depth_first_search.hpp``> 61 62Parameters 63---------- 64 65IN: ``const Graph& g`` 66 The graph type must be a model of `Distributed Graph`_. The graph 67 must be undirected. 68 69IN: ``vertex_descriptor s`` 70 The start vertex must be the same in every process. 71 72IN: ``DFSVisitor vis`` 73 The visitor must be a distributed DFS visitor. The suble differences 74 between sequential and distributed DFS visitors are discussed in the 75 section `Visitor Event Points`_. 76 77IN: ``VertexIndexMap map`` 78 A model of `Readable Property Map`_ whose key type is the vertex 79 descriptor type of the graph ``g`` and whose value type is an 80 integral type. The property map should map from vertices to their 81 (local) indices in the range *[0, num_vertices(g))*. 82 83 **Default**: ``get(vertex_index, g)`` 84 85UTIL/OUT: ``ColorMap color`` 86 The color map must be a `Distributed Property Map`_ with the same 87 process group as the graph ``g`` whose colors must monotonically 88 darken (white -> gray -> black). 89 90 **Default**: A distributed ``iterator_property_map`` created from a 91 ``std::vector`` of ``default_color_type``. 92 93UTIL/OUT: ``ParentMap parent`` 94 The parent map must be a `Distributed Property Map`_ with the same 95 process group as the graph ``g`` whose key and values types are the 96 same as the vertex descriptor type of the graph ``g``. This 97 property map holds the parent of each vertex in the depth-first 98 search tree. 99 100 **Default**: A distributed ``iterator_property_map`` created from a 101 ``std::vector`` of the vertex descriptor type of the graph. 102 103UTIL: ``ExploreMap explore`` 104 The explore map must be a `Distributed Property Map`_ with the same 105 process group as the graph ``g`` whose key and values types are the 106 same as the vertex descriptor type of the graph ``g``. 107 108 **Default**: A distributed ``iterator_property_map`` created from a 109 ``std::vector`` of the vertex descriptor type of the graph. 110 111UTIL: ``NextOutEdgeMap next_out_edge`` 112 The next out-edge map must be a `Distributed Property Map`_ with the 113 same process group as the graph ``g`` whose key type is the vertex 114 descriptor of the graph ``g`` and whose value type is the 115 ``out_edge_iterator`` type of the graph. It is used internally to 116 keep track of the next edge that should be traversed from each 117 vertex. 118 119 **Default**: A distributed ``iterator_property_map`` created from a 120 ``std::vector`` of the ``out_edge_iterator`` type of the graph. 121 122Complexity 123---------- 124Depth-first search is inherently sequential, so parallel speedup is 125very poor. Regardless of the number of processors, the algorithm will 126not be faster than *O(V)*; see [Tsin02]_ for more details. 127 128Visitor Event Points 129-------------------- 130The `DFS Visitor`_ concept defines 8 event points that will be 131triggered by the `sequential depth-first search`_. The distributed 132DFS retains these event points, but the sequence of events 133triggered and the process in which each event occurs will change 134depending on the distribution of the graph. 135 136``initialize_vertex(s, g)`` 137 This will be invoked by every process for each local vertex. 138 139 140``discover_vertex(u, g)`` 141 This will be invoked each time a process discovers a new vertex 142 ``u``. 143 144 145``examine_vertex(u, g)`` 146 This will be invoked by the process owning the vertex ``u``. 147 148``examine_edge(e, g)`` 149 This will be invoked by the process owning the source vertex of 150 ``e``. 151 152 153``tree_edge(e, g)`` 154 Similar to ``examine_edge``, this will be invoked by the process 155 owning the source vertex and may be invoked only once. 156 157 158``back_edge(e, g)`` 159 Some edges that would be forward or cross edges in the sequential 160 DFS may be detected as back edges by the distributed DFS, so extra 161 ``back_edge`` events may be received. 162 163``forward_or_cross_edge(e, g)`` 164 Some edges that would be forward or cross edges in the sequential 165 DFS may be detected as back edges by the distributed DFS, so fewer 166 ``forward_or_cross_edge`` events may be received in the distributed 167 algorithm than in the sequential case. 168 169``finish_vertex(e, g)`` 170 See documentation for ``examine_vertex``. 171 172Making Visitors Safe for Distributed DFS 173~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 174The three most important things to remember when updating an existing 175DFS visitor for distributed DFS or writing a new distributed DFS 176visitor are: 177 1781. Be sure that all state is either entirely local or in a 179 distributed data structure (most likely a property map!) using 180 the same process group as the graph. 181 1822. Be sure that the visitor doesn't require precise event sequences 183 that cannot be guaranteed by distributed DFS, e.g., requiring 184 ``back_edge`` and ``forward_or_cross_edge`` events to be completely 185 distinct. 186 1873. Be sure that the visitor can operate on incomplete 188 information. This often includes using an appropriate reduction 189 operation in a `distributed property map`_ and verifying that 190 results written are "better" that what was previously written. 191 192Bibliography 193------------ 194 195.. [Cidon88] Isreal Cidon. Yet another distributed depth-first-search 196 algorithm. Information Processing Letters, 26(6):301--305, 1988. 197 198 199.. [Tsin02] Y. H. Tsin. Some remarks on distributed depth-first 200 search. Information Processing Letters, 82(4):173--178, 2002. 201 202----------------------------------------------------------------------------- 203 204Copyright (C) 2005 The Trustees of Indiana University. 205 206Authors: Douglas Gregor and Andrew Lumsdaine 207 208.. |Logo| image:: pbgl-logo.png 209 :align: middle 210 :alt: Parallel BGL 211 :target: http://www.osl.iu.edu/research/pbgl 212 213.. _sequential counterpart: http://www.boost.org/libs/graph/doc/depth_first_visit.html 214.. _sequential depth-first search: http://www.boost.org/libs/graph/doc/depth_first_visit.html 215.. _Distributed Graph: DistributedGraph.html 216.. _Immediate Process Group: concepts/ImmediateProcessGroup.html 217.. _Distributed Property Map: distributed_property_map.html 218.. _DFS Visitor: http://www.boost.org/libs/graph/doc/DFSVisitor.html 219.. _Readable Property Map: http://www.boost.org/libs/property_map/ReadablePropertyMap.html 220
