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/concept/assert.hpp>
29 #ifdef BOOST_GRAPH_USE_MPI
30 #include <boost/graph/distributed/concepts.hpp>
31 #endif // BOOST_GRAPH_USE_MPI
35 template <class Visitor, class Graph>
36 struct BFSVisitorConcept {
38 BOOST_CONCEPT_ASSERT(( CopyConstructibleConcept<Visitor> ));
39 vis.initialize_vertex(u, g);
40 vis.discover_vertex(u, g);
41 vis.examine_vertex(u, g);
42 vis.examine_edge(e, g);
44 vis.non_tree_edge(e, g);
45 vis.gray_target(e, g);
46 vis.black_target(e, g);
47 vis.finish_vertex(u, g);
51 typename graph_traits<Graph>::vertex_descriptor u;
52 typename graph_traits<Graph>::edge_descriptor e;
56 // Multiple-source version
57 template <class IncidenceGraph, class Buffer, class BFSVisitor,
58 class ColorMap, class SourceIterator>
59 void breadth_first_visit
60 (const IncidenceGraph& g,
61 SourceIterator sources_begin, SourceIterator sources_end,
62 Buffer& Q, BFSVisitor vis, ColorMap color)
64 BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<IncidenceGraph> ));
65 typedef graph_traits<IncidenceGraph> GTraits;
66 typedef typename GTraits::vertex_descriptor Vertex;
67 BOOST_CONCEPT_ASSERT(( BFSVisitorConcept<BFSVisitor, IncidenceGraph> ));
68 BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<ColorMap, Vertex> ));
69 typedef typename property_traits<ColorMap>::value_type ColorValue;
70 typedef color_traits<ColorValue> Color;
71 typename GTraits::out_edge_iterator ei, ei_end;
73 for (; sources_begin != sources_end; ++sources_begin) {
74 Vertex s = *sources_begin;
75 put(color, s, Color::gray()); vis.discover_vertex(s, g);
79 Vertex u = Q.top(); Q.pop(); vis.examine_vertex(u, g);
80 for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {
81 Vertex v = target(*ei, g); vis.examine_edge(*ei, g);
82 ColorValue v_color = get(color, v);
83 if (v_color == Color::white()) { vis.tree_edge(*ei, g);
84 put(color, v, Color::gray()); vis.discover_vertex(v, g);
86 } else { vis.non_tree_edge(*ei, g);
87 if (v_color == Color::gray()) vis.gray_target(*ei, g);
88 else vis.black_target(*ei, g);
91 put(color, u, Color::black()); vis.finish_vertex(u, g);
93 } // breadth_first_visit
95 // Single-source version
96 template <class IncidenceGraph, class Buffer, class BFSVisitor,
98 void breadth_first_visit
99 (const IncidenceGraph& g,
100 typename graph_traits<IncidenceGraph>::vertex_descriptor s,
101 Buffer& Q, BFSVisitor vis, ColorMap color)
103 typename graph_traits<IncidenceGraph>::vertex_descriptor sources[1] = {s};
104 breadth_first_visit(g, sources, sources + 1, Q, vis, color);
108 template <class VertexListGraph, class SourceIterator,
109 class Buffer, class BFSVisitor,
111 void breadth_first_search
112 (const VertexListGraph& g,
113 SourceIterator sources_begin, SourceIterator sources_end,
114 Buffer& Q, BFSVisitor vis, ColorMap color)
117 typedef typename property_traits<ColorMap>::value_type ColorValue;
118 typedef color_traits<ColorValue> Color;
119 typename boost::graph_traits<VertexListGraph>::vertex_iterator i, i_end;
120 for (boost::tie(i, i_end) = vertices(g); i != i_end; ++i) {
121 vis.initialize_vertex(*i, g);
122 put(color, *i, Color::white());
124 breadth_first_visit(g, sources_begin, sources_end, Q, vis, color);
127 template <class VertexListGraph, class Buffer, class BFSVisitor,
129 void breadth_first_search
130 (const VertexListGraph& g,
131 typename graph_traits<VertexListGraph>::vertex_descriptor s,
132 Buffer& Q, BFSVisitor vis, ColorMap color)
134 typename graph_traits<VertexListGraph>::vertex_descriptor sources[1] = {s};
135 breadth_first_search(g, sources, sources + 1, Q, vis, color);
138 namespace graph { struct bfs_visitor_event_not_overridden {}; }
141 template <class Visitors = null_visitor>
145 bfs_visitor(Visitors vis) : m_vis(vis) { }
147 template <class Vertex, class Graph>
148 graph::bfs_visitor_event_not_overridden
149 initialize_vertex(Vertex u, Graph& g)
151 invoke_visitors(m_vis, u, g, ::boost::on_initialize_vertex());
152 return graph::bfs_visitor_event_not_overridden();
155 template <class Vertex, class Graph>
156 graph::bfs_visitor_event_not_overridden
157 discover_vertex(Vertex u, Graph& g)
159 invoke_visitors(m_vis, u, g, ::boost::on_discover_vertex());
160 return graph::bfs_visitor_event_not_overridden();
163 template <class Vertex, class Graph>
164 graph::bfs_visitor_event_not_overridden
165 examine_vertex(Vertex u, Graph& g)
167 invoke_visitors(m_vis, u, g, ::boost::on_examine_vertex());
168 return graph::bfs_visitor_event_not_overridden();
171 template <class Edge, class Graph>
172 graph::bfs_visitor_event_not_overridden
173 examine_edge(Edge e, Graph& g)
175 invoke_visitors(m_vis, e, g, ::boost::on_examine_edge());
176 return graph::bfs_visitor_event_not_overridden();
179 template <class Edge, class Graph>
180 graph::bfs_visitor_event_not_overridden
181 tree_edge(Edge e, Graph& g)
183 invoke_visitors(m_vis, e, g, ::boost::on_tree_edge());
184 return graph::bfs_visitor_event_not_overridden();
187 template <class Edge, class Graph>
188 graph::bfs_visitor_event_not_overridden
189 non_tree_edge(Edge e, Graph& g)
191 invoke_visitors(m_vis, e, g, ::boost::on_non_tree_edge());
192 return graph::bfs_visitor_event_not_overridden();
195 template <class Edge, class Graph>
196 graph::bfs_visitor_event_not_overridden
197 gray_target(Edge e, Graph& g)
199 invoke_visitors(m_vis, e, g, ::boost::on_gray_target());
200 return graph::bfs_visitor_event_not_overridden();
203 template <class Edge, class Graph>
204 graph::bfs_visitor_event_not_overridden
205 black_target(Edge e, Graph& g)
207 invoke_visitors(m_vis, e, g, ::boost::on_black_target());
208 return graph::bfs_visitor_event_not_overridden();
211 template <class Vertex, class Graph>
212 graph::bfs_visitor_event_not_overridden
213 finish_vertex(Vertex u, Graph& g)
215 invoke_visitors(m_vis, u, g, ::boost::on_finish_vertex());
216 return graph::bfs_visitor_event_not_overridden();
219 BOOST_GRAPH_EVENT_STUB(on_initialize_vertex,bfs)
220 BOOST_GRAPH_EVENT_STUB(on_discover_vertex,bfs)
221 BOOST_GRAPH_EVENT_STUB(on_examine_vertex,bfs)
222 BOOST_GRAPH_EVENT_STUB(on_examine_edge,bfs)
223 BOOST_GRAPH_EVENT_STUB(on_tree_edge,bfs)
224 BOOST_GRAPH_EVENT_STUB(on_non_tree_edge,bfs)
225 BOOST_GRAPH_EVENT_STUB(on_gray_target,bfs)
226 BOOST_GRAPH_EVENT_STUB(on_black_target,bfs)
227 BOOST_GRAPH_EVENT_STUB(on_finish_vertex,bfs)
232 template <class Visitors>
233 bfs_visitor<Visitors>
234 make_bfs_visitor(Visitors vis) {
235 return bfs_visitor<Visitors>(vis);
237 typedef bfs_visitor<> default_bfs_visitor;
242 template <class VertexListGraph, class ColorMap, class BFSVisitor,
243 class P, class T, class R>
246 typename graph_traits<VertexListGraph>::vertex_descriptor s,
249 const bgl_named_params<P, T, R>& params,
252 typedef graph_traits<VertexListGraph> Traits;
254 typedef typename Traits::vertex_descriptor Vertex;
255 typedef boost::queue<Vertex> queue_t;
259 choose_param(get_param(params, buffer_param_t()), boost::ref(Q)).get(),
263 #ifdef BOOST_GRAPH_USE_MPI
264 template <class DistributedGraph, class ColorMap, class BFSVisitor,
265 class P, class T, class R>
267 (DistributedGraph& g,
268 typename graph_traits<DistributedGraph>::vertex_descriptor s,
271 const bgl_named_params<P, T, R>& params,
273 #endif // BOOST_GRAPH_USE_MPI
275 //-------------------------------------------------------------------------
276 // Choose between default color and color parameters. Using
277 // function dispatching so that we don't require vertex index if
278 // the color default is not being used.
280 template <class ColorMap>
281 struct bfs_dispatch {
282 template <class VertexListGraph, class P, class T, class R>
285 typename graph_traits<VertexListGraph>::vertex_descriptor s,
286 const bgl_named_params<P, T, R>& params,
291 choose_param(get_param(params, graph_visitor),
292 make_bfs_visitor(null_visitor())),
295 boost::is_base_and_derived<
296 distributed_graph_tag,
297 typename graph_traits<VertexListGraph>::traversal_category>::value>());
302 struct bfs_dispatch<param_not_found> {
303 template <class VertexListGraph, class P, class T, class R>
306 typename graph_traits<VertexListGraph>::vertex_descriptor s,
307 const bgl_named_params<P, T, R>& params,
310 null_visitor null_vis;
314 make_two_bit_color_map
316 choose_const_pmap(get_param(params, vertex_index),
318 choose_param(get_param(params, graph_visitor),
319 make_bfs_visitor(null_vis)),
322 boost::is_base_and_derived<
323 distributed_graph_tag,
324 typename graph_traits<VertexListGraph>::traversal_category>::value>());
328 } // namespace detail
331 // Named Parameter Variant
332 template <class VertexListGraph, class P, class T, class R>
333 void breadth_first_search
334 (const VertexListGraph& g,
335 typename graph_traits<VertexListGraph>::vertex_descriptor s,
336 const bgl_named_params<P, T, R>& params)
338 // The graph is passed by *const* reference so that graph adaptors
339 // (temporaries) can be passed into this function. However, the
340 // graph is not really const since we may write to property maps
342 VertexListGraph& ng = const_cast<VertexListGraph&>(g);
343 typedef typename get_param_type< vertex_color_t, bgl_named_params<P,T,R> >::type C;
344 detail::bfs_dispatch<C>::apply(ng, s, params,
345 get_param(params, vertex_color));
350 // This version does not initialize colors, user has to.
352 template <class IncidenceGraph, class P, class T, class R>
353 void breadth_first_visit
354 (const IncidenceGraph& g,
355 typename graph_traits<IncidenceGraph>::vertex_descriptor s,
356 const bgl_named_params<P, T, R>& params)
358 // The graph is passed by *const* reference so that graph adaptors
359 // (temporaries) can be passed into this function. However, the
360 // graph is not really const since we may write to property maps
362 IncidenceGraph& ng = const_cast<IncidenceGraph&>(g);
364 typedef graph_traits<IncidenceGraph> Traits;
366 typedef typename Traits::vertex_descriptor vertex_descriptor;
367 typedef boost::queue<vertex_descriptor> queue_t;
372 choose_param(get_param(params, buffer_param_t()), boost::ref(Q)).get(),
373 choose_param(get_param(params, graph_visitor),
374 make_bfs_visitor(null_visitor())),
375 choose_pmap(get_param(params, vertex_color), ng, vertex_color)
381 template <typename Graph, typename Source>
382 struct breadth_first_search_impl {
383 typedef void result_type;
384 template <typename ArgPack>
385 void operator()(const Graph& g, const Source& source, const ArgPack& arg_pack) {
386 using namespace boost::graph::keywords;
387 typename boost::graph_traits<Graph>::vertex_descriptor sources[1] = {source};
388 boost::queue<typename boost::graph_traits<Graph>::vertex_descriptor> Q;
389 boost::breadth_first_search(g,
392 boost::unwrap_ref(arg_pack[_buffer | boost::ref(Q)]),
393 arg_pack[_visitor | make_bfs_visitor(null_visitor())],
394 boost::detail::make_color_map_from_arg_pack(g, arg_pack));
398 BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(breadth_first_search, 2, 4)
402 // Named Parameter Variant
403 BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(breadth_first_search, 2)
408 #ifdef BOOST_GRAPH_USE_MPI
409 # include <boost/graph/distributed/breadth_first_search.hpp>
412 #endif // BOOST_GRAPH_BREADTH_FIRST_SEARCH_HPP