1<?xml version="1.0" encoding="utf-8" ?> 2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"> 4<head> 5<meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> 6<meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/" /> 7<title>Parallel BGL Depth-First Visit</title> 8<link rel="stylesheet" href="../../../../rst.css" type="text/css" /> 9</head> 10<body> 11<div class="document" id="logo-depth-first-visit"> 12<h1 class="title"><a class="reference external" href="http://www.osl.iu.edu/research/pbgl"><img align="middle" alt="Parallel BGL" class="align-middle" src="pbgl-logo.png" /></a> Depth-First Visit</h1> 13 14<!-- Copyright (C) 2004-2008 The Trustees of Indiana University. 15Use, modification and distribution is subject to the Boost Software 16License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 17http://www.boost.org/LICENSE_1_0.txt) --> 18<pre class="literal-block"> 19template<typename DistributedGraph, typename DFSVisitor> 20void 21depth_first_visit(const DistributedGraph& g, 22 typename graph_traits<DistributedGraph>::vertex_descriptor s, 23 DFSVisitor vis); 24 25namespace graph { 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); 32 33 template<typename DistributedGraph, typename DFSVisitor, 34 typename VertexIndexMap> 35 void 36 tsin_depth_first_visit(const DistributedGraph& g, 37 typename graph_traits<DistributedGraph>::vertex_descriptor s, 38 DFSVisitor vis, VertexIndexMap index_map); 39 40 template<typename DistributedGraph, typename ColorMap, typename ParentMap, 41 typename ExploreMap, typename NextOutEdgeMap, typename DFSVisitor> 42 void 43 tsin_depth_first_visit(const DistributedGraph& g, 44 typename graph_traits<DistributedGraph>::vertex_descriptor s, 45 DFSVisitor vis, ColorMap color, ParentMap parent, ExploreMap explore, 46 NextOutEdgeMap next_out_edge); 47} 48</pre> 49<p>The <tt class="docutils literal"><span class="pre">depth_first_visit()</span></tt> function performs a distributed 50depth-first traversal of an undirected graph using Tsin's corrections 51<a class="citation-reference" href="#tsin02" id="id1">[Tsin02]</a> to Cidon's algorithm <a class="citation-reference" href="#cidon88" id="id2">[Cidon88]</a>. The distributed DFS is 52syntactically similar to its <a class="reference external" href="http://www.boost.org/libs/graph/doc/depth_first_visit.html">sequential counterpart</a>, which provides 53additional background and discussion. Differences in semantics are 54highlighted here, and we refer the reader to the documentation of the 55<a class="reference external" href="http://www.boost.org/libs/graph/doc/depth_first_visit.html">sequential depth-first search</a> for the remainder of the 56details. Visitors passed to depth-first search need to account for the 57distribution of vertices across processes, because events will be 58triggered on certain processes but not others. See the section 59<a class="reference internal" href="#visitor-event-points">Visitor Event Points</a> for details.</p> 60<div class="section" id="where-defined"> 61<h1>Where Defined</h1> 62<p><<tt class="docutils literal"><span class="pre">boost/graph/distributed/depth_first_search.hpp</span></tt>></p> 63<p>also available in</p> 64<p><<tt class="docutils literal"><span class="pre">boost/graph/depth_first_search.hpp</span></tt>></p> 65</div> 66<div class="section" id="parameters"> 67<h1>Parameters</h1> 68<dl class="docutils"> 69<dt>IN: <tt class="docutils literal"><span class="pre">const</span> <span class="pre">Graph&</span> <span class="pre">g</span></tt></dt> 70<dd>The graph type must be a model of <a class="reference external" href="DistributedGraph.html">Distributed Graph</a>. The graph 71must be undirected.</dd> 72<dt>IN: <tt class="docutils literal"><span class="pre">vertex_descriptor</span> <span class="pre">s</span></tt></dt> 73<dd>The start vertex must be the same in every process.</dd> 74<dt>IN: <tt class="docutils literal"><span class="pre">DFSVisitor</span> <span class="pre">vis</span></tt></dt> 75<dd>The visitor must be a distributed DFS visitor. The suble differences 76between sequential and distributed DFS visitors are discussed in the 77section <a class="reference internal" href="#visitor-event-points">Visitor Event Points</a>.</dd> 78<dt>IN: <tt class="docutils literal"><span class="pre">VertexIndexMap</span> <span class="pre">map</span></tt></dt> 79<dd><p class="first">A model of <a class="reference external" href="http://www.boost.org/libs/property_map/ReadablePropertyMap.html">Readable Property Map</a> whose key type is the vertex 80descriptor type of the graph <tt class="docutils literal"><span class="pre">g</span></tt> and whose value type is an 81integral type. The property map should map from vertices to their 82(local) indices in the range <em>[0, num_vertices(g))</em>.</p> 83<p class="last"><strong>Default</strong>: <tt class="docutils literal"><span class="pre">get(vertex_index,</span> <span class="pre">g)</span></tt></p> 84</dd> 85<dt>UTIL/OUT: <tt class="docutils literal"><span class="pre">ColorMap</span> <span class="pre">color</span></tt></dt> 86<dd><p class="first">The color map must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a> with the same 87process group as the graph <tt class="docutils literal"><span class="pre">g</span></tt> whose colors must monotonically 88darken (white -> gray -> black).</p> 89<p class="last"><strong>Default</strong>: A distributed <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> created from a 90<tt class="docutils literal"><span class="pre">std::vector</span></tt> of <tt class="docutils literal"><span class="pre">default_color_type</span></tt>.</p> 91</dd> 92<dt>UTIL/OUT: <tt class="docutils literal"><span class="pre">ParentMap</span> <span class="pre">parent</span></tt></dt> 93<dd><p class="first">The parent map must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a> with the same 94process group as the graph <tt class="docutils literal"><span class="pre">g</span></tt> whose key and values types are the 95same as the vertex descriptor type of the graph <tt class="docutils literal"><span class="pre">g</span></tt>. This 96property map holds the parent of each vertex in the depth-first 97search tree.</p> 98<p class="last"><strong>Default</strong>: A distributed <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> created from a 99<tt class="docutils literal"><span class="pre">std::vector</span></tt> of the vertex descriptor type of the graph.</p> 100</dd> 101<dt>UTIL: <tt class="docutils literal"><span class="pre">ExploreMap</span> <span class="pre">explore</span></tt></dt> 102<dd><p class="first">The explore map must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a> with the same 103process group as the graph <tt class="docutils literal"><span class="pre">g</span></tt> whose key and values types are the 104same as the vertex descriptor type of the graph <tt class="docutils literal"><span class="pre">g</span></tt>.</p> 105<p class="last"><strong>Default</strong>: A distributed <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> created from a 106<tt class="docutils literal"><span class="pre">std::vector</span></tt> of the vertex descriptor type of the graph.</p> 107</dd> 108<dt>UTIL: <tt class="docutils literal"><span class="pre">NextOutEdgeMap</span> <span class="pre">next_out_edge</span></tt></dt> 109<dd><p class="first">The next out-edge map must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a> with the 110same process group as the graph <tt class="docutils literal"><span class="pre">g</span></tt> whose key type is the vertex 111descriptor of the graph <tt class="docutils literal"><span class="pre">g</span></tt> and whose value type is the 112<tt class="docutils literal"><span class="pre">out_edge_iterator</span></tt> type of the graph. It is used internally to 113keep track of the next edge that should be traversed from each 114vertex.</p> 115<p class="last"><strong>Default</strong>: A distributed <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> created from a 116<tt class="docutils literal"><span class="pre">std::vector</span></tt> of the <tt class="docutils literal"><span class="pre">out_edge_iterator</span></tt> type of the graph.</p> 117</dd> 118</dl> 119</div> 120<div class="section" id="complexity"> 121<h1>Complexity</h1> 122<p>Depth-first search is inherently sequential, so parallel speedup is 123very poor. Regardless of the number of processors, the algorithm will 124not be faster than <em>O(V)</em>; see <a class="citation-reference" href="#tsin02" id="id3">[Tsin02]</a> for more details.</p> 125</div> 126<div class="section" id="visitor-event-points"> 127<h1>Visitor Event Points</h1> 128<p>The <a class="reference external" href="http://www.boost.org/libs/graph/doc/DFSVisitor.html">DFS Visitor</a> concept defines 8 event points that will be 129triggered by the <a class="reference external" href="http://www.boost.org/libs/graph/doc/depth_first_visit.html">sequential depth-first search</a>. The distributed 130DFS retains these event points, but the sequence of events 131triggered and the process in which each event occurs will change 132depending on the distribution of the graph.</p> 133<dl class="docutils"> 134<dt><tt class="docutils literal"><span class="pre">initialize_vertex(s,</span> <span class="pre">g)</span></tt></dt> 135<dd>This will be invoked by every process for each local vertex.</dd> 136<dt><tt class="docutils literal"><span class="pre">discover_vertex(u,</span> <span class="pre">g)</span></tt></dt> 137<dd>This will be invoked each time a process discovers a new vertex 138<tt class="docutils literal"><span class="pre">u</span></tt>.</dd> 139<dt><tt class="docutils literal"><span class="pre">examine_vertex(u,</span> <span class="pre">g)</span></tt></dt> 140<dd>This will be invoked by the process owning the vertex <tt class="docutils literal"><span class="pre">u</span></tt>.</dd> 141<dt><tt class="docutils literal"><span class="pre">examine_edge(e,</span> <span class="pre">g)</span></tt></dt> 142<dd>This will be invoked by the process owning the source vertex of 143<tt class="docutils literal"><span class="pre">e</span></tt>.</dd> 144<dt><tt class="docutils literal"><span class="pre">tree_edge(e,</span> <span class="pre">g)</span></tt></dt> 145<dd>Similar to <tt class="docutils literal"><span class="pre">examine_edge</span></tt>, this will be invoked by the process 146owning the source vertex and may be invoked only once.</dd> 147<dt><tt class="docutils literal"><span class="pre">back_edge(e,</span> <span class="pre">g)</span></tt></dt> 148<dd>Some edges that would be forward or cross edges in the sequential 149DFS may be detected as back edges by the distributed DFS, so extra 150<tt class="docutils literal"><span class="pre">back_edge</span></tt> events may be received.</dd> 151<dt><tt class="docutils literal"><span class="pre">forward_or_cross_edge(e,</span> <span class="pre">g)</span></tt></dt> 152<dd>Some edges that would be forward or cross edges in the sequential 153DFS may be detected as back edges by the distributed DFS, so fewer 154<tt class="docutils literal"><span class="pre">forward_or_cross_edge</span></tt> events may be received in the distributed 155algorithm than in the sequential case.</dd> 156<dt><tt class="docutils literal"><span class="pre">finish_vertex(e,</span> <span class="pre">g)</span></tt></dt> 157<dd>See documentation for <tt class="docutils literal"><span class="pre">examine_vertex</span></tt>.</dd> 158</dl> 159<div class="section" id="making-visitors-safe-for-distributed-dfs"> 160<h2>Making Visitors Safe for Distributed DFS</h2> 161<p>The three most important things to remember when updating an existing 162DFS visitor for distributed DFS or writing a new distributed DFS 163visitor are:</p> 164<ol class="arabic simple"> 165<li>Be sure that all state is either entirely local or in a 166distributed data structure (most likely a property map!) using 167the same process group as the graph.</li> 168<li>Be sure that the visitor doesn't require precise event sequences 169that cannot be guaranteed by distributed DFS, e.g., requiring 170<tt class="docutils literal"><span class="pre">back_edge</span></tt> and <tt class="docutils literal"><span class="pre">forward_or_cross_edge</span></tt> events to be completely 171distinct.</li> 172<li>Be sure that the visitor can operate on incomplete 173information. This often includes using an appropriate reduction 174operation in a <a class="reference external" href="distributed_property_map.html">distributed property map</a> and verifying that 175results written are "better" that what was previously written.</li> 176</ol> 177</div> 178</div> 179<div class="section" id="bibliography"> 180<h1>Bibliography</h1> 181<table class="docutils citation" frame="void" id="cidon88" rules="none"> 182<colgroup><col class="label" /><col /></colgroup> 183<tbody valign="top"> 184<tr><td class="label"><a class="fn-backref" href="#id2">[Cidon88]</a></td><td>Isreal Cidon. Yet another distributed depth-first-search 185algorithm. Information Processing Letters, 26(6):301--305, 1988.</td></tr> 186</tbody> 187</table> 188<table class="docutils citation" frame="void" id="tsin02" rules="none"> 189<colgroup><col class="label" /><col /></colgroup> 190<tbody valign="top"> 191<tr><td class="label">[Tsin02]</td><td><em>(<a class="fn-backref" href="#id1">1</a>, <a class="fn-backref" href="#id3">2</a>)</em> Y. H. Tsin. Some remarks on distributed depth-first 192search. Information Processing Letters, 82(4):173--178, 2002.</td></tr> 193</tbody> 194</table> 195<hr class="docutils" /> 196<p>Copyright (C) 2005 The Trustees of Indiana University.</p> 197<p>Authors: Douglas Gregor and Andrew Lumsdaine</p> 198</div> 199</div> 200<div class="footer"> 201<hr class="footer" /> 202Generated on: 2009-05-31 00:21 UTC. 203Generated by <a class="reference external" href="http://docutils.sourceforge.net/">Docutils</a> from <a class="reference external" href="http://docutils.sourceforge.net/rst.html">reStructuredText</a> source. 204 205</div> 206</body> 207</html> 208
