1 | // |
2 | //======================================================================= |
3 | // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. |
4 | // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek |
5 | // |
6 | // Distributed under the Boost Software License, Version 1.0. (See |
7 | // accompanying file LICENSE_1_0.txt or copy at |
8 | // http://www.boost.org/LICENSE_1_0.txt) |
9 | //======================================================================= |
10 | // |
11 | #ifndef BOOST_GRAPH_BREADTH_FIRST_SEARCH_HPP |
12 | #define BOOST_GRAPH_BREADTH_FIRST_SEARCH_HPP |
13 | |
14 | /* |
15 | Breadth First Search Algorithm (Cormen, Leiserson, and Rivest p. 470) |
16 | */ |
17 | #include <boost/config.hpp> |
18 | #include <vector> |
19 | #include <boost/pending/queue.hpp> |
20 | #include <boost/graph/graph_traits.hpp> |
21 | #include <boost/graph/graph_concepts.hpp> |
22 | #include <boost/graph/visitors.hpp> |
23 | #include <boost/graph/named_function_params.hpp> |
24 | #include <boost/graph/overloading.hpp> |
25 | #include <boost/graph/graph_concepts.hpp> |
26 | #include <boost/graph/two_bit_color_map.hpp> |
27 | #include <boost/graph/detail/mpi_include.hpp> |
28 | #include <boost/concept/assert.hpp> |
29 | |
30 | #include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/concepts.hpp>) |
31 | |
32 | namespace boost |
33 | { |
34 | |
35 | template < class Visitor, class Graph > struct BFSVisitorConcept |
36 | { |
37 | void constraints() |
38 | { |
39 | BOOST_CONCEPT_ASSERT((CopyConstructibleConcept< Visitor >)); |
40 | vis.initialize_vertex(u, g); |
41 | vis.discover_vertex(u, g); |
42 | vis.examine_vertex(u, g); |
43 | vis.examine_edge(e, g); |
44 | vis.tree_edge(e, g); |
45 | vis.non_tree_edge(e, g); |
46 | vis.gray_target(e, g); |
47 | vis.black_target(e, g); |
48 | vis.finish_vertex(u, g); |
49 | } |
50 | Visitor vis; |
51 | Graph g; |
52 | typename graph_traits< Graph >::vertex_descriptor u; |
53 | typename graph_traits< Graph >::edge_descriptor e; |
54 | }; |
55 | |
56 | // Multiple-source version |
57 | template < class IncidenceGraph, class Buffer, class BFSVisitor, class ColorMap, |
58 | class SourceIterator > |
59 | void breadth_first_visit(const IncidenceGraph& g, SourceIterator sources_begin, |
60 | SourceIterator sources_end, Buffer& Q, BFSVisitor vis, ColorMap color) |
61 | { |
62 | BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< IncidenceGraph >)); |
63 | typedef graph_traits< IncidenceGraph > GTraits; |
64 | typedef typename GTraits::vertex_descriptor Vertex; |
65 | BOOST_CONCEPT_ASSERT((BFSVisitorConcept< BFSVisitor, IncidenceGraph >)); |
66 | BOOST_CONCEPT_ASSERT((ReadWritePropertyMapConcept< ColorMap, Vertex >)); |
67 | typedef typename property_traits< ColorMap >::value_type ColorValue; |
68 | typedef color_traits< ColorValue > Color; |
69 | typename GTraits::out_edge_iterator ei, ei_end; |
70 | |
71 | for (; sources_begin != sources_end; ++sources_begin) |
72 | { |
73 | Vertex s = *sources_begin; |
74 | put(color, s, Color::gray()); |
75 | vis.discover_vertex(s, g); |
76 | Q.push(s); |
77 | } |
78 | while (!Q.empty()) |
79 | { |
80 | Vertex u = Q.top(); |
81 | Q.pop(); |
82 | vis.examine_vertex(u, g); |
83 | for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) |
84 | { |
85 | Vertex v = target(*ei, g); |
86 | vis.examine_edge(*ei, g); |
87 | ColorValue v_color = get(color, v); |
88 | if (v_color == Color::white()) |
89 | { |
90 | vis.tree_edge(*ei, g); |
91 | put(color, v, Color::gray()); |
92 | vis.discover_vertex(v, g); |
93 | Q.push(v); |
94 | } |
95 | else |
96 | { |
97 | vis.non_tree_edge(*ei, g); |
98 | if (v_color == Color::gray()) |
99 | vis.gray_target(*ei, g); |
100 | else |
101 | vis.black_target(*ei, g); |
102 | } |
103 | } // end for |
104 | put(color, u, Color::black()); |
105 | vis.finish_vertex(u, g); |
106 | } // end while |
107 | } // breadth_first_visit |
108 | |
109 | // Single-source version |
110 | template < class IncidenceGraph, class Buffer, class BFSVisitor, |
111 | class ColorMap > |
112 | void breadth_first_visit(const IncidenceGraph& g, |
113 | typename graph_traits< IncidenceGraph >::vertex_descriptor s, Buffer& Q, |
114 | BFSVisitor vis, ColorMap color) |
115 | { |
116 | typename graph_traits< IncidenceGraph >::vertex_descriptor sources[1] |
117 | = { s }; |
118 | breadth_first_visit(g, sources, sources + 1, Q, vis, color); |
119 | } |
120 | |
121 | template < class VertexListGraph, class SourceIterator, class Buffer, |
122 | class BFSVisitor, class ColorMap > |
123 | void breadth_first_search(const VertexListGraph& g, |
124 | SourceIterator sources_begin, SourceIterator sources_end, Buffer& Q, |
125 | BFSVisitor vis, ColorMap color) |
126 | { |
127 | // Initialization |
128 | typedef typename property_traits< ColorMap >::value_type ColorValue; |
129 | typedef color_traits< ColorValue > Color; |
130 | typename boost::graph_traits< VertexListGraph >::vertex_iterator i, i_end; |
131 | for (boost::tie(i, i_end) = vertices(g); i != i_end; ++i) |
132 | { |
133 | vis.initialize_vertex(*i, g); |
134 | put(color, *i, Color::white()); |
135 | } |
136 | breadth_first_visit(g, sources_begin, sources_end, Q, vis, color); |
137 | } |
138 | |
139 | template < class VertexListGraph, class Buffer, class BFSVisitor, |
140 | class ColorMap > |
141 | void breadth_first_search(const VertexListGraph& g, |
142 | typename graph_traits< VertexListGraph >::vertex_descriptor s, Buffer& Q, |
143 | BFSVisitor vis, ColorMap color) |
144 | { |
145 | typename graph_traits< VertexListGraph >::vertex_descriptor sources[1] |
146 | = { s }; |
147 | breadth_first_search(g, sources, sources + 1, Q, vis, color); |
148 | } |
149 | |
150 | namespace graph |
151 | { |
152 | struct bfs_visitor_event_not_overridden |
153 | { |
154 | }; |
155 | } |
156 | |
157 | template < class Visitors = null_visitor > class bfs_visitor |
158 | { |
159 | public: |
160 | bfs_visitor() {} |
161 | bfs_visitor(Visitors vis) : m_vis(vis) {} |
162 | |
163 | template < class Vertex, class Graph > |
164 | graph::bfs_visitor_event_not_overridden initialize_vertex( |
165 | Vertex u, Graph& g) |
166 | { |
167 | invoke_visitors(m_vis, u, g, ::boost::on_initialize_vertex()); |
168 | return graph::bfs_visitor_event_not_overridden(); |
169 | } |
170 | |
171 | template < class Vertex, class Graph > |
172 | graph::bfs_visitor_event_not_overridden discover_vertex(Vertex u, Graph& g) |
173 | { |
174 | invoke_visitors(m_vis, u, g, ::boost::on_discover_vertex()); |
175 | return graph::bfs_visitor_event_not_overridden(); |
176 | } |
177 | |
178 | template < class Vertex, class Graph > |
179 | graph::bfs_visitor_event_not_overridden examine_vertex(Vertex u, Graph& g) |
180 | { |
181 | invoke_visitors(m_vis, u, g, ::boost::on_examine_vertex()); |
182 | return graph::bfs_visitor_event_not_overridden(); |
183 | } |
184 | |
185 | template < class Edge, class Graph > |
186 | graph::bfs_visitor_event_not_overridden examine_edge(Edge e, Graph& g) |
187 | { |
188 | invoke_visitors(m_vis, e, g, ::boost::on_examine_edge()); |
189 | return graph::bfs_visitor_event_not_overridden(); |
190 | } |
191 | |
192 | template < class Edge, class Graph > |
193 | graph::bfs_visitor_event_not_overridden tree_edge(Edge e, Graph& g) |
194 | { |
195 | invoke_visitors(m_vis, e, g, ::boost::on_tree_edge()); |
196 | return graph::bfs_visitor_event_not_overridden(); |
197 | } |
198 | |
199 | template < class Edge, class Graph > |
200 | graph::bfs_visitor_event_not_overridden non_tree_edge(Edge e, Graph& g) |
201 | { |
202 | invoke_visitors(m_vis, e, g, ::boost::on_non_tree_edge()); |
203 | return graph::bfs_visitor_event_not_overridden(); |
204 | } |
205 | |
206 | template < class Edge, class Graph > |
207 | graph::bfs_visitor_event_not_overridden gray_target(Edge e, Graph& g) |
208 | { |
209 | invoke_visitors(m_vis, e, g, ::boost::on_gray_target()); |
210 | return graph::bfs_visitor_event_not_overridden(); |
211 | } |
212 | |
213 | template < class Edge, class Graph > |
214 | graph::bfs_visitor_event_not_overridden black_target(Edge e, Graph& g) |
215 | { |
216 | invoke_visitors(m_vis, e, g, ::boost::on_black_target()); |
217 | return graph::bfs_visitor_event_not_overridden(); |
218 | } |
219 | |
220 | template < class Vertex, class Graph > |
221 | graph::bfs_visitor_event_not_overridden finish_vertex(Vertex u, Graph& g) |
222 | { |
223 | invoke_visitors(m_vis, u, g, ::boost::on_finish_vertex()); |
224 | return graph::bfs_visitor_event_not_overridden(); |
225 | } |
226 | |
227 | BOOST_GRAPH_EVENT_STUB(on_initialize_vertex, bfs) |
228 | BOOST_GRAPH_EVENT_STUB(on_discover_vertex, bfs) |
229 | BOOST_GRAPH_EVENT_STUB(on_examine_vertex, bfs) |
230 | BOOST_GRAPH_EVENT_STUB(on_examine_edge, bfs) |
231 | BOOST_GRAPH_EVENT_STUB(on_tree_edge, bfs) |
232 | BOOST_GRAPH_EVENT_STUB(on_non_tree_edge, bfs) |
233 | BOOST_GRAPH_EVENT_STUB(on_gray_target, bfs) |
234 | BOOST_GRAPH_EVENT_STUB(on_black_target, bfs) |
235 | BOOST_GRAPH_EVENT_STUB(on_finish_vertex, bfs) |
236 | |
237 | protected: |
238 | Visitors m_vis; |
239 | }; |
240 | template < class Visitors > |
241 | bfs_visitor< Visitors > make_bfs_visitor(Visitors vis) |
242 | { |
243 | return bfs_visitor< Visitors >(vis); |
244 | } |
245 | typedef bfs_visitor<> default_bfs_visitor; |
246 | |
247 | namespace detail |
248 | { |
249 | |
250 | template < class VertexListGraph, class ColorMap, class BFSVisitor, class P, |
251 | class T, class R > |
252 | void bfs_helper(VertexListGraph& g, |
253 | typename graph_traits< VertexListGraph >::vertex_descriptor s, |
254 | ColorMap color, BFSVisitor vis, |
255 | const bgl_named_params< P, T, R >& params, boost::mpl::false_) |
256 | { |
257 | typedef graph_traits< VertexListGraph > Traits; |
258 | // Buffer default |
259 | typedef typename Traits::vertex_descriptor Vertex; |
260 | typedef boost::queue< Vertex > queue_t; |
261 | queue_t Q; |
262 | breadth_first_search(g, s, |
263 | choose_param(get_param(params, buffer_param_t()), boost::ref(Q)) |
264 | .get(), |
265 | vis, color); |
266 | } |
267 | |
268 | #ifdef BOOST_GRAPH_USE_MPI |
269 | template < class DistributedGraph, class ColorMap, class BFSVisitor, |
270 | class P, class T, class R > |
271 | void bfs_helper(DistributedGraph& g, |
272 | typename graph_traits< DistributedGraph >::vertex_descriptor s, |
273 | ColorMap color, BFSVisitor vis, |
274 | const bgl_named_params< P, T, R >& params, boost::mpl::true_); |
275 | #endif // BOOST_GRAPH_USE_MPI |
276 | |
277 | //------------------------------------------------------------------------- |
278 | // Choose between default color and color parameters. Using |
279 | // function dispatching so that we don't require vertex index if |
280 | // the color default is not being used. |
281 | |
282 | template < class ColorMap > struct bfs_dispatch |
283 | { |
284 | template < class VertexListGraph, class P, class T, class R > |
285 | static void apply(VertexListGraph& g, |
286 | typename graph_traits< VertexListGraph >::vertex_descriptor s, |
287 | const bgl_named_params< P, T, R >& params, ColorMap color) |
288 | { |
289 | bfs_helper(g, s, color, |
290 | choose_param(get_param(params, graph_visitor), |
291 | make_bfs_visitor(vis: null_visitor())), |
292 | params, |
293 | boost::mpl::bool_< |
294 | boost::is_base_and_derived< distributed_graph_tag, |
295 | typename graph_traits< |
296 | VertexListGraph >::traversal_category >::value >()); |
297 | } |
298 | }; |
299 | |
300 | template <> struct bfs_dispatch< param_not_found > |
301 | { |
302 | template < class VertexListGraph, class P, class T, class R > |
303 | static void apply(VertexListGraph& g, |
304 | typename graph_traits< VertexListGraph >::vertex_descriptor s, |
305 | const bgl_named_params< P, T, R >& params, param_not_found) |
306 | { |
307 | null_visitor null_vis; |
308 | |
309 | bfs_helper(g, s, |
310 | make_two_bit_color_map(num_vertices(g), |
311 | choose_const_pmap( |
312 | get_param(params, vertex_index), g, vertex_index)), |
313 | choose_param(get_param(params, graph_visitor), |
314 | make_bfs_visitor(vis: null_vis)), |
315 | params, |
316 | boost::mpl::bool_< |
317 | boost::is_base_and_derived< distributed_graph_tag, |
318 | typename graph_traits< |
319 | VertexListGraph >::traversal_category >::value >()); |
320 | } |
321 | }; |
322 | |
323 | } // namespace detail |
324 | |
325 | #if 1 |
326 | // Named Parameter Variant |
327 | template < class VertexListGraph, class P, class T, class R > |
328 | void breadth_first_search(const VertexListGraph& g, |
329 | typename graph_traits< VertexListGraph >::vertex_descriptor s, |
330 | const bgl_named_params< P, T, R >& params) |
331 | { |
332 | // The graph is passed by *const* reference so that graph adaptors |
333 | // (temporaries) can be passed into this function. However, the |
334 | // graph is not really const since we may write to property maps |
335 | // of the graph. |
336 | VertexListGraph& ng = const_cast< VertexListGraph& >(g); |
337 | typedef typename get_param_type< vertex_color_t, |
338 | bgl_named_params< P, T, R > >::type C; |
339 | detail::bfs_dispatch< C >::apply( |
340 | ng, s, params, get_param(params, vertex_color)); |
341 | } |
342 | #endif |
343 | |
344 | // This version does not initialize colors, user has to. |
345 | |
346 | template < class IncidenceGraph, class P, class T, class R > |
347 | void breadth_first_visit(const IncidenceGraph& g, |
348 | typename graph_traits< IncidenceGraph >::vertex_descriptor s, |
349 | const bgl_named_params< P, T, R >& params) |
350 | { |
351 | // The graph is passed by *const* reference so that graph adaptors |
352 | // (temporaries) can be passed into this function. However, the |
353 | // graph is not really const since we may write to property maps |
354 | // of the graph. |
355 | IncidenceGraph& ng = const_cast< IncidenceGraph& >(g); |
356 | |
357 | typedef graph_traits< IncidenceGraph > Traits; |
358 | // Buffer default |
359 | typedef typename Traits::vertex_descriptor vertex_descriptor; |
360 | typedef boost::queue< vertex_descriptor > queue_t; |
361 | queue_t Q; |
362 | |
363 | breadth_first_visit(ng, s, |
364 | choose_param(get_param(params, buffer_param_t()), boost::ref(Q)).get(), |
365 | choose_param( |
366 | get_param(params, graph_visitor), make_bfs_visitor(vis: null_visitor())), |
367 | choose_pmap(get_param(params, vertex_color), ng, vertex_color)); |
368 | } |
369 | |
370 | namespace graph |
371 | { |
372 | namespace detail |
373 | { |
374 | template < typename Graph, typename Source > |
375 | struct breadth_first_search_impl |
376 | { |
377 | typedef void result_type; |
378 | template < typename ArgPack > |
379 | void operator()( |
380 | const Graph& g, const Source& source, const ArgPack& arg_pack) |
381 | { |
382 | using namespace boost::graph::keywords; |
383 | typename boost::graph_traits< Graph >::vertex_descriptor |
384 | sources[1] |
385 | = { source }; |
386 | boost::queue< |
387 | typename boost::graph_traits< Graph >::vertex_descriptor > |
388 | Q; |
389 | boost::breadth_first_search(g, &sources[0], &sources[1], |
390 | boost::unwrap_ref(arg_pack[_buffer | boost::ref(Q)]), |
391 | arg_pack[_visitor | make_bfs_visitor(vis: null_visitor())], |
392 | boost::detail::make_color_map_from_arg_pack(g, arg_pack)); |
393 | } |
394 | }; |
395 | } |
396 | BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(breadth_first_search, 2, 4) |
397 | } |
398 | |
399 | #if 0 |
400 | // Named Parameter Variant |
401 | BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(breadth_first_search, 2) |
402 | #endif |
403 | |
404 | } // namespace boost |
405 | |
406 | #include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/breadth_first_search.hpp>) |
407 | |
408 | #endif // BOOST_GRAPH_BREADTH_FIRST_SEARCH_HPP |
409 | |