123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269 |
- <?xml version="1.0" encoding="utf-8" ?>
- <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
- <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
- <head>
- <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
- <meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/" />
- <title>Parallel BGL Breadth-First Search</title>
- <link rel="stylesheet" href="../../../../rst.css" type="text/css" />
- </head>
- <body>
- <div class="document" id="logo-breadth-first-search">
- <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> Breadth-First Search</h1>
- <!-- 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) -->
- <pre class="literal-block">
- // named parameter version
- template <class Graph, class P, class T, class R>
- void breadth_first_search(Graph& G,
- typename graph_traits<Graph>::vertex_descriptor s,
- const bgl_named_params<P, T, R>& params);
- // non-named parameter version
- template <class Graph, class Buffer, class BFSVisitor,
- class ColorMap>
- void breadth_first_search(const Graph& g,
- typename graph_traits<Graph>::vertex_descriptor s,
- Buffer& Q, BFSVisitor vis, ColorMap color);
- </pre>
- <p>The <tt class="docutils literal"><span class="pre">breadth_first_search()</span></tt> function performs a distributed breadth-first
- traversal of a directed or undirected graph. The distributed BFS is
- syntactically equivalent to its <a class="reference external" href="http://www.boost.org/libs/graph/doc/breadth_first_search.html">sequential counterpart</a>, which
- provides additional background and discussion. Differences in
- semantics are highlighted here, and we refer the reader to the
- documentation of the <a class="reference external" href="http://www.boost.org/libs/graph/doc/breadth_first_search.html">sequential breadth-first search</a> for the
- remainder of the details.</p>
- <p>This distributed breadth-first search algorithm implements a
- <em>level-synchronized</em> breadth-first search, meaning that all vertices
- in a given level of the BFS tree will be processed (potentially in
- parallel) before any vertices from a successive level in the tree are
- processed. Distributed breadth-first search visitors should account
- for this behavior, a topic discussed further in <a class="reference internal" href="#visitor-event-points">Visitor Event
- Points</a>.</p>
- <div class="contents topic" id="contents">
- <p class="topic-title first">Contents</p>
- <ul class="simple">
- <li><a class="reference internal" href="#where-defined" id="id1">Where Defined</a></li>
- <li><a class="reference internal" href="#parameter-defaults" id="id2">Parameter Defaults</a></li>
- <li><a class="reference internal" href="#complexity" id="id3">Complexity</a></li>
- <li><a class="reference internal" href="#visitor-event-points" id="id4">Visitor Event Points</a><ul>
- <li><a class="reference internal" href="#making-visitors-safe-for-distributed-bfs" id="id5">Making Visitors Safe for Distributed BFS</a></li>
- <li><a class="reference internal" href="#distributed-bfs-visitor-example" id="id6">Distributed BFS Visitor Example</a></li>
- </ul>
- </li>
- <li><a class="reference internal" href="#performance" id="id7">Performance</a></li>
- </ul>
- </div>
- <div class="section" id="where-defined">
- <h1><a class="toc-backref" href="#id1">Where Defined</a></h1>
- <p><<tt class="docutils literal"><span class="pre">boost/graph/breadth_first_search.hpp</span></tt>></p>
- </div>
- <div class="section" id="parameter-defaults">
- <h1><a class="toc-backref" href="#id2">Parameter Defaults</a></h1>
- <p>All parameters of the <a class="reference external" href="http://www.boost.org/libs/graph/doc/breadth_first_search.html">sequential breadth-first search</a> are supported
- and have essentially the same meaning. Only differences are documented
- here.</p>
- <dl class="docutils">
- <dt>IN: <tt class="docutils literal"><span class="pre">Graph&</span> <span class="pre">g</span></tt></dt>
- <dd>The graph type must be a model of <a class="reference external" href="DistributedGraph.html">Distributed Graph</a>.</dd>
- <dt>IN: <tt class="docutils literal"><span class="pre">vertex_descriptor</span> <span class="pre">s</span></tt></dt>
- <dd>The start vertex must be the same in every process.</dd>
- <dt>IN: <tt class="docutils literal"><span class="pre">visitor(BFSVisitor</span> <span class="pre">vis)</span></tt></dt>
- <dd>The visitor must be a distributed BFS visitor. The suble differences
- between sequential and distributed BFS visitors are discussed in the
- section <a class="reference internal" href="#visitor-event-points">Visitor Event Points</a>.</dd>
- <dt>UTIL/OUT: <tt class="docutils literal"><span class="pre">color_map(ColorMap</span> <span class="pre">color)</span></tt></dt>
- <dd>The color map must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a> with the same
- process group as the graph <tt class="docutils literal"><span class="pre">g</span></tt> whose colors must monotonically
- darken (white -> gray -> black). The default value is a distributed
- <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> created from a <tt class="docutils literal"><span class="pre">std::vector</span></tt> of
- <tt class="docutils literal"><span class="pre">default_color_type</span></tt>.</dd>
- <dt>UTIL: <tt class="docutils literal"><span class="pre">buffer(Buffer&</span> <span class="pre">Q)</span></tt></dt>
- <dd><p class="first">The queue must be a distributed queue that passes vertices to their
- owning process. If already-visited vertices should not be visited
- again (as is typical for BFS), the queue must filter duplicates
- itself. The queue controls synchronization within the algorithm: its
- <tt class="docutils literal"><span class="pre">empty()</span></tt> method must not return <tt class="docutils literal"><span class="pre">true</span></tt> until all local queues
- are empty.</p>
- <dl class="last docutils">
- <dt><strong>Default:</strong> A <tt class="docutils literal"><span class="pre">distributed_queue</span></tt> of a <tt class="docutils literal"><span class="pre">filtered_queue</span></tt> over a</dt>
- <dd>standard <tt class="docutils literal"><span class="pre">boost::queue</span></tt>. This queue filters out duplicate
- vertices and distributes vertices appropriately.</dd>
- </dl>
- </dd>
- </dl>
- </div>
- <div class="section" id="complexity">
- <h1><a class="toc-backref" href="#id3">Complexity</a></h1>
- <p>This algorithm performs <em>O(V + E)</em> work in <em>d + 1</em> BSP supersteps,
- where <em>d</em> is the diameter of the connected component being
- searched. Over all supersteps, <em>O(E)</em> messages of constant size will
- be transmitted.</p>
- </div>
- <div class="section" id="visitor-event-points">
- <h1><a class="toc-backref" href="#id4">Visitor Event Points</a></h1>
- <p>The <a class="reference external" href="http://www.boost.org/libs/graph/doc/BFSVisitor.html">BFS Visitor</a> concept defines 9 event points that will be
- triggered by the <a class="reference external" href="http://www.boost.org/libs/graph/doc/breadth_first_search.html">sequential breadth-first search</a>. The distributed
- BFS retains these nine 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.</p>
- <dl class="docutils">
- <dt><tt class="docutils literal"><span class="pre">initialize_vertex(s,</span> <span class="pre">g)</span></tt></dt>
- <dd>This will be invoked by every process for each local vertex.</dd>
- <dt><tt class="docutils literal"><span class="pre">discover_vertex(u,</span> <span class="pre">g)</span></tt></dt>
- <dd>This will be invoked each time a process discovers a new vertex
- <tt class="docutils literal"><span class="pre">u</span></tt>. Due to incomplete information in distributed property maps,
- this event may be triggered many times for the same vertex <tt class="docutils literal"><span class="pre">u</span></tt>.</dd>
- <dt><tt class="docutils literal"><span class="pre">examine_vertex(u,</span> <span class="pre">g)</span></tt></dt>
- <dd>This will be invoked by the process owning the vertex <tt class="docutils literal"><span class="pre">u</span></tt>. If the
- distributed queue prevents duplicates, it will be invoked only
- once for a particular vertex <tt class="docutils literal"><span class="pre">u</span></tt>.</dd>
- <dt><tt class="docutils literal"><span class="pre">examine_edge(e,</span> <span class="pre">g)</span></tt></dt>
- <dd>This will be invoked by the process owning the source vertex of
- <tt class="docutils literal"><span class="pre">e</span></tt>. If the distributed queue prevents duplicates, it will be
- invoked only once for a particular edge <tt class="docutils literal"><span class="pre">e</span></tt>.</dd>
- <dt><tt class="docutils literal"><span class="pre">tree_edge(e,</span> <span class="pre">g)</span></tt></dt>
- <dd>Similar to <tt class="docutils literal"><span class="pre">examine_edge</span></tt>, this will be invoked by the process
- owning the source vertex and may be invoked only once. Unlike the
- sequential BFS, this event may be triggered even when the target has
- already been discovered (but by a different process). Thus, some
- <tt class="docutils literal"><span class="pre">non_tree_edge</span></tt> events in a sequential BFS may become
- <tt class="docutils literal"><span class="pre">tree_edge</span></tt> in a distributed BFS.</dd>
- <dt><tt class="docutils literal"><span class="pre">non_tree_edge(e,</span> <span class="pre">g)</span></tt></dt>
- <dd>Some <tt class="docutils literal"><span class="pre">non_tree_edge</span></tt> events in a sequential BFS may become
- <tt class="docutils literal"><span class="pre">tree_edge</span></tt> events in a distributed BFS. See the description of
- <tt class="docutils literal"><span class="pre">tree_edge</span></tt> for additional details.</dd>
- <dt><tt class="docutils literal"><span class="pre">gray_target(e,</span> <span class="pre">g)</span></tt></dt>
- <dd>As with <tt class="docutils literal"><span class="pre">tree_edge</span></tt> not knowing when another process has already
- discovered a vertex, <tt class="docutils literal"><span class="pre">gray_target</span></tt> events may occur in a
- distributed BFS when <tt class="docutils literal"><span class="pre">black_target</span></tt> events may occur in a
- sequential BFS, due to a lack of information on a given
- processor. The source of edge <tt class="docutils literal"><span class="pre">e</span></tt> will be local to the process
- executing this event.</dd>
- <dt><tt class="docutils literal"><span class="pre">black_target(e,</span> <span class="pre">g)</span></tt></dt>
- <dd>See documentation for <tt class="docutils literal"><span class="pre">gray_target</span></tt></dd>
- <dt><tt class="docutils literal"><span class="pre">finish_vertex(e,</span> <span class="pre">g)</span></tt></dt>
- <dd>See documentation for <tt class="docutils literal"><span class="pre">examine_vertex</span></tt>.</dd>
- </dl>
- <div class="section" id="making-visitors-safe-for-distributed-bfs">
- <h2><a class="toc-backref" href="#id5">Making Visitors Safe for Distributed BFS</a></h2>
- <p>The three most important things to remember when updating an existing
- BFS visitor for distributed BFS or writing a new distributed BFS
- visitor are:</p>
- <ol class="arabic simple">
- <li>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.</li>
- <li>Be sure that the visitor doesn't require precise event sequences
- that cannot be guaranteed by distributed BFS, e.g., requiring
- <tt class="docutils literal"><span class="pre">tree_edge</span></tt> and <tt class="docutils literal"><span class="pre">non_tree_edge</span></tt> events to be completely
- distinct.</li>
- <li>Be sure that the visitor can operate on incomplete
- information. This often includes using an appropriate reduction
- operation in a <a class="reference external" href="distributed_property_map.html">distributed property map</a> and verifying that
- results written are "better" that what was previously written.</li>
- </ol>
- </div>
- <div class="section" id="distributed-bfs-visitor-example">
- <h2><a class="toc-backref" href="#id6">Distributed BFS Visitor Example</a></h2>
- <p>To illustrate the differences between sequential and distributed BFS
- visitors, we consider a BFS visitor that places the distance from the
- source vertex to every other vertex in a property map. The sequential
- visitor is very simple:</p>
- <pre class="literal-block">
- template<typename DistanceMap>
- struct bfs_discovery_visitor : bfs_visitor<>
- {
- bfs_discovery_visitor(DistanceMap distance) : distance(distance) {}
- template<typename Edge, typename Graph>
- void tree_edge(Edge e, const Graph& g)
- {
- std::size_t new_distance = get(distance, source(e, g)) + 1;
- put(distance, target(e, g), new_distance);
- }
- private:
- DistanceMap distance;
- };
- </pre>
- <p>To revisit this code for distributed BFS, we consider the three points
- in the section <a class="reference internal" href="#making-visitors-safe-for-distributed-bfs">Making Visitors Safe for Distributed BFS</a>:</p>
- <ol class="arabic">
- <li><p class="first">The distance map will need to become distributed, because the
- distance to each vertex should be stored in the process owning the
- vertex. This is actually a requirement on the user to provide such
- a distributed property map, although in many cases the property map
- will automatically be distributed and no syntactic changes will be
- required.</p>
- </li>
- <li><p class="first">This visitor <em>does</em> require a precise sequence of events that may
- change with a distributed BFS. The extraneous <tt class="docutils literal"><span class="pre">tree_edge</span></tt> events
- that may occur could result in attempts to put distances into the
- distance map multiple times for a single vertex. We therefore need
- to consider bullet #3.</p>
- </li>
- <li><p class="first">Since multiple distance values may be written for each vertex, we
- must always choose the best value we can find to update the
- distance map. The distributed property map <tt class="docutils literal"><span class="pre">distance</span></tt> needs to
- resolve distances to the smallest distance it has seen. For
- instance, process 0 may find vertex <tt class="docutils literal"><span class="pre">u</span></tt> at level 3 but process 1
- finds it at level 5: the distance must remain at 3. To do this, we
- state that the property map's <em>role</em> is as a distance map, which
- introduces an appropriate reduction operation:</p>
- <pre class="literal-block">
- set_property_map_role(vertex_distance, distance);
- </pre>
- </li>
- </ol>
- <p>The resulting distributed BFS visitor (which also applies, with no
- changes, in the sequential BFS) is very similar to our original
- sequential BFS visitor. Note the single-line difference in the
- constructor:</p>
- <pre class="literal-block">
- template<typename DistanceMap>
- struct bfs_discovery_visitor : bfs_visitor<>
- {
- bfs_discovery_visitor(DistanceMap distance) : distance(distance)
- {
- set_property_map_role(vertex_distance, distance);
- }
- template<typename Edge, typename Graph>
- void tree_edge(Edge e, const Graph& g)
- {
- std::size_t new_distance = get(distance, source(e, g)) + 1;
- put(distance, target(e, g), new_distance);
- }
- private:
- DistanceMap distance;
- };
- </pre>
- </div>
- </div>
- <div class="section" id="performance">
- <h1><a class="toc-backref" href="#id7">Performance</a></h1>
- <p>The performance of Breadth-First Search is illustrated by the
- following charts. Scaling and performance is reasonable for all of the
- graphs we have tried.</p>
- <img align="left" alt="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_4.png" class="align-left" src="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_4.png" />
- <img alt="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_4_speedup_1.png" src="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_4_speedup_1.png" />
- <img align="left" alt="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_4.png" class="align-left" src="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_4.png" />
- <img alt="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_4_speedup_1.png" src="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_4_speedup_1.png" />
- <hr class="docutils" />
- <p>Copyright (C) 2004 The Trustees of Indiana University.</p>
- <p>Authors: Douglas Gregor and Andrew Lumsdaine</p>
- </div>
- </div>
- <div class="footer">
- <hr class="footer" />
- Generated on: 2009-05-31 00:21 UTC.
- Generated 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.
- </div>
- </body>
- </html>
|