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_NEIGHBOR_BREADTH_FIRST_SEARCH_HPP
12 #define BOOST_GRAPH_NEIGHBOR_BREADTH_FIRST_SEARCH_HPP
15 Neighbor Breadth First Search
16 Like BFS, but traverses in-edges as well as out-edges.
17 (for directed graphs only. use normal BFS for undirected graphs)
19 #include <boost/config.hpp>
21 #include <boost/pending/queue.hpp>
22 #include <boost/graph/graph_traits.hpp>
23 #include <boost/graph/graph_concepts.hpp>
24 #include <boost/graph/visitors.hpp>
25 #include <boost/graph/named_function_params.hpp>
29 template <class Visitor, class Graph>
30 struct NeighborBFSVisitorConcept {
32 function_requires< CopyConstructibleConcept<Visitor> >();
33 vis.initialize_vertex(u, g);
34 vis.discover_vertex(u, g);
35 vis.examine_vertex(u, g);
36 vis.examine_out_edge(e, g);
37 vis.examine_in_edge(e, g);
38 vis.tree_out_edge(e, g);
39 vis.tree_in_edge(e, g);
40 vis.non_tree_out_edge(e, g);
41 vis.non_tree_in_edge(e, g);
42 vis.gray_target(e, g);
43 vis.black_target(e, g);
44 vis.gray_source(e, g);
45 vis.black_source(e, g);
46 vis.finish_vertex(u, g);
50 typename graph_traits<Graph>::vertex_descriptor u;
51 typename graph_traits<Graph>::edge_descriptor e;
54 template <class Visitors = null_visitor>
55 class neighbor_bfs_visitor {
57 neighbor_bfs_visitor(Visitors vis = Visitors()) : m_vis(vis) { }
59 template <class Vertex, class Graph>
60 void initialize_vertex(Vertex u, Graph& g) {
61 invoke_visitors(m_vis, u, g, on_initialize_vertex());
63 template <class Vertex, class Graph>
64 void discover_vertex(Vertex u, Graph& g) {
65 invoke_visitors(m_vis, u, g, on_discover_vertex());
67 template <class Vertex, class Graph>
68 void examine_vertex(Vertex u, Graph& g) {
69 invoke_visitors(m_vis, u, g, on_examine_vertex());
71 template <class Edge, class Graph>
72 void examine_out_edge(Edge e, Graph& g) {
73 invoke_visitors(m_vis, e, g, on_examine_edge());
75 template <class Edge, class Graph>
76 void tree_out_edge(Edge e, Graph& g) {
77 invoke_visitors(m_vis, e, g, on_tree_edge());
79 template <class Edge, class Graph>
80 void non_tree_out_edge(Edge e, Graph& g) {
81 invoke_visitors(m_vis, e, g, on_non_tree_edge());
83 template <class Edge, class Graph>
84 void gray_target(Edge e, Graph& g) {
85 invoke_visitors(m_vis, e, g, on_gray_target());
87 template <class Edge, class Graph>
88 void black_target(Edge e, Graph& g) {
89 invoke_visitors(m_vis, e, g, on_black_target());
91 template <class Edge, class Graph>
92 void examine_in_edge(Edge e, Graph& g) {
93 invoke_visitors(m_vis, e, g, on_examine_edge());
95 template <class Edge, class Graph>
96 void tree_in_edge(Edge e, Graph& g) {
97 invoke_visitors(m_vis, e, g, on_tree_edge());
99 template <class Edge, class Graph>
100 void non_tree_in_edge(Edge e, Graph& g) {
101 invoke_visitors(m_vis, e, g, on_non_tree_edge());
103 template <class Edge, class Graph>
104 void gray_source(Edge e, Graph& g) {
105 invoke_visitors(m_vis, e, g, on_gray_target());
107 template <class Edge, class Graph>
108 void black_source(Edge e, Graph& g) {
109 invoke_visitors(m_vis, e, g, on_black_target());
111 template <class Vertex, class Graph>
112 void finish_vertex(Vertex u, Graph& g) {
113 invoke_visitors(m_vis, u, g, on_finish_vertex());
119 template <class Visitors>
120 neighbor_bfs_visitor<Visitors>
121 make_neighbor_bfs_visitor(Visitors vis) {
122 return neighbor_bfs_visitor<Visitors>(vis);
127 template <class BidirectionalGraph, class Buffer, class BFSVisitor,
129 void neighbor_bfs_impl
130 (const BidirectionalGraph& g,
131 typename graph_traits<BidirectionalGraph>::vertex_descriptor s,
132 Buffer& Q, BFSVisitor vis, ColorMap color)
135 function_requires< BidirectionalGraphConcept<BidirectionalGraph> >();
136 typedef graph_traits<BidirectionalGraph> GTraits;
137 typedef typename GTraits::vertex_descriptor Vertex;
138 typedef typename GTraits::edge_descriptor Edge;
140 NeighborBFSVisitorConcept<BFSVisitor, BidirectionalGraph> >();
141 function_requires< ReadWritePropertyMapConcept<ColorMap, Vertex> >();
142 typedef typename property_traits<ColorMap>::value_type ColorValue;
143 typedef color_traits<ColorValue> Color;
145 put(color, s, Color::gray());
146 vis.discover_vertex(s, g);
148 while (! Q.empty()) {
150 Q.pop(); // pop before push to avoid problem if Q is priority_queue.
151 vis.examine_vertex(u, g);
153 typename GTraits::out_edge_iterator ei, ei_end;
154 for (tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {
156 vis.examine_out_edge(e, g);
157 Vertex v = target(e, g);
158 ColorValue v_color = get(color, v);
159 if (v_color == Color::white()) {
160 vis.tree_out_edge(e, g);
161 put(color, v, Color::gray());
162 vis.discover_vertex(v, g);
165 vis.non_tree_out_edge(e, g);
166 if (v_color == Color::gray())
167 vis.gray_target(e, g);
169 vis.black_target(e, g);
173 typename GTraits::in_edge_iterator in_ei, in_ei_end;
174 for (tie(in_ei, in_ei_end) = in_edges(u, g);
175 in_ei != in_ei_end; ++in_ei) {
177 vis.examine_in_edge(e, g);
178 Vertex v = source(e, g);
179 ColorValue v_color = get(color, v);
180 if (v_color == Color::white()) {
181 vis.tree_in_edge(e, g);
182 put(color, v, Color::gray());
183 vis.discover_vertex(v, g);
186 vis.non_tree_in_edge(e, g);
187 if (v_color == Color::gray())
188 vis.gray_source(e, g);
190 vis.black_source(e, g);
194 put(color, u, Color::black());
195 vis.finish_vertex(u, g);
200 template <class VertexListGraph, class ColorMap, class BFSVisitor,
201 class P, class T, class R>
202 void neighbor_bfs_helper
204 typename graph_traits<VertexListGraph>::vertex_descriptor s,
207 const bgl_named_params<P, T, R>& params)
209 typedef graph_traits<VertexListGraph> Traits;
211 typedef typename Traits::vertex_descriptor Vertex;
212 typedef boost::queue<Vertex> queue_t;
214 detail::wrap_ref<queue_t> Qref(Q);
216 typedef typename property_traits<ColorMap>::value_type ColorValue;
217 typedef color_traits<ColorValue> Color;
218 typename boost::graph_traits<VertexListGraph>::vertex_iterator i, i_end;
219 for (tie(i, i_end) = vertices(g); i != i_end; ++i) {
220 put(color, *i, Color::white());
221 vis.initialize_vertex(*i, g);
225 choose_param(get_param(params, buffer_param_t()), Qref).ref,
229 //-------------------------------------------------------------------------
230 // Choose between default color and color parameters. Using
231 // function dispatching so that we don't require vertex index if
232 // the color default is not being used.
234 template <class ColorMap>
235 struct neighbor_bfs_dispatch {
236 template <class VertexListGraph, class P, class T, class R>
239 typename graph_traits<VertexListGraph>::vertex_descriptor s,
240 const bgl_named_params<P, T, R>& params,
245 choose_param(get_param(params, graph_visitor),
246 make_neighbor_bfs_visitor(null_visitor())),
252 struct neighbor_bfs_dispatch<detail::error_property_not_found> {
253 template <class VertexListGraph, class P, class T, class R>
256 typename graph_traits<VertexListGraph>::vertex_descriptor s,
257 const bgl_named_params<P, T, R>& params,
258 detail::error_property_not_found)
260 std::vector<default_color_type> color_vec(num_vertices(g));
261 null_visitor null_vis;
265 make_iterator_property_map
267 choose_const_pmap(get_param(params, vertex_index),
268 g, vertex_index), color_vec[0]),
269 choose_param(get_param(params, graph_visitor),
270 make_neighbor_bfs_visitor(null_vis)),
275 } // namespace detail
278 // Named Parameter Variant
279 template <class VertexListGraph, class P, class T, class R>
280 void neighbor_breadth_first_search
281 (const VertexListGraph& g,
282 typename graph_traits<VertexListGraph>::vertex_descriptor s,
283 const bgl_named_params<P, T, R>& params)
285 // The graph is passed by *const* reference so that graph adaptors
286 // (temporaries) can be passed into this function. However, the
287 // graph is not really const since we may write to property maps
289 VertexListGraph& ng = const_cast<VertexListGraph&>(g);
290 typedef typename property_value< bgl_named_params<P,T,R>,
291 vertex_color_t>::type C;
292 detail::neighbor_bfs_dispatch<C>::apply(ng, s, params,
293 get_param(params, vertex_color));
297 // This version does not initialize colors, user has to.
299 template <class IncidenceGraph, class P, class T, class R>
300 void neighbor_breadth_first_visit
302 typename graph_traits<IncidenceGraph>::vertex_descriptor s,
303 const bgl_named_params<P, T, R>& params)
305 typedef graph_traits<IncidenceGraph> Traits;
307 typedef boost::queue<typename Traits::vertex_descriptor> queue_t;
309 detail::wrap_ref<queue_t> Qref(Q);
311 detail::neighbor_bfs_impl
313 choose_param(get_param(params, buffer_param_t()), Qref).ref,
314 choose_param(get_param(params, graph_visitor),
315 make_neighbor_bfs_visitor(null_visitor())),
316 choose_pmap(get_param(params, vertex_color), g, vertex_color)
322 #endif // BOOST_GRAPH_NEIGHBOR_BREADTH_FIRST_SEARCH_HPP