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/concept/assert.hpp>
28
29#ifdef BOOST_GRAPH_USE_MPI
30#include <boost/graph/distributed/concepts.hpp>
31#endif // BOOST_GRAPH_USE_MPI
32
33namespace boost {
34
35 template <class Visitor, class Graph>
36 struct BFSVisitorConcept {
37 void constraints() {
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);
43 vis.tree_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);
48 }
49 Visitor vis;
50 Graph g;
51 typename graph_traits<Graph>::vertex_descriptor u;
52 typename graph_traits<Graph>::edge_descriptor e;
53 };
54
55
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)
63 {
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;
72
73 for (; sources_begin != sources_end; ++sources_begin) {
74 Vertex s = *sources_begin;
75 put(color, s, Color::gray()); vis.discover_vertex(s, g);
76 Q.push(s);
77 }
78 while (! Q.empty()) {
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);
85 Q.push(v);
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);
89 }
90 } // end for
91 put(color, u, Color::black()); vis.finish_vertex(u, g);
92 } // end while
93 } // breadth_first_visit
94
95 // Single-source version
96 template <class IncidenceGraph, class Buffer, class BFSVisitor,
97 class ColorMap>
98 void breadth_first_visit
99 (const IncidenceGraph& g,
100 typename graph_traits<IncidenceGraph>::vertex_descriptor s,
101 Buffer& Q, BFSVisitor vis, ColorMap color)
102 {
103 typename graph_traits<IncidenceGraph>::vertex_descriptor sources[1] = {s};
104 breadth_first_visit(g, sources, sources + 1, Q, vis, color);
105 }
106
107
108 template <class VertexListGraph, class SourceIterator,
109 class Buffer, class BFSVisitor,
110 class ColorMap>
111 void breadth_first_search
112 (const VertexListGraph& g,
113 SourceIterator sources_begin, SourceIterator sources_end,
114 Buffer& Q, BFSVisitor vis, ColorMap color)
115 {
116 // Initialization
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());
123 }
124 breadth_first_visit(g, sources_begin, sources_end, Q, vis, color);
125 }
126
127 template <class VertexListGraph, class Buffer, class BFSVisitor,
128 class ColorMap>
129 void breadth_first_search
130 (const VertexListGraph& g,
131 typename graph_traits<VertexListGraph>::vertex_descriptor s,
132 Buffer& Q, BFSVisitor vis, ColorMap color)
133 {
134 typename graph_traits<VertexListGraph>::vertex_descriptor sources[1] = {s};
135 breadth_first_search(g, sources, sources + 1, Q, vis, color);
136 }
137
138 namespace graph { struct bfs_visitor_event_not_overridden {}; }
139
140
141 template <class Visitors = null_visitor>
142 class bfs_visitor {
143 public:
144 bfs_visitor() { }
145 bfs_visitor(Visitors vis) : m_vis(vis) { }
146
147 template <class Vertex, class Graph>
148 graph::bfs_visitor_event_not_overridden
149 initialize_vertex(Vertex u, Graph& g)
150 {
151 invoke_visitors(m_vis, u, g, ::boost::on_initialize_vertex());
152 return graph::bfs_visitor_event_not_overridden();
153 }
154
155 template <class Vertex, class Graph>
156 graph::bfs_visitor_event_not_overridden
157 discover_vertex(Vertex u, Graph& g)
158 {
159 invoke_visitors(m_vis, u, g, ::boost::on_discover_vertex());
160 return graph::bfs_visitor_event_not_overridden();
161 }
162
163 template <class Vertex, class Graph>
164 graph::bfs_visitor_event_not_overridden
165 examine_vertex(Vertex u, Graph& g)
166 {
167 invoke_visitors(m_vis, u, g, ::boost::on_examine_vertex());
168 return graph::bfs_visitor_event_not_overridden();
169 }
170
171 template <class Edge, class Graph>
172 graph::bfs_visitor_event_not_overridden
173 examine_edge(Edge e, Graph& g)
174 {
175 invoke_visitors(m_vis, e, g, ::boost::on_examine_edge());
176 return graph::bfs_visitor_event_not_overridden();
177 }
178
179 template <class Edge, class Graph>
180 graph::bfs_visitor_event_not_overridden
181 tree_edge(Edge e, Graph& g)
182 {
183 invoke_visitors(m_vis, e, g, ::boost::on_tree_edge());
184 return graph::bfs_visitor_event_not_overridden();
185 }
186
187 template <class Edge, class Graph>
188 graph::bfs_visitor_event_not_overridden
189 non_tree_edge(Edge e, Graph& g)
190 {
191 invoke_visitors(m_vis, e, g, ::boost::on_non_tree_edge());
192 return graph::bfs_visitor_event_not_overridden();
193 }
194
195 template <class Edge, class Graph>
196 graph::bfs_visitor_event_not_overridden
197 gray_target(Edge e, Graph& g)
198 {
199 invoke_visitors(m_vis, e, g, ::boost::on_gray_target());
200 return graph::bfs_visitor_event_not_overridden();
201 }
202
203 template <class Edge, class Graph>
204 graph::bfs_visitor_event_not_overridden
205 black_target(Edge e, Graph& g)
206 {
207 invoke_visitors(m_vis, e, g, ::boost::on_black_target());
208 return graph::bfs_visitor_event_not_overridden();
209 }
210
211 template <class Vertex, class Graph>
212 graph::bfs_visitor_event_not_overridden
213 finish_vertex(Vertex u, Graph& g)
214 {
215 invoke_visitors(m_vis, u, g, ::boost::on_finish_vertex());
216 return graph::bfs_visitor_event_not_overridden();
217 }
218
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)
228
229 protected:
230 Visitors m_vis;
231 };
232 template <class Visitors>
233 bfs_visitor<Visitors>
234 make_bfs_visitor(Visitors vis) {
235 return bfs_visitor<Visitors>(vis);
236 }
237 typedef bfs_visitor<> default_bfs_visitor;
238
239
240 namespace detail {
241
242 template <class VertexListGraph, class ColorMap, class BFSVisitor,
243 class P, class T, class R>
244 void bfs_helper
245 (VertexListGraph& g,
246 typename graph_traits<VertexListGraph>::vertex_descriptor s,
247 ColorMap color,
248 BFSVisitor vis,
249 const bgl_named_params<P, T, R>& params,
250 boost::mpl::false_)
251 {
252 typedef graph_traits<VertexListGraph> Traits;
253 // Buffer default
254 typedef typename Traits::vertex_descriptor Vertex;
255 typedef boost::queue<Vertex> queue_t;
256 queue_t Q;
257 breadth_first_search
258 (g, s,
259 choose_param(get_param(params, buffer_param_t()), boost::ref(Q)).get(),
260 vis, color);
261 }
262
263#ifdef BOOST_GRAPH_USE_MPI
264 template <class DistributedGraph, class ColorMap, class BFSVisitor,
265 class P, class T, class R>
266 void bfs_helper
267 (DistributedGraph& g,
268 typename graph_traits<DistributedGraph>::vertex_descriptor s,
269 ColorMap color,
270 BFSVisitor vis,
271 const bgl_named_params<P, T, R>& params,
272 boost::mpl::true_);
273#endif // BOOST_GRAPH_USE_MPI
274
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.
279
280 template <class ColorMap>
281 struct bfs_dispatch {
282 template <class VertexListGraph, class P, class T, class R>
283 static void apply
284 (VertexListGraph& g,
285 typename graph_traits<VertexListGraph>::vertex_descriptor s,
286 const bgl_named_params<P, T, R>& params,
287 ColorMap color)
288 {
289 bfs_helper
290 (g, s, color,
291 choose_param(get_param(params, graph_visitor),
292 make_bfs_visitor(vis: null_visitor())),
293 params,
294 boost::mpl::bool_<
295 boost::is_base_and_derived<
296 distributed_graph_tag,
297 typename graph_traits<VertexListGraph>::traversal_category>::value>());
298 }
299 };
300
301 template <>
302 struct bfs_dispatch<param_not_found> {
303 template <class VertexListGraph, class P, class T, class R>
304 static void apply
305 (VertexListGraph& g,
306 typename graph_traits<VertexListGraph>::vertex_descriptor s,
307 const bgl_named_params<P, T, R>& params,
308 param_not_found)
309 {
310 null_visitor null_vis;
311
312 bfs_helper
313 (g, s,
314 make_two_bit_color_map
315 (num_vertices(g),
316 choose_const_pmap(get_param(params, vertex_index),
317 g, vertex_index)),
318 choose_param(get_param(params, graph_visitor),
319 make_bfs_visitor(vis: null_vis)),
320 params,
321 boost::mpl::bool_<
322 boost::is_base_and_derived<
323 distributed_graph_tag,
324 typename graph_traits<VertexListGraph>::traversal_category>::value>());
325 }
326 };
327
328 } // namespace detail
329
330#if 1
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)
337 {
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
341 // of the graph.
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));
346 }
347#endif
348
349
350 // This version does not initialize colors, user has to.
351
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)
357 {
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
361 // of the graph.
362 IncidenceGraph& ng = const_cast<IncidenceGraph&>(g);
363
364 typedef graph_traits<IncidenceGraph> Traits;
365 // Buffer default
366 typedef typename Traits::vertex_descriptor vertex_descriptor;
367 typedef boost::queue<vertex_descriptor> queue_t;
368 queue_t Q;
369
370 breadth_first_visit
371 (ng, s,
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(vis: null_visitor())),
375 choose_pmap(get_param(params, vertex_color), ng, vertex_color)
376 );
377 }
378
379 namespace graph {
380 namespace detail {
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,
390 &sources[0],
391 &sources[1],
392 boost::unwrap_ref(arg_pack[_buffer | boost::ref(Q)]),
393 arg_pack[_visitor | make_bfs_visitor(vis: null_visitor())],
394 boost::detail::make_color_map_from_arg_pack(g, arg_pack));
395 }
396 };
397 }
398 BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(breadth_first_search, 2, 4)
399 }
400
401#if 0
402 // Named Parameter Variant
403 BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(breadth_first_search, 2)
404#endif
405
406} // namespace boost
407
408#ifdef BOOST_GRAPH_USE_MPI
409# include <boost/graph/distributed/breadth_first_search.hpp>
410#endif
411
412#endif // BOOST_GRAPH_BREADTH_FIRST_SEARCH_HPP
413
414

source code of boost/boost/graph/breadth_first_search.hpp