]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | //======================================================================= |
2 | // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. | |
3 | // Copyright 2003 Bruce Barr | |
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 | // Nonrecursive implementation of depth_first_visit_impl submitted by | |
12 | // Bruce Barr, schmoost <at> yahoo.com, May/June 2003. | |
13 | #ifndef BOOST_GRAPH_RECURSIVE_DFS_HPP | |
14 | #define BOOST_GRAPH_RECURSIVE_DFS_HPP | |
15 | ||
16 | #include <boost/config.hpp> | |
17 | #include <boost/graph/graph_traits.hpp> | |
18 | #include <boost/graph/graph_concepts.hpp> | |
19 | #include <boost/graph/properties.hpp> | |
20 | #include <boost/graph/visitors.hpp> | |
21 | #include <boost/graph/named_function_params.hpp> | |
92f5a8d4 | 22 | #include <boost/graph/detail/mpi_include.hpp> |
7c673cae FG |
23 | #include <boost/ref.hpp> |
24 | #include <boost/implicit_cast.hpp> | |
25 | #include <boost/optional.hpp> | |
26 | #include <boost/parameter.hpp> | |
27 | #include <boost/concept/assert.hpp> | |
28 | #include <boost/tti/has_member_function.hpp> | |
29 | ||
30 | #include <vector> | |
31 | #include <utility> | |
32 | ||
f67539c2 TL |
33 | namespace boost |
34 | { | |
35 | ||
36 | template < class Visitor, class Graph > class DFSVisitorConcept | |
37 | { | |
38 | public: | |
39 | void constraints() | |
40 | { | |
41 | BOOST_CONCEPT_ASSERT((CopyConstructibleConcept< Visitor >)); | |
42 | vis.initialize_vertex(u, g); | |
43 | vis.start_vertex(u, g); | |
44 | vis.discover_vertex(u, g); | |
45 | vis.examine_edge(e, g); | |
46 | vis.tree_edge(e, g); | |
47 | vis.back_edge(e, g); | |
48 | vis.forward_or_cross_edge(e, g); | |
49 | // vis.finish_edge(e, g); // Optional for user | |
50 | vis.finish_vertex(u, g); | |
7c673cae | 51 | } |
f67539c2 TL |
52 | |
53 | private: | |
7c673cae FG |
54 | Visitor vis; |
55 | Graph g; | |
f67539c2 TL |
56 | typename graph_traits< Graph >::vertex_descriptor u; |
57 | typename graph_traits< Graph >::edge_descriptor e; | |
58 | }; | |
7c673cae | 59 | |
f67539c2 TL |
60 | namespace detail |
61 | { | |
7c673cae | 62 | |
f67539c2 TL |
63 | struct nontruth2 |
64 | { | |
65 | template < class T, class T2 > | |
66 | bool operator()(const T&, const T2&) const | |
67 | { | |
68 | return false; | |
69 | } | |
7c673cae FG |
70 | }; |
71 | ||
72 | BOOST_TTI_HAS_MEMBER_FUNCTION(finish_edge) | |
73 | ||
f67539c2 TL |
74 | template < bool IsCallable > struct do_call_finish_edge |
75 | { | |
76 | template < typename E, typename G, typename Vis > | |
77 | static void call_finish_edge(Vis& vis, E e, const G& g) | |
78 | { | |
79 | vis.finish_edge(e, g); | |
80 | } | |
7c673cae FG |
81 | }; |
82 | ||
f67539c2 TL |
83 | template <> struct do_call_finish_edge< false > |
84 | { | |
85 | template < typename E, typename G, typename Vis > | |
86 | static void call_finish_edge(Vis&, E, const G&) | |
87 | { | |
88 | } | |
7c673cae FG |
89 | }; |
90 | ||
f67539c2 TL |
91 | template < typename E, typename G, typename Vis > |
92 | void call_finish_edge(Vis& vis, E e, const G& g) | |
93 | { // Only call if method exists | |
94 | #if ((defined(__GNUC__) && (__GNUC__ > 4) \ | |
95 | || ((__GNUC__ == 4) && (__GNUC_MINOR__ >= 9))) \ | |
96 | || defined(__clang__) \ | |
97 | || (defined(__INTEL_COMPILER) && (__INTEL_COMPILER >= 1200))) | |
98 | do_call_finish_edge< has_member_function_finish_edge< Vis, void, | |
99 | boost::mpl::vector< E, const G& > >::value >::call_finish_edge(vis, | |
100 | e, g); | |
7c673cae | 101 | #else |
f67539c2 TL |
102 | do_call_finish_edge< has_member_function_finish_edge< Vis, |
103 | void >::value >::call_finish_edge(vis, e, g); | |
7c673cae FG |
104 | #endif |
105 | } | |
106 | ||
7c673cae FG |
107 | // Define BOOST_RECURSIVE_DFS to use older, recursive version. |
108 | // It is retained for a while in order to perform performance | |
109 | // comparison. | |
110 | #ifndef BOOST_RECURSIVE_DFS | |
111 | ||
112 | // If the vertex u and the iterators ei and ei_end are thought of as the | |
113 | // context of the algorithm, each push and pop from the stack could | |
114 | // be thought of as a context shift. | |
115 | // Each pass through "while (ei != ei_end)" may refer to the out-edges of | |
116 | // an entirely different vertex, because the context of the algorithm | |
117 | // shifts every time a white adjacent vertex is discovered. | |
118 | // The corresponding context shift back from the adjacent vertex occurs | |
119 | // after all of its out-edges have been examined. | |
120 | // | |
92f5a8d4 | 121 | // See https://lists.boost.org/Archives/boost/2003/06/49265.php for FAQ. |
7c673cae | 122 | |
f67539c2 TL |
123 | template < class IncidenceGraph, class DFSVisitor, class ColorMap, |
124 | class TerminatorFunc > | |
125 | void depth_first_visit_impl(const IncidenceGraph& g, | |
126 | typename graph_traits< IncidenceGraph >::vertex_descriptor u, | |
127 | DFSVisitor& vis, ColorMap color, TerminatorFunc func = TerminatorFunc()) | |
7c673cae | 128 | { |
f67539c2 TL |
129 | BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< IncidenceGraph >)); |
130 | BOOST_CONCEPT_ASSERT((DFSVisitorConcept< DFSVisitor, IncidenceGraph >)); | |
131 | typedef | |
132 | typename graph_traits< IncidenceGraph >::vertex_descriptor Vertex; | |
133 | typedef typename graph_traits< IncidenceGraph >::edge_descriptor Edge; | |
134 | BOOST_CONCEPT_ASSERT((ReadWritePropertyMapConcept< ColorMap, Vertex >)); | |
135 | typedef typename property_traits< ColorMap >::value_type ColorValue; | |
136 | BOOST_CONCEPT_ASSERT((ColorValueConcept< ColorValue >)); | |
137 | typedef color_traits< ColorValue > Color; | |
138 | typedef typename graph_traits< IncidenceGraph >::out_edge_iterator Iter; | |
139 | typedef std::pair< Vertex, | |
140 | std::pair< boost::optional< Edge >, std::pair< Iter, Iter > > > | |
141 | VertexInfo; | |
142 | ||
143 | boost::optional< Edge > src_e; | |
144 | Iter ei, ei_end; | |
145 | std::vector< VertexInfo > stack; | |
146 | ||
147 | // Possible optimization for vector | |
148 | // stack.reserve(num_vertices(g)); | |
149 | ||
150 | put(color, u, Color::gray()); | |
151 | vis.discover_vertex(u, g); | |
152 | boost::tie(ei, ei_end) = out_edges(u, g); | |
153 | if (func(u, g)) | |
154 | { | |
155 | // If this vertex terminates the search, we push empty range | |
156 | stack.push_back(std::make_pair(u, | |
157 | std::make_pair(boost::optional< Edge >(), | |
158 | std::make_pair(ei_end, ei_end)))); | |
159 | } | |
160 | else | |
161 | { | |
162 | stack.push_back(std::make_pair(u, | |
163 | std::make_pair( | |
164 | boost::optional< Edge >(), std::make_pair(ei, ei_end)))); | |
165 | } | |
166 | while (!stack.empty()) | |
167 | { | |
168 | VertexInfo& back = stack.back(); | |
169 | u = back.first; | |
170 | src_e = back.second.first; | |
171 | boost::tie(ei, ei_end) = back.second.second; | |
172 | stack.pop_back(); | |
173 | // finish_edge has to be called here, not after the | |
174 | // loop. Think of the pop as the return from a recursive call. | |
175 | if (src_e) | |
176 | { | |
177 | call_finish_edge(vis, src_e.get(), g); | |
7c673cae | 178 | } |
f67539c2 TL |
179 | while (ei != ei_end) |
180 | { | |
181 | Vertex v = target(*ei, g); | |
182 | vis.examine_edge(*ei, g); | |
183 | ColorValue v_color = get(color, v); | |
184 | if (v_color == Color::white()) | |
185 | { | |
186 | vis.tree_edge(*ei, g); | |
187 | src_e = *ei; | |
188 | stack.push_back(std::make_pair(u, | |
189 | std::make_pair(src_e, std::make_pair(++ei, ei_end)))); | |
190 | u = v; | |
191 | put(color, u, Color::gray()); | |
192 | vis.discover_vertex(u, g); | |
193 | boost::tie(ei, ei_end) = out_edges(u, g); | |
194 | if (func(u, g)) | |
195 | { | |
196 | ei = ei_end; | |
197 | } | |
198 | } | |
199 | else | |
200 | { | |
201 | if (v_color == Color::gray()) | |
202 | { | |
203 | vis.back_edge(*ei, g); | |
204 | } | |
205 | else | |
206 | { | |
207 | vis.forward_or_cross_edge(*ei, g); | |
208 | } | |
209 | call_finish_edge(vis, *ei, g); | |
210 | ++ei; | |
211 | } | |
7c673cae | 212 | } |
f67539c2 TL |
213 | put(color, u, Color::black()); |
214 | vis.finish_vertex(u, g); | |
7c673cae | 215 | } |
7c673cae FG |
216 | } |
217 | ||
218 | #else // BOOST_RECURSIVE_DFS is defined | |
219 | ||
f67539c2 TL |
220 | template < class IncidenceGraph, class DFSVisitor, class ColorMap, |
221 | class TerminatorFunc > | |
222 | void depth_first_visit_impl(const IncidenceGraph& g, | |
223 | typename graph_traits< IncidenceGraph >::vertex_descriptor u, | |
224 | DFSVisitor& vis, // pass-by-reference here, important! | |
225 | ColorMap color, TerminatorFunc func) | |
7c673cae | 226 | { |
f67539c2 TL |
227 | BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< IncidenceGraph >)); |
228 | BOOST_CONCEPT_ASSERT((DFSVisitorConcept< DFSVisitor, IncidenceGraph >)); | |
229 | typedef | |
230 | typename graph_traits< IncidenceGraph >::vertex_descriptor Vertex; | |
231 | BOOST_CONCEPT_ASSERT((ReadWritePropertyMapConcept< ColorMap, Vertex >)); | |
232 | typedef typename property_traits< ColorMap >::value_type ColorValue; | |
233 | BOOST_CONCEPT_ASSERT((ColorValueConcept< ColorValue >)); | |
234 | typedef color_traits< ColorValue > Color; | |
235 | typename graph_traits< IncidenceGraph >::out_edge_iterator ei, ei_end; | |
236 | ||
237 | put(color, u, Color::gray()); | |
238 | vis.discover_vertex(u, g); | |
239 | ||
240 | if (!func(u, g)) | |
241 | for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) | |
242 | { | |
243 | Vertex v = target(*ei, g); | |
244 | vis.examine_edge(*ei, g); | |
245 | ColorValue v_color = get(color, v); | |
246 | if (v_color == Color::white()) | |
247 | { | |
248 | vis.tree_edge(*ei, g); | |
249 | depth_first_visit_impl(g, v, vis, color, func); | |
250 | } | |
251 | else if (v_color == Color::gray()) | |
252 | vis.back_edge(*ei, g); | |
253 | else | |
254 | vis.forward_or_cross_edge(*ei, g); | |
255 | call_finish_edge(vis, *ei, g); | |
256 | } | |
257 | put(color, u, Color::black()); | |
258 | vis.finish_vertex(u, g); | |
7c673cae FG |
259 | } |
260 | ||
261 | #endif | |
262 | ||
f67539c2 TL |
263 | } // namespace detail |
264 | ||
265 | template < class VertexListGraph, class DFSVisitor, class ColorMap > | |
266 | void depth_first_search(const VertexListGraph& g, DFSVisitor vis, | |
267 | ColorMap color, | |
268 | typename graph_traits< VertexListGraph >::vertex_descriptor start_vertex) | |
269 | { | |
270 | typedef typename graph_traits< VertexListGraph >::vertex_descriptor Vertex; | |
271 | BOOST_CONCEPT_ASSERT((DFSVisitorConcept< DFSVisitor, VertexListGraph >)); | |
272 | typedef typename property_traits< ColorMap >::value_type ColorValue; | |
273 | typedef color_traits< ColorValue > Color; | |
274 | ||
275 | typename graph_traits< VertexListGraph >::vertex_iterator ui, ui_end; | |
276 | for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) | |
277 | { | |
278 | Vertex u = implicit_cast< Vertex >(*ui); | |
279 | put(color, u, Color::white()); | |
280 | vis.initialize_vertex(u, g); | |
7c673cae FG |
281 | } |
282 | ||
f67539c2 TL |
283 | if (start_vertex != detail::get_default_starting_vertex(g)) |
284 | { | |
285 | vis.start_vertex(start_vertex, g); | |
286 | detail::depth_first_visit_impl( | |
287 | g, start_vertex, vis, color, detail::nontruth2()); | |
7c673cae FG |
288 | } |
289 | ||
f67539c2 TL |
290 | for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) |
291 | { | |
292 | Vertex u = implicit_cast< Vertex >(*ui); | |
293 | ColorValue u_color = get(color, u); | |
294 | if (u_color == Color::white()) | |
295 | { | |
296 | vis.start_vertex(u, g); | |
297 | detail::depth_first_visit_impl( | |
298 | g, u, vis, color, detail::nontruth2()); | |
299 | } | |
7c673cae | 300 | } |
f67539c2 TL |
301 | } |
302 | ||
303 | template < class VertexListGraph, class DFSVisitor, class ColorMap > | |
304 | void depth_first_search( | |
305 | const VertexListGraph& g, DFSVisitor vis, ColorMap color) | |
306 | { | |
307 | typedef typename boost::graph_traits< VertexListGraph >::vertex_iterator vi; | |
308 | std::pair< vi, vi > verts = vertices(g); | |
7c673cae | 309 | if (verts.first == verts.second) |
f67539c2 | 310 | return; |
7c673cae FG |
311 | |
312 | depth_first_search(g, vis, color, detail::get_default_starting_vertex(g)); | |
f67539c2 | 313 | } |
7c673cae | 314 | |
f67539c2 TL |
315 | template < class Visitors = null_visitor > class dfs_visitor |
316 | { | |
317 | public: | |
318 | dfs_visitor() {} | |
319 | dfs_visitor(Visitors vis) : m_vis(vis) {} | |
7c673cae | 320 | |
f67539c2 TL |
321 | template < class Vertex, class Graph > |
322 | void initialize_vertex(Vertex u, const Graph& g) | |
323 | { | |
324 | invoke_visitors(m_vis, u, g, ::boost::on_initialize_vertex()); | |
7c673cae | 325 | } |
f67539c2 TL |
326 | template < class Vertex, class Graph > |
327 | void start_vertex(Vertex u, const Graph& g) | |
328 | { | |
329 | invoke_visitors(m_vis, u, g, ::boost::on_start_vertex()); | |
7c673cae | 330 | } |
f67539c2 TL |
331 | template < class Vertex, class Graph > |
332 | void discover_vertex(Vertex u, const Graph& g) | |
333 | { | |
334 | invoke_visitors(m_vis, u, g, ::boost::on_discover_vertex()); | |
7c673cae | 335 | } |
f67539c2 TL |
336 | template < class Edge, class Graph > |
337 | void examine_edge(Edge u, const Graph& g) | |
338 | { | |
339 | invoke_visitors(m_vis, u, g, ::boost::on_examine_edge()); | |
7c673cae | 340 | } |
f67539c2 TL |
341 | template < class Edge, class Graph > void tree_edge(Edge u, const Graph& g) |
342 | { | |
343 | invoke_visitors(m_vis, u, g, ::boost::on_tree_edge()); | |
7c673cae | 344 | } |
f67539c2 TL |
345 | template < class Edge, class Graph > void back_edge(Edge u, const Graph& g) |
346 | { | |
347 | invoke_visitors(m_vis, u, g, ::boost::on_back_edge()); | |
7c673cae | 348 | } |
f67539c2 TL |
349 | template < class Edge, class Graph > |
350 | void forward_or_cross_edge(Edge u, const Graph& g) | |
351 | { | |
352 | invoke_visitors(m_vis, u, g, ::boost::on_forward_or_cross_edge()); | |
7c673cae | 353 | } |
f67539c2 TL |
354 | template < class Edge, class Graph > |
355 | void finish_edge(Edge u, const Graph& g) | |
356 | { | |
357 | invoke_visitors(m_vis, u, g, ::boost::on_finish_edge()); | |
7c673cae | 358 | } |
f67539c2 TL |
359 | template < class Vertex, class Graph > |
360 | void finish_vertex(Vertex u, const Graph& g) | |
361 | { | |
362 | invoke_visitors(m_vis, u, g, ::boost::on_finish_vertex()); | |
7c673cae FG |
363 | } |
364 | ||
f67539c2 TL |
365 | BOOST_GRAPH_EVENT_STUB(on_initialize_vertex, dfs) |
366 | BOOST_GRAPH_EVENT_STUB(on_start_vertex, dfs) | |
367 | BOOST_GRAPH_EVENT_STUB(on_discover_vertex, dfs) | |
368 | BOOST_GRAPH_EVENT_STUB(on_examine_edge, dfs) | |
369 | BOOST_GRAPH_EVENT_STUB(on_tree_edge, dfs) | |
370 | BOOST_GRAPH_EVENT_STUB(on_back_edge, dfs) | |
371 | BOOST_GRAPH_EVENT_STUB(on_forward_or_cross_edge, dfs) | |
372 | BOOST_GRAPH_EVENT_STUB(on_finish_edge, dfs) | |
373 | BOOST_GRAPH_EVENT_STUB(on_finish_vertex, dfs) | |
374 | ||
375 | protected: | |
7c673cae | 376 | Visitors m_vis; |
f67539c2 TL |
377 | }; |
378 | template < class Visitors > | |
379 | dfs_visitor< Visitors > make_dfs_visitor(Visitors vis) | |
380 | { | |
381 | return dfs_visitor< Visitors >(vis); | |
382 | } | |
383 | typedef dfs_visitor<> default_dfs_visitor; | |
384 | ||
385 | // Boost.Parameter named parameter variant | |
386 | namespace graph | |
387 | { | |
388 | namespace detail | |
389 | { | |
390 | template < typename Graph > struct depth_first_search_impl | |
391 | { | |
392 | typedef void result_type; | |
393 | template < typename ArgPack > | |
394 | void operator()(const Graph& g, const ArgPack& arg_pack) const | |
395 | { | |
396 | using namespace boost::graph::keywords; | |
397 | boost::depth_first_search(g, | |
398 | arg_pack[_visitor | make_dfs_visitor(null_visitor())], | |
399 | boost::detail::make_color_map_from_arg_pack(g, arg_pack), | |
400 | arg_pack[_root_vertex | |
401 | || boost::detail::get_default_starting_vertex_t< | |
402 | Graph >(g)]); | |
403 | } | |
404 | }; | |
7c673cae FG |
405 | } |
406 | BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(depth_first_search, 1, 4) | |
f67539c2 | 407 | } |
7c673cae | 408 | |
f67539c2 | 409 | BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(depth_first_search, 1) |
7c673cae | 410 | |
f67539c2 TL |
411 | template < class IncidenceGraph, class DFSVisitor, class ColorMap > |
412 | void depth_first_visit(const IncidenceGraph& g, | |
413 | typename graph_traits< IncidenceGraph >::vertex_descriptor u, | |
414 | DFSVisitor vis, ColorMap color) | |
415 | { | |
7c673cae FG |
416 | vis.start_vertex(u, g); |
417 | detail::depth_first_visit_impl(g, u, vis, color, detail::nontruth2()); | |
f67539c2 TL |
418 | } |
419 | ||
420 | template < class IncidenceGraph, class DFSVisitor, class ColorMap, | |
421 | class TerminatorFunc > | |
422 | void depth_first_visit(const IncidenceGraph& g, | |
423 | typename graph_traits< IncidenceGraph >::vertex_descriptor u, | |
424 | DFSVisitor vis, ColorMap color, TerminatorFunc func = TerminatorFunc()) | |
425 | { | |
7c673cae FG |
426 | vis.start_vertex(u, g); |
427 | detail::depth_first_visit_impl(g, u, vis, color, func); | |
f67539c2 | 428 | } |
7c673cae FG |
429 | } // namespace boost |
430 | ||
1e59de90 | 431 | #include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/depth_first_search.hpp>) |
7c673cae FG |
432 | |
433 | #endif |