]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Copyright (C) 2004-2008 The Trustees of Indiana University. |
2 | ||
3 | // Use, modification and distribution is subject to the Boost Software | |
4 | // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
5 | // http://www.boost.org/LICENSE_1_0.txt) | |
6 | ||
7 | // Authors: Douglas Gregor | |
8 | // Andrew Lumsdaine | |
9 | #ifndef BOOST_GRAPH_DISTRIBUTED_DFS_HPP | |
10 | #define BOOST_GRAPH_DISTRIBUTED_DFS_HPP | |
11 | ||
12 | #ifndef BOOST_GRAPH_USE_MPI | |
13 | #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included" | |
14 | #endif | |
15 | ||
16 | #include <boost/graph/graph_traits.hpp> | |
17 | #include <boost/property_map/property_map.hpp> | |
18 | #include <boost/graph/overloading.hpp> | |
19 | #include <boost/graph/properties.hpp> | |
20 | #include <boost/graph/distributed/concepts.hpp> | |
21 | #include <boost/static_assert.hpp> | |
22 | #include <boost/assert.hpp> | |
23 | #include <boost/graph/parallel/process_group.hpp> | |
24 | #include <boost/graph/parallel/container_traits.hpp> | |
25 | ||
26 | namespace boost { | |
27 | namespace graph { namespace distributed { namespace detail { | |
28 | template<typename DistributedGraph, typename ColorMap, typename ParentMap, | |
29 | typename ExploreMap, typename VertexIndexMap, typename DFSVisitor> | |
30 | class parallel_dfs | |
31 | { | |
32 | typedef typename graph_traits<DistributedGraph>::vertex_iterator | |
33 | vertex_iterator; | |
34 | typedef typename graph_traits<DistributedGraph>::vertex_descriptor | |
35 | vertex_descriptor; | |
36 | typedef typename graph_traits<DistributedGraph>::out_edge_iterator | |
37 | out_edge_iterator; | |
38 | ||
39 | typedef typename boost::graph::parallel::process_group_type<DistributedGraph> | |
40 | ::type process_group_type; | |
41 | typedef typename process_group_type::process_id_type process_id_type; | |
42 | ||
43 | /** | |
44 | * The first vertex in the pair is the local node (i) and the | |
45 | * second vertex in the pair is the (possibly remote) node (j). | |
46 | */ | |
47 | typedef boost::parallel::detail::untracked_pair<vertex_descriptor, vertex_descriptor> vertex_pair; | |
48 | ||
49 | typedef typename property_traits<ColorMap>::value_type color_type; | |
50 | typedef color_traits<color_type> Color; | |
51 | ||
52 | // Message types | |
53 | enum { discover_msg = 10, return_msg = 50, visited_msg = 100 , done_msg = 150}; | |
54 | ||
55 | ||
56 | public: | |
57 | parallel_dfs(const DistributedGraph& g, ColorMap color, | |
58 | ParentMap parent, ExploreMap explore, | |
59 | VertexIndexMap index_map, DFSVisitor vis) | |
60 | : g(g), color(color), parent(parent), explore(explore), | |
61 | index_map(index_map), vis(vis), pg(process_group(g)), | |
62 | owner(get(vertex_owner, g)), next_out_edge(num_vertices(g)) | |
63 | { } | |
64 | ||
65 | void run(vertex_descriptor s) | |
66 | { | |
67 | vertex_iterator vi, vi_end; | |
68 | for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) { | |
69 | put(color, *vi, Color::white()); | |
70 | put(parent, *vi, *vi); | |
71 | put(explore, *vi, *vi); | |
72 | next_out_edge[get(index_map, *vi)] = out_edges(*vi, g).first; | |
73 | vis.initialize_vertex(*vi, g); | |
74 | } | |
75 | ||
76 | vis.start_vertex(s, g); | |
77 | ||
78 | if (get(owner, s) == process_id(pg)) { | |
79 | send_oob(pg, get(owner, s), discover_msg, vertex_pair(s, s)); | |
80 | } | |
81 | ||
82 | bool done = false; | |
83 | while (!done) { | |
84 | std::pair<process_id_type, int> msg = *pg.poll(true); | |
85 | ||
86 | switch (msg.second) { | |
87 | case discover_msg: | |
88 | { | |
89 | vertex_pair p; | |
90 | receive_oob(pg, msg.first, msg.second, p); | |
91 | ||
92 | if (p.first != p.second) { | |
93 | // delete j from nomessage(j) | |
94 | if (get(color, p.second) != Color::black()) | |
95 | local_put(color, p.second, Color::gray()); | |
96 | ||
97 | if (recover(p)) break; | |
98 | } | |
99 | ||
100 | if (get(color, p.first) == Color::white()) { | |
101 | put(color, p.first, Color::gray()); | |
102 | put(parent, p.first, p.second); | |
103 | ||
104 | vis.discover_vertex(p.first, g); | |
105 | ||
106 | if (shift_center_of_activity(p.first)) break; | |
107 | ||
108 | out_edge_iterator ei, ei_end; | |
109 | for (boost::tie(ei,ei_end) = out_edges(p.first, g); ei != ei_end; ++ei) | |
110 | { | |
111 | // Notify everyone who may not know that the source | |
112 | // vertex has been visited. They can then mark the | |
113 | // corresponding color map entry gray. | |
114 | if (get(parent, p.first) != target(*ei, g) | |
115 | && get(explore, p.first) != target(*ei, g)) { | |
116 | vertex_pair visit(target(*ei, g), p.first); | |
117 | ||
118 | send_oob(pg, get(owner, target(*ei, g)), visited_msg, visit); | |
119 | } | |
120 | } | |
121 | } | |
122 | } | |
123 | break; | |
124 | ||
125 | case visited_msg: | |
126 | { | |
127 | vertex_pair p; | |
128 | receive_oob(pg, msg.first, msg.second, p); | |
129 | ||
130 | // delete j from nomessage(j) | |
131 | if (get(color, p.second) != Color::black()) | |
132 | local_put(color, p.second, Color::gray()); | |
133 | ||
134 | recover(p); | |
135 | } | |
136 | break; | |
137 | ||
138 | case return_msg: | |
139 | { | |
140 | vertex_pair p; | |
141 | receive_oob(pg, msg.first, msg.second, p); | |
142 | ||
143 | // delete j from nomessage(i) | |
144 | local_put(color, p.second, Color::black()); | |
145 | ||
146 | shift_center_of_activity(p.first); | |
147 | } | |
148 | break; | |
149 | ||
150 | case done_msg: | |
151 | { | |
152 | receive_oob(pg, msg.first, msg.second, done); | |
153 | ||
154 | // Propagate done message downward in tree | |
155 | done = true; | |
156 | process_id_type id = process_id(pg); | |
157 | process_id_type left = 2*id + 1; | |
158 | process_id_type right = left + 1; | |
159 | if (left < num_processes(pg)) | |
160 | send_oob(pg, left, done_msg, done); | |
161 | if (right < num_processes(pg)) | |
162 | send_oob(pg, right, done_msg, done); | |
163 | } | |
164 | break; | |
165 | ||
166 | default: | |
167 | BOOST_ASSERT(false); | |
168 | } | |
169 | } | |
170 | } | |
171 | ||
172 | private: | |
173 | bool recover(const vertex_pair& p) | |
174 | { | |
175 | if (get(explore, p.first) == p.second) { | |
176 | return shift_center_of_activity(p.first); | |
177 | } | |
178 | else | |
179 | return false; | |
180 | } | |
181 | ||
182 | bool shift_center_of_activity(vertex_descriptor i) | |
183 | { | |
184 | for (out_edge_iterator ei = next_out_edge[get(index_map, i)], | |
185 | ei_end = out_edges(i, g).second; | |
186 | ei != ei_end; ++ei) { | |
187 | vis.examine_edge(*ei, g); | |
188 | ||
189 | vertex_descriptor k = target(*ei, g); | |
190 | color_type target_color = get(color, k); | |
191 | if (target_color == Color::black()) vis.forward_or_cross_edge(*ei, g); | |
192 | else if (target_color == Color::gray()) vis.back_edge(*ei, g); | |
193 | else { | |
194 | put(explore, i, k); | |
195 | vis.tree_edge(*ei, g); | |
196 | vertex_pair p(k, i); | |
197 | send_oob(pg, get(owner, k), discover_msg, p); | |
198 | next_out_edge[get(index_map, i)] = ++ei; | |
199 | return false; | |
200 | } | |
201 | } | |
202 | ||
203 | next_out_edge[get(index_map, i)] = out_edges(i, g).second; | |
204 | put(explore, i, i); | |
205 | put(color, i, Color::black()); | |
206 | vis.finish_vertex(i, g); | |
207 | ||
208 | if (get(parent, i) == i) { | |
209 | send_oob(pg, 0, done_msg, true); | |
210 | return true; | |
211 | } | |
212 | else { | |
213 | vertex_pair ret(get(parent, i), i); | |
214 | send_oob(pg, get(owner, ret.first), return_msg, ret); | |
215 | } | |
216 | return false; | |
217 | } | |
218 | ||
219 | const DistributedGraph& g; | |
220 | ColorMap color; | |
221 | ParentMap parent; | |
222 | ExploreMap explore; | |
223 | VertexIndexMap index_map; | |
224 | DFSVisitor vis; | |
225 | process_group_type pg; | |
226 | typename property_map<DistributedGraph, vertex_owner_t>::const_type owner; | |
227 | std::vector<out_edge_iterator> next_out_edge; | |
228 | }; | |
229 | } // end namespace detail | |
230 | ||
231 | template<typename DistributedGraph, typename ColorMap, typename ParentMap, | |
232 | typename ExploreMap, typename VertexIndexMap, typename DFSVisitor> | |
233 | void | |
234 | tsin_depth_first_visit | |
235 | (const DistributedGraph& g, | |
236 | typename graph_traits<DistributedGraph>::vertex_descriptor s, | |
237 | DFSVisitor vis, ColorMap color, ParentMap parent, ExploreMap explore, | |
238 | VertexIndexMap index_map) | |
239 | { | |
240 | typedef typename graph_traits<DistributedGraph>::directed_category | |
241 | directed_category; | |
242 | BOOST_STATIC_ASSERT( | |
243 | (is_convertible<directed_category, undirected_tag>::value)); | |
244 | ||
245 | set_property_map_role(vertex_color, color); | |
246 | graph::distributed::detail::parallel_dfs | |
247 | <DistributedGraph, ColorMap, ParentMap, ExploreMap, VertexIndexMap, | |
248 | DFSVisitor> do_dfs(g, color, parent, explore, index_map, vis); | |
249 | do_dfs.run(s); | |
250 | ||
251 | using boost::graph::parallel::process_group; | |
252 | synchronize(process_group(g)); | |
253 | } | |
254 | ||
255 | template<typename DistributedGraph, typename DFSVisitor, | |
256 | typename VertexIndexMap> | |
257 | void | |
258 | tsin_depth_first_visit | |
259 | (const DistributedGraph& g, | |
260 | typename graph_traits<DistributedGraph>::vertex_descriptor s, | |
261 | DFSVisitor vis, | |
262 | VertexIndexMap index_map) | |
263 | { | |
264 | typedef typename graph_traits<DistributedGraph>::vertex_descriptor | |
265 | vertex_descriptor; | |
266 | ||
267 | std::vector<default_color_type> colors(num_vertices(g)); | |
268 | std::vector<vertex_descriptor> parent(num_vertices(g)); | |
269 | std::vector<vertex_descriptor> explore(num_vertices(g)); | |
270 | tsin_depth_first_visit | |
271 | (g, s, | |
272 | vis, | |
273 | make_iterator_property_map(colors.begin(), index_map), | |
274 | make_iterator_property_map(parent.begin(), index_map), | |
275 | make_iterator_property_map(explore.begin(), index_map), | |
276 | index_map); | |
277 | } | |
278 | ||
279 | template<typename DistributedGraph, typename DFSVisitor, | |
280 | typename VertexIndexMap> | |
281 | void | |
282 | tsin_depth_first_visit | |
283 | (const DistributedGraph& g, | |
284 | typename graph_traits<DistributedGraph>::vertex_descriptor s, | |
285 | DFSVisitor vis) | |
286 | { | |
287 | tsin_depth_first_visit(g, s, vis, get(vertex_index, g)); | |
288 | } | |
289 | } // end namespace distributed | |
290 | ||
291 | using distributed::tsin_depth_first_visit; | |
292 | ||
293 | } // end namespace graph | |
294 | ||
295 | template<typename DistributedGraph, typename DFSVisitor> | |
296 | void | |
297 | depth_first_visit | |
298 | (const DistributedGraph& g, | |
299 | typename graph_traits<DistributedGraph>::vertex_descriptor s, | |
300 | DFSVisitor vis) | |
301 | { | |
302 | graph::tsin_depth_first_visit(g, s, vis, get(vertex_index, g)); | |
303 | } | |
304 | ||
305 | } // end namespace boost | |
306 | ||
307 | #endif // BOOST_GRAPH_DISTRIBUTED_DFS_HPP |