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
32namespace boost
33{
34
35template < 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
57template < class IncidenceGraph, class Buffer, class BFSVisitor, class ColorMap,
58 class SourceIterator >
59void 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
110template < class IncidenceGraph, class Buffer, class BFSVisitor,
111 class ColorMap >
112void 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
121template < class VertexListGraph, class SourceIterator, class Buffer,
122 class BFSVisitor, class ColorMap >
123void 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
139template < class VertexListGraph, class Buffer, class BFSVisitor,
140 class ColorMap >
141void 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
150namespace graph
151{
152 struct bfs_visitor_event_not_overridden
153 {
154 };
155}
156
157template < class Visitors = null_visitor > class bfs_visitor
158{
159public:
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
237protected:
238 Visitors m_vis;
239};
240template < class Visitors >
241bfs_visitor< Visitors > make_bfs_visitor(Visitors vis)
242{
243 return bfs_visitor< Visitors >(vis);
244}
245typedef bfs_visitor<> default_bfs_visitor;
246
247namespace 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
327template < class VertexListGraph, class P, class T, class R >
328void 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
346template < class IncidenceGraph, class P, class T, class R >
347void 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
370namespace 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

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