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>
20 #include <boost/ref.hpp>
22 #include <boost/pending/queue.hpp>
23 #include <boost/graph/graph_traits.hpp>
24 #include <boost/graph/graph_concepts.hpp>
25 #include <boost/graph/visitors.hpp>
26 #include <boost/graph/named_function_params.hpp>
27 #include <boost/concept/assert.hpp>
31 template <class Visitor, class Graph>
32 struct NeighborBFSVisitorConcept {
34 BOOST_CONCEPT_ASSERT(( CopyConstructibleConcept<Visitor> ));
35 vis.initialize_vertex(u, g);
36 vis.discover_vertex(u, g);
37 vis.examine_vertex(u, g);
38 vis.examine_out_edge(e, g);
39 vis.examine_in_edge(e, g);
40 vis.tree_out_edge(e, g);
41 vis.tree_in_edge(e, g);
42 vis.non_tree_out_edge(e, g);
43 vis.non_tree_in_edge(e, g);
44 vis.gray_target(e, g);
45 vis.black_target(e, g);
46 vis.gray_source(e, g);
47 vis.black_source(e, g);
48 vis.finish_vertex(u, g);
52 typename graph_traits<Graph>::vertex_descriptor u;
53 typename graph_traits<Graph>::edge_descriptor e;
56 template <class Visitors = null_visitor>
57 class neighbor_bfs_visitor {
59 neighbor_bfs_visitor(Visitors vis = Visitors()) : m_vis(vis) { }
61 template <class Vertex, class Graph>
62 void initialize_vertex(Vertex u, Graph& g) {
63 invoke_visitors(m_vis, u, g, on_initialize_vertex());
65 template <class Vertex, class Graph>
66 void discover_vertex(Vertex u, Graph& g) {
67 invoke_visitors(m_vis, u, g, on_discover_vertex());
69 template <class Vertex, class Graph>
70 void examine_vertex(Vertex u, Graph& g) {
71 invoke_visitors(m_vis, u, g, on_examine_vertex());
73 template <class Edge, class Graph>
74 void examine_out_edge(Edge e, Graph& g) {
75 invoke_visitors(m_vis, e, g, on_examine_edge());
77 template <class Edge, class Graph>
78 void tree_out_edge(Edge e, Graph& g) {
79 invoke_visitors(m_vis, e, g, on_tree_edge());
81 template <class Edge, class Graph>
82 void non_tree_out_edge(Edge e, Graph& g) {
83 invoke_visitors(m_vis, e, g, on_non_tree_edge());
85 template <class Edge, class Graph>
86 void gray_target(Edge e, Graph& g) {
87 invoke_visitors(m_vis, e, g, on_gray_target());
89 template <class Edge, class Graph>
90 void black_target(Edge e, Graph& g) {
91 invoke_visitors(m_vis, e, g, on_black_target());
93 template <class Edge, class Graph>
94 void examine_in_edge(Edge e, Graph& g) {
95 invoke_visitors(m_vis, e, g, on_examine_edge());
97 template <class Edge, class Graph>
98 void tree_in_edge(Edge e, Graph& g) {
99 invoke_visitors(m_vis, e, g, on_tree_edge());
101 template <class Edge, class Graph>
102 void non_tree_in_edge(Edge e, Graph& g) {
103 invoke_visitors(m_vis, e, g, on_non_tree_edge());
105 template <class Edge, class Graph>
106 void gray_source(Edge e, Graph& g) {
107 invoke_visitors(m_vis, e, g, on_gray_target());
109 template <class Edge, class Graph>
110 void black_source(Edge e, Graph& g) {
111 invoke_visitors(m_vis, e, g, on_black_target());
113 template <class Vertex, class Graph>
114 void finish_vertex(Vertex u, Graph& g) {
115 invoke_visitors(m_vis, u, g, on_finish_vertex());
121 template <class Visitors>
122 neighbor_bfs_visitor<Visitors>
123 make_neighbor_bfs_visitor(Visitors vis) {
124 return neighbor_bfs_visitor<Visitors>(vis);
129 template <class BidirectionalGraph, class Buffer, class BFSVisitor,
131 void neighbor_bfs_impl
132 (const BidirectionalGraph& g,
133 typename graph_traits<BidirectionalGraph>::vertex_descriptor s,
134 Buffer& Q, BFSVisitor vis, ColorMap color)
137 BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<BidirectionalGraph> ));
138 typedef graph_traits<BidirectionalGraph> GTraits;
139 typedef typename GTraits::vertex_descriptor Vertex;
140 typedef typename GTraits::edge_descriptor Edge;
141 BOOST_CONCEPT_ASSERT((
142 NeighborBFSVisitorConcept<BFSVisitor, BidirectionalGraph> ));
143 BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<ColorMap, Vertex> ));
144 typedef typename property_traits<ColorMap>::value_type ColorValue;
145 typedef color_traits<ColorValue> Color;
147 put(color, s, Color::gray());
148 vis.discover_vertex(s, g);
150 while (! Q.empty()) {
152 Q.pop(); // pop before push to avoid problem if Q is priority_queue.
153 vis.examine_vertex(u, g);
155 typename GTraits::out_edge_iterator ei, ei_end;
156 for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {
158 vis.examine_out_edge(e, g);
159 Vertex v = target(e, g);
160 ColorValue v_color = get(color, v);
161 if (v_color == Color::white()) {
162 vis.tree_out_edge(e, g);
163 put(color, v, Color::gray());
164 vis.discover_vertex(v, g);
167 vis.non_tree_out_edge(e, g);
168 if (v_color == Color::gray())
169 vis.gray_target(e, g);
171 vis.black_target(e, g);
175 typename GTraits::in_edge_iterator in_ei, in_ei_end;
176 for (boost::tie(in_ei, in_ei_end) = in_edges(u, g);
177 in_ei != in_ei_end; ++in_ei) {
179 vis.examine_in_edge(e, g);
180 Vertex v = source(e, g);
181 ColorValue v_color = get(color, v);
182 if (v_color == Color::white()) {
183 vis.tree_in_edge(e, g);
184 put(color, v, Color::gray());
185 vis.discover_vertex(v, g);
188 vis.non_tree_in_edge(e, g);
189 if (v_color == Color::gray())
190 vis.gray_source(e, g);
192 vis.black_source(e, g);
196 put(color, u, Color::black());
197 vis.finish_vertex(u, g);
202 template <class VertexListGraph, class ColorMap, class BFSVisitor,
203 class P, class T, class R>
204 void neighbor_bfs_helper
206 typename graph_traits<VertexListGraph>::vertex_descriptor s,
209 const bgl_named_params<P, T, R>& params)
211 typedef graph_traits<VertexListGraph> Traits;
213 typedef typename Traits::vertex_descriptor Vertex;
214 typedef boost::queue<Vertex> queue_t;
217 typedef typename property_traits<ColorMap>::value_type ColorValue;
218 typedef color_traits<ColorValue> Color;
219 typename boost::graph_traits<VertexListGraph>::vertex_iterator i, i_end;
220 for (boost::tie(i, i_end) = vertices(g); i != i_end; ++i) {
221 put(color, *i, Color::white());
222 vis.initialize_vertex(*i, g);
226 choose_param(get_param(params, buffer_param_t()), boost::ref(Q)).get(),
230 //-------------------------------------------------------------------------
231 // Choose between default color and color parameters. Using
232 // function dispatching so that we don't require vertex index if
233 // the color default is not being used.
235 template <class ColorMap>
236 struct neighbor_bfs_dispatch {
237 template <class VertexListGraph, class P, class T, class R>
240 typename graph_traits<VertexListGraph>::vertex_descriptor s,
241 const bgl_named_params<P, T, R>& params,
246 choose_param(get_param(params, graph_visitor),
247 make_neighbor_bfs_visitor(null_visitor())),
253 struct neighbor_bfs_dispatch<param_not_found> {
254 template <class VertexListGraph, class P, class T, class R>
257 typename graph_traits<VertexListGraph>::vertex_descriptor s,
258 const bgl_named_params<P, T, R>& params,
261 std::vector<default_color_type> color_vec(num_vertices(g));
262 null_visitor null_vis;
266 make_iterator_property_map
268 choose_const_pmap(get_param(params, vertex_index),
269 g, vertex_index), color_vec[0]),
270 choose_param(get_param(params, graph_visitor),
271 make_neighbor_bfs_visitor(null_vis)),
276 } // namespace detail
279 // Named Parameter Variant
280 template <class VertexListGraph, class P, class T, class R>
281 void neighbor_breadth_first_search
282 (const VertexListGraph& g,
283 typename graph_traits<VertexListGraph>::vertex_descriptor s,
284 const bgl_named_params<P, T, R>& params)
286 // The graph is passed by *const* reference so that graph adaptors
287 // (temporaries) can be passed into this function. However, the
288 // graph is not really const since we may write to property maps
290 VertexListGraph& ng = const_cast<VertexListGraph&>(g);
291 typedef typename get_param_type< vertex_color_t, bgl_named_params<P,T,R> >::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;
310 detail::neighbor_bfs_impl
312 choose_param(get_param(params, buffer_param_t()), boost::ref(Q)).get(),
313 choose_param(get_param(params, graph_visitor),
314 make_neighbor_bfs_visitor(null_visitor())),
315 choose_pmap(get_param(params, vertex_color), g, vertex_color)
321 #endif // BOOST_GRAPH_NEIGHBOR_BREADTH_FIRST_SEARCH_HPP