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:
parallel_dfs(const DistributedGraph & g,ColorMap color,ParentMap parent,ExploreMap explore,VertexIndexMap index_map,DFSVisitor vis)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
run(vertex_descriptor s)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:
recover(const vertex_pair & p)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
shift_center_of_activity(vertex_descriptor i)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
tsin_depth_first_visit(const DistributedGraph & g,typename graph_traits<DistributedGraph>::vertex_descriptor s,DFSVisitor vis,ColorMap color,ParentMap parent,ExploreMap explore,VertexIndexMap index_map)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
tsin_depth_first_visit(const DistributedGraph & g,typename graph_traits<DistributedGraph>::vertex_descriptor s,DFSVisitor vis,VertexIndexMap index_map)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
tsin_depth_first_visit(const DistributedGraph & g,typename graph_traits<DistributedGraph>::vertex_descriptor s,DFSVisitor vis)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
depth_first_visit(const DistributedGraph & g,typename graph_traits<DistributedGraph>::vertex_descriptor s,DFSVisitor vis)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
308