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 {
constraintsboost::BFSVisitorConcept37 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 >
breadth_first_visit(const IncidenceGraph & g,SourceIterator sources_begin,SourceIterator sources_end,Buffer & Q,BFSVisitor vis,ColorMap color)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 >
breadth_first_visit(const IncidenceGraph & g,typename graph_traits<IncidenceGraph>::vertex_descriptor s,Buffer & Q,BFSVisitor vis,ColorMap color)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 >
breadth_first_search(const VertexListGraph & g,SourceIterator sources_begin,SourceIterator sources_end,Buffer & Q,BFSVisitor vis,ColorMap color)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 >
breadth_first_search(const VertexListGraph & g,typename graph_traits<VertexListGraph>::vertex_descriptor s,Buffer & Q,BFSVisitor vis,ColorMap color)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:
bfs_visitor()160 bfs_visitor() {}
bfs_visitor(Visitors vis)161 bfs_visitor(Visitors vis) : m_vis(vis) {}
162
163 template < class Vertex, class Graph >
initialize_vertex(Vertex u,Graph & g)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 >
discover_vertex(Vertex u,Graph & g)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 >
examine_vertex(Vertex u,Graph & g)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 >
examine_edge(Edge e,Graph & g)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 >
tree_edge(Edge e,Graph & g)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 >
non_tree_edge(Edge e,Graph & g)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 >
gray_target(Edge e,Graph & g)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 >
black_target(Edge e,Graph & g)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 >
finish_vertex(Vertex u,Graph & g)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 >
make_bfs_visitor(Visitors vis)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 >
bfs_helper(VertexListGraph & g,typename graph_traits<VertexListGraph>::vertex_descriptor s,ColorMap color,BFSVisitor vis,const bgl_named_params<P,T,R> & params,boost::mpl::false_)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 >
applyboost::detail::bfs_dispatch285 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(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 >
applyboost::detail::bfs_dispatch303 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(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 >
breadth_first_search(const VertexListGraph & g,typename graph_traits<VertexListGraph>::vertex_descriptor s,const bgl_named_params<P,T,R> & params)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 >
breadth_first_visit(const IncidenceGraph & g,typename graph_traits<IncidenceGraph>::vertex_descriptor s,const bgl_named_params<P,T,R> & params)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(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 >
operator ()boost::graph::detail::breadth_first_search_impl379 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(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