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