1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
|
.. 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
|
