]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
33 | namespace 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(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(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(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(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 |