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