]>
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 | ||
29 | namespace boost { | |
30 | ||
31 | template <class Visitor, class Graph> | |
32 | struct NeighborBFSVisitorConcept { | |
33 | void constraints() { | |
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); | |
49 | } | |
50 | Visitor vis; | |
51 | Graph g; | |
52 | typename graph_traits<Graph>::vertex_descriptor u; | |
53 | typename graph_traits<Graph>::edge_descriptor e; | |
54 | }; | |
55 | ||
56 | template <class Visitors = null_visitor> | |
57 | class neighbor_bfs_visitor { | |
58 | public: | |
59 | neighbor_bfs_visitor(Visitors vis = Visitors()) : m_vis(vis) { } | |
60 | ||
61 | template <class Vertex, class Graph> | |
62 | void initialize_vertex(Vertex u, Graph& g) { | |
63 | invoke_visitors(m_vis, u, g, on_initialize_vertex()); | |
64 | } | |
65 | template <class Vertex, class Graph> | |
66 | void discover_vertex(Vertex u, Graph& g) { | |
67 | invoke_visitors(m_vis, u, g, on_discover_vertex()); | |
68 | } | |
69 | template <class Vertex, class Graph> | |
70 | void examine_vertex(Vertex u, Graph& g) { | |
71 | invoke_visitors(m_vis, u, g, on_examine_vertex()); | |
72 | } | |
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()); | |
76 | } | |
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()); | |
80 | } | |
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()); | |
84 | } | |
85 | template <class Edge, class Graph> | |
86 | void gray_target(Edge e, Graph& g) { | |
87 | invoke_visitors(m_vis, e, g, on_gray_target()); | |
88 | } | |
89 | template <class Edge, class Graph> | |
90 | void black_target(Edge e, Graph& g) { | |
91 | invoke_visitors(m_vis, e, g, on_black_target()); | |
92 | } | |
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()); | |
96 | } | |
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()); | |
100 | } | |
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()); | |
104 | } | |
105 | template <class Edge, class Graph> | |
106 | void gray_source(Edge e, Graph& g) { | |
107 | invoke_visitors(m_vis, e, g, on_gray_target()); | |
108 | } | |
109 | template <class Edge, class Graph> | |
110 | void black_source(Edge e, Graph& g) { | |
111 | invoke_visitors(m_vis, e, g, on_black_target()); | |
112 | } | |
113 | template <class Vertex, class Graph> | |
114 | void finish_vertex(Vertex u, Graph& g) { | |
115 | invoke_visitors(m_vis, u, g, on_finish_vertex()); | |
116 | } | |
117 | protected: | |
118 | Visitors m_vis; | |
119 | }; | |
120 | ||
121 | template <class Visitors> | |
122 | neighbor_bfs_visitor<Visitors> | |
123 | make_neighbor_bfs_visitor(Visitors vis) { | |
124 | return neighbor_bfs_visitor<Visitors>(vis); | |
125 | } | |
126 | ||
127 | namespace detail { | |
128 | ||
129 | template <class BidirectionalGraph, class Buffer, class BFSVisitor, | |
130 | class ColorMap> | |
131 | void neighbor_bfs_impl | |
132 | (const BidirectionalGraph& g, | |
133 | typename graph_traits<BidirectionalGraph>::vertex_descriptor s, | |
134 | Buffer& Q, BFSVisitor vis, ColorMap color) | |
135 | ||
136 | { | |
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; | |
146 | ||
147 | put(color, s, Color::gray()); | |
148 | vis.discover_vertex(s, g); | |
149 | Q.push(s); | |
150 | while (! Q.empty()) { | |
151 | Vertex u = Q.top(); | |
152 | Q.pop(); // pop before push to avoid problem if Q is priority_queue. | |
153 | vis.examine_vertex(u, g); | |
154 | ||
155 | typename GTraits::out_edge_iterator ei, ei_end; | |
156 | for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) { | |
157 | Edge e = *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); | |
165 | Q.push(v); | |
166 | } else { | |
167 | vis.non_tree_out_edge(e, g); | |
168 | if (v_color == Color::gray()) | |
169 | vis.gray_target(e, g); | |
170 | else | |
171 | vis.black_target(e, g); | |
172 | } | |
173 | } // for out-edges | |
174 | ||
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) { | |
178 | Edge e = *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); | |
186 | Q.push(v); | |
187 | } else { | |
188 | vis.non_tree_in_edge(e, g); | |
189 | if (v_color == Color::gray()) | |
190 | vis.gray_source(e, g); | |
191 | else | |
192 | vis.black_source(e, g); | |
193 | } | |
194 | } // for in-edges | |
195 | ||
196 | put(color, u, Color::black()); | |
197 | vis.finish_vertex(u, g); | |
198 | } // while | |
199 | } | |
200 | ||
201 | ||
202 | template <class VertexListGraph, class ColorMap, class BFSVisitor, | |
203 | class P, class T, class R> | |
204 | void neighbor_bfs_helper | |
205 | (VertexListGraph& g, | |
206 | typename graph_traits<VertexListGraph>::vertex_descriptor s, | |
207 | ColorMap color, | |
208 | BFSVisitor vis, | |
209 | const bgl_named_params<P, T, R>& params) | |
210 | { | |
211 | typedef graph_traits<VertexListGraph> Traits; | |
212 | // Buffer default | |
213 | typedef typename Traits::vertex_descriptor Vertex; | |
214 | typedef boost::queue<Vertex> queue_t; | |
215 | queue_t Q; | |
216 | // Initialization | |
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); | |
223 | } | |
224 | neighbor_bfs_impl | |
225 | (g, s, | |
226 | choose_param(get_param(params, buffer_param_t()), boost::ref(Q)).get(), | |
227 | vis, color); | |
228 | } | |
229 | ||
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. | |
234 | ||
235 | template <class ColorMap> | |
236 | struct neighbor_bfs_dispatch { | |
237 | template <class VertexListGraph, class P, class T, class R> | |
238 | static void apply | |
239 | (VertexListGraph& g, | |
240 | typename graph_traits<VertexListGraph>::vertex_descriptor s, | |
241 | const bgl_named_params<P, T, R>& params, | |
242 | ColorMap color) | |
243 | { | |
244 | neighbor_bfs_helper | |
245 | (g, s, color, | |
246 | choose_param(get_param(params, graph_visitor), | |
247 | make_neighbor_bfs_visitor(null_visitor())), | |
248 | params); | |
249 | } | |
250 | }; | |
251 | ||
252 | template <> | |
253 | struct neighbor_bfs_dispatch<param_not_found> { | |
254 | template <class VertexListGraph, class P, class T, class R> | |
255 | static void apply | |
256 | (VertexListGraph& g, | |
257 | typename graph_traits<VertexListGraph>::vertex_descriptor s, | |
258 | const bgl_named_params<P, T, R>& params, | |
259 | param_not_found) | |
260 | { | |
261 | std::vector<default_color_type> color_vec(num_vertices(g)); | |
262 | null_visitor null_vis; | |
263 | ||
264 | neighbor_bfs_helper | |
265 | (g, s, | |
266 | make_iterator_property_map | |
267 | (color_vec.begin(), | |
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)), | |
272 | params); | |
273 | } | |
274 | }; | |
275 | ||
276 | } // namespace detail | |
277 | ||
278 | ||
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) | |
285 | { | |
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 | |
289 | // of the graph. | |
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)); | |
294 | } | |
295 | ||
296 | ||
297 | // This version does not initialize colors, user has to. | |
298 | ||
299 | template <class IncidenceGraph, class P, class T, class R> | |
300 | void neighbor_breadth_first_visit | |
301 | (IncidenceGraph& g, | |
302 | typename graph_traits<IncidenceGraph>::vertex_descriptor s, | |
303 | const bgl_named_params<P, T, R>& params) | |
304 | { | |
305 | typedef graph_traits<IncidenceGraph> Traits; | |
306 | // Buffer default | |
307 | typedef boost::queue<typename Traits::vertex_descriptor> queue_t; | |
308 | queue_t Q; | |
309 | ||
310 | detail::neighbor_bfs_impl | |
311 | (g, s, | |
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) | |
316 | ); | |
317 | } | |
318 | ||
319 | } // namespace boost | |
320 | ||
321 | #endif // BOOST_GRAPH_NEIGHBOR_BREADTH_FIRST_SEARCH_HPP | |
322 |