123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219 |
- .. 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
|