2 //=======================================================================
3 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
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 //=======================================================================
11 #ifndef BOOST_GRAPH_BREADTH_FIRST_SEARCH_HPP
12 #define BOOST_GRAPH_BREADTH_FIRST_SEARCH_HPP
15 Breadth First Search Algorithm (Cormen, Leiserson, and Rivest p. 470)
17 #include <boost/config.hpp>
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>
30 #include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/concepts.hpp>)
35 template < class Visitor, class Graph > struct BFSVisitorConcept
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);
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);
52 typename graph_traits< Graph >::vertex_descriptor u;
53 typename graph_traits< Graph >::edge_descriptor e;
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)
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;
71 for (; sources_begin != sources_end; ++sources_begin)
73 Vertex s = *sources_begin;
74 put(color, s, Color::gray());
75 vis.discover_vertex(s, g);
82 vis.examine_vertex(u, g);
83 for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei)
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())
90 vis.tree_edge(*ei, g);
91 put(color, v, Color::gray());
92 vis.discover_vertex(v, g);
97 vis.non_tree_edge(*ei, g);
98 if (v_color == Color::gray())
99 vis.gray_target(*ei, g);
101 vis.black_target(*ei, g);
104 put(color, u, Color::black());
105 vis.finish_vertex(u, g);
107 } // breadth_first_visit
109 // Single-source version
110 template < class IncidenceGraph, class Buffer, class BFSVisitor,
112 void breadth_first_visit(const IncidenceGraph& g,
113 typename graph_traits< IncidenceGraph >::vertex_descriptor s, Buffer& Q,
114 BFSVisitor vis, ColorMap color)
116 typename graph_traits< IncidenceGraph >::vertex_descriptor sources[1]
118 breadth_first_visit(g, sources, sources + 1, Q, vis, color);
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)
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)
133 vis.initialize_vertex(*i, g);
134 put(color, *i, Color::white());
136 breadth_first_visit(g, sources_begin, sources_end, Q, vis, color);
139 template < class VertexListGraph, class Buffer, class BFSVisitor,
141 void breadth_first_search(const VertexListGraph& g,
142 typename graph_traits< VertexListGraph >::vertex_descriptor s, Buffer& Q,
143 BFSVisitor vis, ColorMap color)
145 typename graph_traits< VertexListGraph >::vertex_descriptor sources[1]
147 breadth_first_search(g, sources, sources + 1, Q, vis, color);
152 struct bfs_visitor_event_not_overridden
157 template < class Visitors = null_visitor > class bfs_visitor
161 bfs_visitor(Visitors vis) : m_vis(vis) {}
163 template < class Vertex, class Graph >
164 graph::bfs_visitor_event_not_overridden initialize_vertex(
167 invoke_visitors(m_vis, u, g, ::boost::on_initialize_vertex());
168 return graph::bfs_visitor_event_not_overridden();
171 template < class Vertex, class Graph >
172 graph::bfs_visitor_event_not_overridden discover_vertex(Vertex u, Graph& g)
174 invoke_visitors(m_vis, u, g, ::boost::on_discover_vertex());
175 return graph::bfs_visitor_event_not_overridden();
178 template < class Vertex, class Graph >
179 graph::bfs_visitor_event_not_overridden examine_vertex(Vertex u, Graph& g)
181 invoke_visitors(m_vis, u, g, ::boost::on_examine_vertex());
182 return graph::bfs_visitor_event_not_overridden();
185 template < class Edge, class Graph >
186 graph::bfs_visitor_event_not_overridden examine_edge(Edge e, Graph& g)
188 invoke_visitors(m_vis, e, g, ::boost::on_examine_edge());
189 return graph::bfs_visitor_event_not_overridden();
192 template < class Edge, class Graph >
193 graph::bfs_visitor_event_not_overridden tree_edge(Edge e, Graph& g)
195 invoke_visitors(m_vis, e, g, ::boost::on_tree_edge());
196 return graph::bfs_visitor_event_not_overridden();
199 template < class Edge, class Graph >
200 graph::bfs_visitor_event_not_overridden non_tree_edge(Edge e, Graph& g)
202 invoke_visitors(m_vis, e, g, ::boost::on_non_tree_edge());
203 return graph::bfs_visitor_event_not_overridden();
206 template < class Edge, class Graph >
207 graph::bfs_visitor_event_not_overridden gray_target(Edge e, Graph& g)
209 invoke_visitors(m_vis, e, g, ::boost::on_gray_target());
210 return graph::bfs_visitor_event_not_overridden();
213 template < class Edge, class Graph >
214 graph::bfs_visitor_event_not_overridden black_target(Edge e, Graph& g)
216 invoke_visitors(m_vis, e, g, ::boost::on_black_target());
217 return graph::bfs_visitor_event_not_overridden();
220 template < class Vertex, class Graph >
221 graph::bfs_visitor_event_not_overridden finish_vertex(Vertex u, Graph& g)
223 invoke_visitors(m_vis, u, g, ::boost::on_finish_vertex());
224 return graph::bfs_visitor_event_not_overridden();
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)
240 template < class Visitors >
241 bfs_visitor< Visitors > make_bfs_visitor(Visitors vis)
243 return bfs_visitor< Visitors >(vis);
245 typedef bfs_visitor<> default_bfs_visitor;
250 template < class VertexListGraph, class ColorMap, class BFSVisitor, class P,
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_)
257 typedef graph_traits< VertexListGraph > Traits;
259 typedef typename Traits::vertex_descriptor Vertex;
260 typedef boost::queue< Vertex > queue_t;
262 breadth_first_search(g, s,
263 choose_param(get_param(params, buffer_param_t()), boost::ref(Q))
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
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.
282 template < class ColorMap > struct bfs_dispatch
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)
289 bfs_helper(g, s, color,
290 choose_param(get_param(params, graph_visitor),
291 make_bfs_visitor(null_visitor())),
294 boost::is_base_and_derived< distributed_graph_tag,
295 typename graph_traits<
296 VertexListGraph >::traversal_category >::value >());
300 template <> struct bfs_dispatch< param_not_found >
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)
307 null_visitor null_vis;
310 make_two_bit_color_map(num_vertices(g),
312 get_param(params, vertex_index), g, vertex_index)),
313 choose_param(get_param(params, graph_visitor),
314 make_bfs_visitor(null_vis)),
317 boost::is_base_and_derived< distributed_graph_tag,
318 typename graph_traits<
319 VertexListGraph >::traversal_category >::value >());
323 } // namespace detail
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)
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
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));
344 // This version does not initialize colors, user has to.
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)
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
355 IncidenceGraph& ng = const_cast< IncidenceGraph& >(g);
357 typedef graph_traits< IncidenceGraph > Traits;
359 typedef typename Traits::vertex_descriptor vertex_descriptor;
360 typedef boost::queue< vertex_descriptor > queue_t;
363 breadth_first_visit(ng, s,
364 choose_param(get_param(params, buffer_param_t()), boost::ref(Q)).get(),
366 get_param(params, graph_visitor), make_bfs_visitor(null_visitor())),
367 choose_pmap(get_param(params, vertex_color), ng, vertex_color));
374 template < typename Graph, typename Source >
375 struct breadth_first_search_impl
377 typedef void result_type;
378 template < typename ArgPack >
380 const Graph& g, const Source& source, const ArgPack& arg_pack)
382 using namespace boost::graph::keywords;
383 typename boost::graph_traits< Graph >::vertex_descriptor
387 typename boost::graph_traits< Graph >::vertex_descriptor >
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));
396 BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(breadth_first_search, 2, 4)
400 // Named Parameter Variant
401 BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(breadth_first_search, 2)
406 #include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/breadth_first_search.hpp>)
408 #endif // BOOST_GRAPH_BREADTH_FIRST_SEARCH_HPP