]>
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_NEIGHBOR_BREADTH_FIRST_SEARCH_HPP | |
12 | #define BOOST_GRAPH_NEIGHBOR_BREADTH_FIRST_SEARCH_HPP | |
13 | ||
14 | /* | |
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) | |
18 | */ | |
19 | #include <boost/config.hpp> | |
20 | #include <boost/ref.hpp> | |
21 | #include <vector> | |
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> | |
28 | ||
f67539c2 TL |
29 | namespace boost |
30 | { | |
7c673cae | 31 | |
f67539c2 TL |
32 | template < class Visitor, class Graph > struct NeighborBFSVisitorConcept |
33 | { | |
34 | void constraints() | |
35 | { | |
36 | BOOST_CONCEPT_ASSERT((CopyConstructibleConcept< Visitor >)); | |
37 | vis.initialize_vertex(u, g); | |
38 | vis.discover_vertex(u, g); | |
39 | vis.examine_vertex(u, g); | |
40 | vis.examine_out_edge(e, g); | |
41 | vis.examine_in_edge(e, g); | |
42 | vis.tree_out_edge(e, g); | |
43 | vis.tree_in_edge(e, g); | |
44 | vis.non_tree_out_edge(e, g); | |
45 | vis.non_tree_in_edge(e, g); | |
46 | vis.gray_target(e, g); | |
47 | vis.black_target(e, g); | |
48 | vis.gray_source(e, g); | |
49 | vis.black_source(e, g); | |
50 | vis.finish_vertex(u, g); | |
7c673cae FG |
51 | } |
52 | Visitor vis; | |
53 | Graph g; | |
f67539c2 TL |
54 | typename graph_traits< Graph >::vertex_descriptor u; |
55 | typename graph_traits< Graph >::edge_descriptor e; | |
56 | }; | |
7c673cae | 57 | |
f67539c2 TL |
58 | template < class Visitors = null_visitor > class neighbor_bfs_visitor |
59 | { | |
60 | public: | |
61 | neighbor_bfs_visitor(Visitors vis = Visitors()) : m_vis(vis) {} | |
7c673cae | 62 | |
f67539c2 TL |
63 | template < class Vertex, class Graph > |
64 | void initialize_vertex(Vertex u, Graph& g) | |
65 | { | |
66 | invoke_visitors(m_vis, u, g, on_initialize_vertex()); | |
7c673cae | 67 | } |
f67539c2 TL |
68 | template < class Vertex, class Graph > |
69 | void discover_vertex(Vertex u, Graph& g) | |
70 | { | |
71 | invoke_visitors(m_vis, u, g, on_discover_vertex()); | |
7c673cae | 72 | } |
f67539c2 TL |
73 | template < class Vertex, class Graph > |
74 | void examine_vertex(Vertex u, Graph& g) | |
75 | { | |
76 | invoke_visitors(m_vis, u, g, on_examine_vertex()); | |
7c673cae | 77 | } |
f67539c2 TL |
78 | template < class Edge, class Graph > void examine_out_edge(Edge e, Graph& g) |
79 | { | |
80 | invoke_visitors(m_vis, e, g, on_examine_edge()); | |
7c673cae | 81 | } |
f67539c2 TL |
82 | template < class Edge, class Graph > void tree_out_edge(Edge e, Graph& g) |
83 | { | |
84 | invoke_visitors(m_vis, e, g, on_tree_edge()); | |
7c673cae | 85 | } |
f67539c2 TL |
86 | template < class Edge, class Graph > |
87 | void non_tree_out_edge(Edge e, Graph& g) | |
88 | { | |
89 | invoke_visitors(m_vis, e, g, on_non_tree_edge()); | |
7c673cae | 90 | } |
f67539c2 TL |
91 | template < class Edge, class Graph > void gray_target(Edge e, Graph& g) |
92 | { | |
93 | invoke_visitors(m_vis, e, g, on_gray_target()); | |
7c673cae | 94 | } |
f67539c2 TL |
95 | template < class Edge, class Graph > void black_target(Edge e, Graph& g) |
96 | { | |
97 | invoke_visitors(m_vis, e, g, on_black_target()); | |
7c673cae | 98 | } |
f67539c2 TL |
99 | template < class Edge, class Graph > void examine_in_edge(Edge e, Graph& g) |
100 | { | |
101 | invoke_visitors(m_vis, e, g, on_examine_edge()); | |
7c673cae | 102 | } |
f67539c2 TL |
103 | template < class Edge, class Graph > void tree_in_edge(Edge e, Graph& g) |
104 | { | |
105 | invoke_visitors(m_vis, e, g, on_tree_edge()); | |
7c673cae | 106 | } |
f67539c2 TL |
107 | template < class Edge, class Graph > void non_tree_in_edge(Edge e, Graph& g) |
108 | { | |
109 | invoke_visitors(m_vis, e, g, on_non_tree_edge()); | |
7c673cae | 110 | } |
f67539c2 TL |
111 | template < class Edge, class Graph > void gray_source(Edge e, Graph& g) |
112 | { | |
113 | invoke_visitors(m_vis, e, g, on_gray_target()); | |
7c673cae | 114 | } |
f67539c2 TL |
115 | template < class Edge, class Graph > void black_source(Edge e, Graph& g) |
116 | { | |
117 | invoke_visitors(m_vis, e, g, on_black_target()); | |
7c673cae | 118 | } |
f67539c2 TL |
119 | template < class Vertex, class Graph > |
120 | void finish_vertex(Vertex u, Graph& g) | |
121 | { | |
122 | invoke_visitors(m_vis, u, g, on_finish_vertex()); | |
7c673cae | 123 | } |
f67539c2 TL |
124 | |
125 | protected: | |
7c673cae | 126 | Visitors m_vis; |
f67539c2 | 127 | }; |
7c673cae | 128 | |
f67539c2 TL |
129 | template < class Visitors > |
130 | neighbor_bfs_visitor< Visitors > make_neighbor_bfs_visitor(Visitors vis) | |
131 | { | |
132 | return neighbor_bfs_visitor< Visitors >(vis); | |
133 | } | |
7c673cae | 134 | |
f67539c2 TL |
135 | namespace detail |
136 | { | |
7c673cae | 137 | |
f67539c2 TL |
138 | template < class BidirectionalGraph, class Buffer, class BFSVisitor, |
139 | class ColorMap > | |
140 | void neighbor_bfs_impl(const BidirectionalGraph& g, | |
141 | typename graph_traits< BidirectionalGraph >::vertex_descriptor s, | |
142 | Buffer& Q, BFSVisitor vis, ColorMap color) | |
7c673cae FG |
143 | |
144 | { | |
f67539c2 TL |
145 | BOOST_CONCEPT_ASSERT((BidirectionalGraphConcept< BidirectionalGraph >)); |
146 | typedef graph_traits< BidirectionalGraph > GTraits; | |
147 | typedef typename GTraits::vertex_descriptor Vertex; | |
148 | typedef typename GTraits::edge_descriptor Edge; | |
149 | BOOST_CONCEPT_ASSERT( | |
150 | (NeighborBFSVisitorConcept< BFSVisitor, BidirectionalGraph >)); | |
151 | BOOST_CONCEPT_ASSERT((ReadWritePropertyMapConcept< ColorMap, Vertex >)); | |
152 | typedef typename property_traits< ColorMap >::value_type ColorValue; | |
153 | typedef color_traits< ColorValue > Color; | |
7c673cae | 154 | |
f67539c2 TL |
155 | put(color, s, Color::gray()); |
156 | vis.discover_vertex(s, g); | |
157 | Q.push(s); | |
158 | while (!Q.empty()) | |
159 | { | |
160 | Vertex u = Q.top(); | |
161 | Q.pop(); // pop before push to avoid problem if Q is priority_queue. | |
162 | vis.examine_vertex(u, g); | |
7c673cae | 163 | |
f67539c2 TL |
164 | typename GTraits::out_edge_iterator ei, ei_end; |
165 | for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) | |
166 | { | |
167 | Edge e = *ei; | |
168 | vis.examine_out_edge(e, g); | |
169 | Vertex v = target(e, g); | |
170 | ColorValue v_color = get(color, v); | |
171 | if (v_color == Color::white()) | |
172 | { | |
173 | vis.tree_out_edge(e, g); | |
174 | put(color, v, Color::gray()); | |
175 | vis.discover_vertex(v, g); | |
176 | Q.push(v); | |
177 | } | |
178 | else | |
179 | { | |
180 | vis.non_tree_out_edge(e, g); | |
181 | if (v_color == Color::gray()) | |
182 | vis.gray_target(e, g); | |
183 | else | |
184 | vis.black_target(e, g); | |
185 | } | |
186 | } // for out-edges | |
7c673cae | 187 | |
f67539c2 TL |
188 | typename GTraits::in_edge_iterator in_ei, in_ei_end; |
189 | for (boost::tie(in_ei, in_ei_end) = in_edges(u, g); | |
190 | in_ei != in_ei_end; ++in_ei) | |
191 | { | |
192 | Edge e = *in_ei; | |
193 | vis.examine_in_edge(e, g); | |
194 | Vertex v = source(e, g); | |
195 | ColorValue v_color = get(color, v); | |
196 | if (v_color == Color::white()) | |
197 | { | |
198 | vis.tree_in_edge(e, g); | |
199 | put(color, v, Color::gray()); | |
200 | vis.discover_vertex(v, g); | |
201 | Q.push(v); | |
202 | } | |
203 | else | |
204 | { | |
205 | vis.non_tree_in_edge(e, g); | |
206 | if (v_color == Color::gray()) | |
207 | vis.gray_source(e, g); | |
208 | else | |
209 | vis.black_source(e, g); | |
210 | } | |
211 | } // for in-edges | |
212 | ||
213 | put(color, u, Color::black()); | |
214 | vis.finish_vertex(u, g); | |
215 | } // while | |
7c673cae FG |
216 | } |
217 | ||
f67539c2 TL |
218 | template < class VertexListGraph, class ColorMap, class BFSVisitor, class P, |
219 | class T, class R > | |
220 | void neighbor_bfs_helper(VertexListGraph& g, | |
221 | typename graph_traits< VertexListGraph >::vertex_descriptor s, | |
222 | ColorMap color, BFSVisitor vis, | |
223 | const bgl_named_params< P, T, R >& params) | |
7c673cae | 224 | { |
f67539c2 TL |
225 | typedef graph_traits< VertexListGraph > Traits; |
226 | // Buffer default | |
227 | typedef typename Traits::vertex_descriptor Vertex; | |
228 | typedef boost::queue< Vertex > queue_t; | |
229 | queue_t Q; | |
230 | // Initialization | |
231 | typedef typename property_traits< ColorMap >::value_type ColorValue; | |
232 | typedef color_traits< ColorValue > Color; | |
233 | typename boost::graph_traits< VertexListGraph >::vertex_iterator i, | |
234 | i_end; | |
235 | for (boost::tie(i, i_end) = vertices(g); i != i_end; ++i) | |
236 | { | |
237 | put(color, *i, Color::white()); | |
238 | vis.initialize_vertex(*i, g); | |
239 | } | |
240 | neighbor_bfs_impl(g, s, | |
241 | choose_param(get_param(params, buffer_param_t()), boost::ref(Q)) | |
242 | .get(), | |
243 | vis, color); | |
7c673cae FG |
244 | } |
245 | ||
246 | //------------------------------------------------------------------------- | |
247 | // Choose between default color and color parameters. Using | |
248 | // function dispatching so that we don't require vertex index if | |
249 | // the color default is not being used. | |
250 | ||
f67539c2 TL |
251 | template < class ColorMap > struct neighbor_bfs_dispatch |
252 | { | |
253 | template < class VertexListGraph, class P, class T, class R > | |
254 | static void apply(VertexListGraph& g, | |
255 | typename graph_traits< VertexListGraph >::vertex_descriptor s, | |
256 | const bgl_named_params< P, T, R >& params, ColorMap color) | |
257 | { | |
258 | neighbor_bfs_helper(g, s, color, | |
259 | choose_param(get_param(params, graph_visitor), | |
260 | make_neighbor_bfs_visitor(null_visitor())), | |
261 | params); | |
262 | } | |
7c673cae FG |
263 | }; |
264 | ||
f67539c2 TL |
265 | template <> struct neighbor_bfs_dispatch< param_not_found > |
266 | { | |
267 | template < class VertexListGraph, class P, class T, class R > | |
268 | static void apply(VertexListGraph& g, | |
269 | typename graph_traits< VertexListGraph >::vertex_descriptor s, | |
270 | const bgl_named_params< P, T, R >& params, param_not_found) | |
271 | { | |
272 | std::vector< default_color_type > color_vec(num_vertices(g)); | |
273 | null_visitor null_vis; | |
7c673cae | 274 | |
f67539c2 TL |
275 | neighbor_bfs_helper(g, s, |
276 | make_iterator_property_map(color_vec.begin(), | |
277 | choose_const_pmap( | |
278 | get_param(params, vertex_index), g, vertex_index), | |
279 | color_vec[0]), | |
280 | choose_param(get_param(params, graph_visitor), | |
281 | make_neighbor_bfs_visitor(null_vis)), | |
282 | params); | |
283 | } | |
284 | }; | |
7c673cae | 285 | |
f67539c2 | 286 | } // namespace detail |
7c673cae | 287 | |
f67539c2 TL |
288 | // Named Parameter Variant |
289 | template < class VertexListGraph, class P, class T, class R > | |
290 | void neighbor_breadth_first_search(const VertexListGraph& g, | |
291 | typename graph_traits< VertexListGraph >::vertex_descriptor s, | |
292 | const bgl_named_params< P, T, R >& params) | |
293 | { | |
7c673cae FG |
294 | // The graph is passed by *const* reference so that graph adaptors |
295 | // (temporaries) can be passed into this function. However, the | |
296 | // graph is not really const since we may write to property maps | |
297 | // of the graph. | |
f67539c2 TL |
298 | VertexListGraph& ng = const_cast< VertexListGraph& >(g); |
299 | typedef typename get_param_type< vertex_color_t, | |
300 | bgl_named_params< P, T, R > >::type C; | |
301 | detail::neighbor_bfs_dispatch< C >::apply( | |
302 | ng, s, params, get_param(params, vertex_color)); | |
303 | } | |
7c673cae | 304 | |
f67539c2 | 305 | // This version does not initialize colors, user has to. |
7c673cae | 306 | |
f67539c2 TL |
307 | template < class IncidenceGraph, class P, class T, class R > |
308 | void neighbor_breadth_first_visit(IncidenceGraph& g, | |
309 | typename graph_traits< IncidenceGraph >::vertex_descriptor s, | |
310 | const bgl_named_params< P, T, R >& params) | |
311 | { | |
312 | typedef graph_traits< IncidenceGraph > Traits; | |
7c673cae | 313 | // Buffer default |
f67539c2 | 314 | typedef boost::queue< typename Traits::vertex_descriptor > queue_t; |
7c673cae FG |
315 | queue_t Q; |
316 | ||
f67539c2 TL |
317 | detail::neighbor_bfs_impl(g, s, |
318 | choose_param(get_param(params, buffer_param_t()), boost::ref(Q)).get(), | |
319 | choose_param(get_param(params, graph_visitor), | |
320 | make_neighbor_bfs_visitor(null_visitor())), | |
321 | choose_pmap(get_param(params, vertex_color), g, vertex_color)); | |
322 | } | |
7c673cae FG |
323 | |
324 | } // namespace boost | |
325 | ||
326 | #endif // BOOST_GRAPH_NEIGHBOR_BREADTH_FIRST_SEARCH_HPP |