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