Line data Source code
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 : template <class Visitor, class Graph>
35 : struct BFSVisitorConcept {
36 : void constraints() {
37 : BOOST_CONCEPT_ASSERT(( CopyConstructibleConcept<Visitor> ));
38 : vis.initialize_vertex(u, g);
39 : vis.discover_vertex(u, g);
40 : vis.examine_vertex(u, g);
41 : vis.examine_edge(e, g);
42 : vis.tree_edge(e, g);
43 : vis.non_tree_edge(e, g);
44 : vis.gray_target(e, g);
45 : vis.black_target(e, g);
46 : vis.finish_vertex(u, g);
47 : }
48 : Visitor vis;
49 : Graph g;
50 : typename graph_traits<Graph>::vertex_descriptor u;
51 : typename graph_traits<Graph>::edge_descriptor e;
52 : };
53 :
54 :
55 : // Multiple-source version
56 : template <class IncidenceGraph, class Buffer, class BFSVisitor,
57 : class ColorMap, class SourceIterator>
58 0 : void breadth_first_visit
59 : (const IncidenceGraph& g,
60 : SourceIterator sources_begin, SourceIterator sources_end,
61 : Buffer& Q, BFSVisitor vis, ColorMap color)
62 : {
63 : BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<IncidenceGraph> ));
64 : typedef graph_traits<IncidenceGraph> GTraits;
65 : typedef typename GTraits::vertex_descriptor Vertex;
66 : BOOST_CONCEPT_ASSERT(( BFSVisitorConcept<BFSVisitor, IncidenceGraph> ));
67 : BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<ColorMap, Vertex> ));
68 : typedef typename property_traits<ColorMap>::value_type ColorValue;
69 : typedef color_traits<ColorValue> Color;
70 0 : typename GTraits::out_edge_iterator ei, ei_end;
71 :
72 0 : for (; sources_begin != sources_end; ++sources_begin) {
73 0 : Vertex s = *sources_begin;
74 0 : put(color, s, Color::gray()); vis.discover_vertex(s, g);
75 0 : Q.push(s);
76 : }
77 0 : while (! Q.empty()) {
78 0 : Vertex u = Q.top(); Q.pop(); vis.examine_vertex(u, g);
79 0 : for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {
80 0 : Vertex v = target(*ei, g); vis.examine_edge(*ei, g);
81 0 : ColorValue v_color = get(color, v);
82 0 : if (v_color == Color::white()) { vis.tree_edge(*ei, g);
83 0 : put(color, v, Color::gray()); vis.discover_vertex(v, g);
84 0 : Q.push(v);
85 0 : } else { vis.non_tree_edge(*ei, g);
86 0 : if (v_color == Color::gray()) vis.gray_target(*ei, g);
87 0 : else vis.black_target(*ei, g);
88 : }
89 : } // end for
90 0 : put(color, u, Color::black()); vis.finish_vertex(u, g);
91 : } // end while
92 0 : } // breadth_first_visit
93 :
94 : // Single-source version
95 : template <class IncidenceGraph, class Buffer, class BFSVisitor,
96 : class ColorMap>
97 : void breadth_first_visit
98 : (const IncidenceGraph& g,
99 : typename graph_traits<IncidenceGraph>::vertex_descriptor s,
100 : Buffer& Q, BFSVisitor vis, ColorMap color)
101 : {
102 : typename graph_traits<IncidenceGraph>::vertex_descriptor sources[1] = {s};
103 : breadth_first_visit(g, sources, sources + 1, Q, vis, color);
104 : }
105 :
106 :
107 : template <class VertexListGraph, class SourceIterator,
108 : class Buffer, class BFSVisitor,
109 : class ColorMap>
110 : void breadth_first_search
111 : (const VertexListGraph& g,
112 : SourceIterator sources_begin, SourceIterator sources_end,
113 : Buffer& Q, BFSVisitor vis, ColorMap color)
114 : {
115 : // Initialization
116 : typedef typename property_traits<ColorMap>::value_type ColorValue;
117 : typedef color_traits<ColorValue> Color;
118 : typename boost::graph_traits<VertexListGraph>::vertex_iterator i, i_end;
119 : for (boost::tie(i, i_end) = vertices(g); i != i_end; ++i) {
120 : vis.initialize_vertex(*i, g);
121 : put(color, *i, Color::white());
122 : }
123 : breadth_first_visit(g, sources_begin, sources_end, Q, vis, color);
124 : }
125 :
126 : template <class VertexListGraph, class Buffer, class BFSVisitor,
127 : class ColorMap>
128 : void breadth_first_search
129 : (const VertexListGraph& g,
130 : typename graph_traits<VertexListGraph>::vertex_descriptor s,
131 : Buffer& Q, BFSVisitor vis, ColorMap color)
132 : {
133 : typename graph_traits<VertexListGraph>::vertex_descriptor sources[1] = {s};
134 : breadth_first_search(g, sources, sources + 1, Q, vis, color);
135 : }
136 :
137 : namespace graph { struct bfs_visitor_event_not_overridden {}; }
138 :
139 :
140 : template <class Visitors = null_visitor>
141 : class bfs_visitor {
142 : public:
143 : bfs_visitor() { }
144 0 : bfs_visitor(Visitors vis) : m_vis(vis) { }
145 :
146 : template <class Vertex, class Graph>
147 : graph::bfs_visitor_event_not_overridden
148 0 : initialize_vertex(Vertex u, Graph& g)
149 : {
150 0 : invoke_visitors(m_vis, u, g, ::boost::on_initialize_vertex());
151 : return graph::bfs_visitor_event_not_overridden();
152 : }
153 :
154 : template <class Vertex, class Graph>
155 : graph::bfs_visitor_event_not_overridden
156 0 : discover_vertex(Vertex u, Graph& g)
157 : {
158 0 : invoke_visitors(m_vis, u, g, ::boost::on_discover_vertex());
159 : return graph::bfs_visitor_event_not_overridden();
160 : }
161 :
162 : template <class Vertex, class Graph>
163 : graph::bfs_visitor_event_not_overridden
164 0 : examine_vertex(Vertex u, Graph& g)
165 : {
166 0 : invoke_visitors(m_vis, u, g, ::boost::on_examine_vertex());
167 : return graph::bfs_visitor_event_not_overridden();
168 : }
169 :
170 : template <class Edge, class Graph>
171 : graph::bfs_visitor_event_not_overridden
172 : examine_edge(Edge e, Graph& g)
173 : {
174 : invoke_visitors(m_vis, e, g, ::boost::on_examine_edge());
175 : return graph::bfs_visitor_event_not_overridden();
176 : }
177 :
178 : template <class Edge, class Graph>
179 : graph::bfs_visitor_event_not_overridden
180 : tree_edge(Edge e, Graph& g)
181 : {
182 : invoke_visitors(m_vis, e, g, ::boost::on_tree_edge());
183 : return graph::bfs_visitor_event_not_overridden();
184 : }
185 :
186 : template <class Edge, class Graph>
187 : graph::bfs_visitor_event_not_overridden
188 : non_tree_edge(Edge e, Graph& g)
189 : {
190 : invoke_visitors(m_vis, e, g, ::boost::on_non_tree_edge());
191 : return graph::bfs_visitor_event_not_overridden();
192 : }
193 :
194 : template <class Edge, class Graph>
195 : graph::bfs_visitor_event_not_overridden
196 : gray_target(Edge e, Graph& g)
197 : {
198 : invoke_visitors(m_vis, e, g, ::boost::on_gray_target());
199 : return graph::bfs_visitor_event_not_overridden();
200 : }
201 :
202 : template <class Edge, class Graph>
203 : graph::bfs_visitor_event_not_overridden
204 : black_target(Edge e, Graph& g)
205 : {
206 : invoke_visitors(m_vis, e, g, ::boost::on_black_target());
207 : return graph::bfs_visitor_event_not_overridden();
208 : }
209 :
210 : template <class Vertex, class Graph>
211 : graph::bfs_visitor_event_not_overridden
212 : finish_vertex(Vertex u, Graph& g)
213 : {
214 : invoke_visitors(m_vis, u, g, ::boost::on_finish_vertex());
215 : return graph::bfs_visitor_event_not_overridden();
216 : }
217 :
218 : BOOST_GRAPH_EVENT_STUB(on_initialize_vertex,bfs)
219 : BOOST_GRAPH_EVENT_STUB(on_discover_vertex,bfs)
220 : BOOST_GRAPH_EVENT_STUB(on_examine_vertex,bfs)
221 : BOOST_GRAPH_EVENT_STUB(on_examine_edge,bfs)
222 : BOOST_GRAPH_EVENT_STUB(on_tree_edge,bfs)
223 : BOOST_GRAPH_EVENT_STUB(on_non_tree_edge,bfs)
224 : BOOST_GRAPH_EVENT_STUB(on_gray_target,bfs)
225 : BOOST_GRAPH_EVENT_STUB(on_black_target,bfs)
226 : BOOST_GRAPH_EVENT_STUB(on_finish_vertex,bfs)
227 :
228 : protected:
229 : Visitors m_vis;
230 : };
231 : template <class Visitors>
232 : bfs_visitor<Visitors>
233 : make_bfs_visitor(Visitors vis) {
234 : return bfs_visitor<Visitors>(vis);
235 : }
236 : typedef bfs_visitor<> default_bfs_visitor;
237 :
238 :
239 : namespace detail {
240 :
241 : template <class VertexListGraph, class ColorMap, class BFSVisitor,
242 : class P, class T, class R>
243 : void bfs_helper
244 : (VertexListGraph& g,
245 : typename graph_traits<VertexListGraph>::vertex_descriptor s,
246 : ColorMap color,
247 : BFSVisitor vis,
248 : const bgl_named_params<P, T, R>& params,
249 : boost::mpl::false_)
250 : {
251 : typedef graph_traits<VertexListGraph> Traits;
252 : // Buffer default
253 : typedef typename Traits::vertex_descriptor Vertex;
254 : typedef boost::queue<Vertex> queue_t;
255 : queue_t Q;
256 : breadth_first_search
257 : (g, s,
258 : choose_param(get_param(params, buffer_param_t()), boost::ref(Q)).get(),
259 : vis, color);
260 : }
261 :
262 : #ifdef BOOST_GRAPH_USE_MPI
263 : template <class DistributedGraph, class ColorMap, class BFSVisitor,
264 : class P, class T, class R>
265 : void bfs_helper
266 : (DistributedGraph& g,
267 : typename graph_traits<DistributedGraph>::vertex_descriptor s,
268 : ColorMap color,
269 : BFSVisitor vis,
270 : const bgl_named_params<P, T, R>& params,
271 : boost::mpl::true_);
272 : #endif // BOOST_GRAPH_USE_MPI
273 :
274 : //-------------------------------------------------------------------------
275 : // Choose between default color and color parameters. Using
276 : // function dispatching so that we don't require vertex index if
277 : // the color default is not being used.
278 :
279 : template <class ColorMap>
280 : struct bfs_dispatch {
281 : template <class VertexListGraph, class P, class T, class R>
282 : static void apply
283 : (VertexListGraph& g,
284 : typename graph_traits<VertexListGraph>::vertex_descriptor s,
285 : const bgl_named_params<P, T, R>& params,
286 : ColorMap color)
287 : {
288 : bfs_helper
289 : (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<
295 : distributed_graph_tag,
296 : typename graph_traits<VertexListGraph>::traversal_category>::value>());
297 : }
298 : };
299 :
300 : template <>
301 : struct bfs_dispatch<param_not_found> {
302 : template <class VertexListGraph, class P, class T, class R>
303 : static void apply
304 : (VertexListGraph& g,
305 : typename graph_traits<VertexListGraph>::vertex_descriptor s,
306 : const bgl_named_params<P, T, R>& params,
307 : param_not_found)
308 : {
309 : null_visitor null_vis;
310 :
311 : bfs_helper
312 : (g, s,
313 : make_two_bit_color_map
314 : (num_vertices(g),
315 : choose_const_pmap(get_param(params, vertex_index),
316 : g, vertex_index)),
317 : choose_param(get_param(params, graph_visitor),
318 : make_bfs_visitor(null_vis)),
319 : params,
320 : boost::mpl::bool_<
321 : boost::is_base_and_derived<
322 : distributed_graph_tag,
323 : typename graph_traits<VertexListGraph>::traversal_category>::value>());
324 : }
325 : };
326 :
327 : } // namespace detail
328 :
329 : #if 1
330 : // Named Parameter Variant
331 : template <class VertexListGraph, class P, class T, class R>
332 : void breadth_first_search
333 : (const VertexListGraph& g,
334 : typename graph_traits<VertexListGraph>::vertex_descriptor s,
335 : const bgl_named_params<P, T, R>& params)
336 : {
337 : // The graph is passed by *const* reference so that graph adaptors
338 : // (temporaries) can be passed into this function. However, the
339 : // graph is not really const since we may write to property maps
340 : // of the graph.
341 : VertexListGraph& ng = const_cast<VertexListGraph&>(g);
342 : typedef typename get_param_type< vertex_color_t, bgl_named_params<P,T,R> >::type C;
343 : detail::bfs_dispatch<C>::apply(ng, s, params,
344 : get_param(params, vertex_color));
345 : }
346 : #endif
347 :
348 :
349 : // This version does not initialize colors, user has to.
350 :
351 : template <class IncidenceGraph, class P, class T, class R>
352 : void breadth_first_visit
353 : (const IncidenceGraph& g,
354 : typename graph_traits<IncidenceGraph>::vertex_descriptor s,
355 : const bgl_named_params<P, T, R>& params)
356 : {
357 : // The graph is passed by *const* reference so that graph adaptors
358 : // (temporaries) can be passed into this function. However, the
359 : // graph is not really const since we may write to property maps
360 : // of the graph.
361 : IncidenceGraph& ng = const_cast<IncidenceGraph&>(g);
362 :
363 : typedef graph_traits<IncidenceGraph> Traits;
364 : // Buffer default
365 : typedef typename Traits::vertex_descriptor vertex_descriptor;
366 : typedef boost::queue<vertex_descriptor> queue_t;
367 : queue_t Q;
368 :
369 : breadth_first_visit
370 : (ng, s,
371 : choose_param(get_param(params, buffer_param_t()), boost::ref(Q)).get(),
372 : choose_param(get_param(params, graph_visitor),
373 : make_bfs_visitor(null_visitor())),
374 : choose_pmap(get_param(params, vertex_color), ng, vertex_color)
375 : );
376 : }
377 :
378 : namespace graph {
379 : namespace detail {
380 : template <typename Graph, typename Source>
381 : struct breadth_first_search_impl {
382 : typedef void result_type;
383 : template <typename ArgPack>
384 : void operator()(const Graph& g, const Source& source, const ArgPack& arg_pack) {
385 : using namespace boost::graph::keywords;
386 : typename boost::graph_traits<Graph>::vertex_descriptor sources[1] = {source};
387 : boost::queue<typename boost::graph_traits<Graph>::vertex_descriptor> Q;
388 : boost::breadth_first_search(g,
389 : &sources[0],
390 : &sources[1],
391 : boost::unwrap_ref(arg_pack[_buffer | boost::ref(Q)]),
392 : arg_pack[_visitor | make_bfs_visitor(null_visitor())],
393 : boost::detail::make_color_map_from_arg_pack(g, arg_pack));
394 : }
395 : };
396 : }
397 : BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(breadth_first_search, 2, 4)
398 : }
399 :
400 : #if 0
401 : // Named Parameter Variant
402 : BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(breadth_first_search, 2)
403 : #endif
404 :
405 : } // namespace boost
406 :
407 : #include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/breadth_first_search.hpp>)
408 :
409 : #endif // BOOST_GRAPH_BREADTH_FIRST_SEARCH_HPP
410 :
|
