220 lines
8.4 KiB
ReStructuredText
220 lines
8.4 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| Depth-First Visit
|
|
========================
|
|
|
|
::
|
|
|
|
template<typename DistributedGraph, typename DFSVisitor>
|
|
void
|
|
depth_first_visit(const DistributedGraph& g,
|
|
typename graph_traits<DistributedGraph>::vertex_descriptor s,
|
|
DFSVisitor vis);
|
|
|
|
namespace graph {
|
|
template<typename DistributedGraph, typename DFSVisitor,
|
|
typename VertexIndexMap>
|
|
void
|
|
tsin_depth_first_visit(const DistributedGraph& g,
|
|
typename graph_traits<DistributedGraph>::vertex_descriptor s,
|
|
DFSVisitor vis);
|
|
|
|
template<typename DistributedGraph, typename DFSVisitor,
|
|
typename VertexIndexMap>
|
|
void
|
|
tsin_depth_first_visit(const DistributedGraph& g,
|
|
typename graph_traits<DistributedGraph>::vertex_descriptor s,
|
|
DFSVisitor vis, VertexIndexMap index_map);
|
|
|
|
template<typename DistributedGraph, typename ColorMap, typename ParentMap,
|
|
typename ExploreMap, typename NextOutEdgeMap, typename DFSVisitor>
|
|
void
|
|
tsin_depth_first_visit(const DistributedGraph& g,
|
|
typename graph_traits<DistributedGraph>::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
|