279 lines
10 KiB
ReStructuredText
279 lines
10 KiB
ReStructuredText
.. 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| Breadth-First Search
|
|
===========================
|
|
|
|
::
|
|
|
|
// 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);
|
|
|
|
The ``breadth_first_search()`` function performs a distributed breadth-first
|
|
traversal of a directed or undirected graph. The distributed BFS is
|
|
syntactically equivalent 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 breadth-first search`_ for the
|
|
remainder of the details.
|
|
|
|
This distributed breadth-first search algorithm implements a
|
|
*level-synchronized* 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 `Visitor Event
|
|
Points`_.
|
|
|
|
.. contents::
|
|
|
|
Where Defined
|
|
-------------
|
|
<``boost/graph/breadth_first_search.hpp``>
|
|
|
|
Parameter Defaults
|
|
------------------
|
|
All parameters of the `sequential breadth-first search`_ are supported
|
|
and have essentially the same meaning. Only differences are documented
|
|
here.
|
|
|
|
IN: ``Graph& g``
|
|
The graph type must be a model of `Distributed Graph`_.
|
|
|
|
|
|
IN: ``vertex_descriptor s``
|
|
The start vertex must be the same in every process.
|
|
|
|
|
|
IN: ``visitor(BFSVisitor vis)``
|
|
The visitor must be a distributed BFS visitor. The suble differences
|
|
between sequential and distributed BFS visitors are discussed in the
|
|
section `Visitor Event Points`_.
|
|
|
|
UTIL/OUT: ``color_map(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). The default value is a distributed
|
|
``iterator_property_map`` created from a ``std::vector`` of
|
|
``default_color_type``.
|
|
|
|
|
|
UTIL: ``buffer(Buffer& Q)``
|
|
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
|
|
``empty()`` method must not return ``true`` until all local queues
|
|
are empty.
|
|
|
|
**Default:** A ``distributed_queue`` of a ``filtered_queue`` over a
|
|
standard ``boost::queue``. This queue filters out duplicate
|
|
vertices and distributes vertices appropriately.
|
|
|
|
Complexity
|
|
----------
|
|
This algorithm performs *O(V + E)* work in *d + 1* BSP supersteps,
|
|
where *d* is the diameter of the connected component being
|
|
searched. Over all supersteps, *O(E)* messages of constant size will
|
|
be transmitted.
|
|
|
|
Visitor Event Points
|
|
--------------------
|
|
The `BFS Visitor`_ concept defines 9 event points that will be
|
|
triggered by the `sequential breadth-first search`_. 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.
|
|
|
|
``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``. Due to incomplete information in distributed property maps,
|
|
this event may be triggered many times for the same vertex ``u``.
|
|
|
|
|
|
``examine_vertex(u, g)``
|
|
This will be invoked by the process owning the vertex ``u``. If the
|
|
distributed queue prevents duplicates, it will be invoked only
|
|
once for a particular vertex ``u``.
|
|
|
|
|
|
``examine_edge(e, g)``
|
|
This will be invoked by the process owning the source vertex of
|
|
``e``. If the distributed queue prevents duplicates, it will be
|
|
invoked only once for a particular edge ``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. Unlike the
|
|
sequential BFS, this event may be triggered even when the target has
|
|
already been discovered (but by a different process). Thus, some
|
|
``non_tree_edge`` events in a sequential BFS may become
|
|
``tree_edge`` in a distributed BFS.
|
|
|
|
|
|
``non_tree_edge(e, g)``
|
|
Some ``non_tree_edge`` events in a sequential BFS may become
|
|
``tree_edge`` events in a distributed BFS. See the description of
|
|
``tree_edge`` for additional details.
|
|
|
|
|
|
``gray_target(e, g)``
|
|
As with ``tree_edge`` not knowing when another process has already
|
|
discovered a vertex, ``gray_target`` events may occur in a
|
|
distributed BFS when ``black_target`` events may occur in a
|
|
sequential BFS, due to a lack of information on a given
|
|
processor. The source of edge ``e`` will be local to the process
|
|
executing this event.
|
|
|
|
|
|
``black_target(e, g)``
|
|
See documentation for ``gray_target``
|
|
|
|
|
|
``finish_vertex(e, g)``
|
|
See documentation for ``examine_vertex``.
|
|
|
|
Making Visitors Safe for Distributed BFS
|
|
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
|
|
The three most important things to remember when updating an existing
|
|
BFS visitor for distributed BFS or writing a new distributed BFS
|
|
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 BFS, e.g., requiring
|
|
``tree_edge`` and ``non_tree_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.
|
|
|
|
Distributed BFS Visitor Example
|
|
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
|
|
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::
|
|
|
|
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;
|
|
};
|
|
|
|
To revisit this code for distributed BFS, we consider the three points
|
|
in the section `Making Visitors Safe for Distributed BFS`_:
|
|
|
|
1. 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.
|
|
|
|
2. This visitor *does* require a precise sequence of events that may
|
|
change with a distributed BFS. The extraneous ``tree_edge`` 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.
|
|
|
|
3. 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 ``distance`` needs to
|
|
resolve distances to the smallest distance it has seen. For
|
|
instance, process 0 may find vertex ``u`` 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 *role* is as a distance map, which
|
|
introduces an appropriate reduction operation::
|
|
|
|
set_property_map_role(vertex_distance, distance);
|
|
|
|
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::
|
|
|
|
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;
|
|
};
|
|
|
|
|
|
Performance
|
|
-----------
|
|
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.
|
|
|
|
.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeSparse&columns=4
|
|
:align: left
|
|
.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeSparse&columns=4&speedup=1
|
|
|
|
.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeDense&columns=4
|
|
:align: left
|
|
.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeDense&columns=4&speedup=1
|
|
|
|
-----------------------------------------------------------------------------
|
|
|
|
Copyright (C) 2004 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/breadth_first_search.html
|
|
.. _sequential breadth-first search: http://www.boost.org/libs/graph/doc/breadth_first_search.html
|
|
.. _Distributed Graph: DistributedGraph.html
|
|
.. _Distributed Property Map: distributed_property_map.html
|
|
.. _BFS Visitor: http://www.boost.org/libs/graph/doc/BFSVisitor.html
|