Line data Source code
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/graph/detail/mpi_include.hpp>
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 0 : 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 0 : static void call_finish_edge(Vis& vis, E e, const G& g) {
69 0 : 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 0 : static void call_finish_edge(Vis&, E, const G&) {}
76 : };
77 :
78 : template <typename E, typename G, typename Vis>
79 0 : 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 0 : 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 : //
106 : // See https://lists.boost.org/Archives/boost/2003/06/49265.php for FAQ.
107 :
108 : template <class IncidenceGraph, class DFSVisitor, class ColorMap,
109 : class TerminatorFunc>
110 0 : 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 0 : boost::optional<Edge> src_e;
128 0 : Iter ei, ei_end;
129 0 : std::vector<VertexInfo> stack;
130 :
131 : // Possible optimization for vector
132 : //stack.reserve(num_vertices(g));
133 :
134 0 : put(color, u, Color::gray());
135 0 : vis.discover_vertex(u, g);
136 0 : boost::tie(ei, ei_end) = out_edges(u, g);
137 0 : 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 0 : stack.push_back(std::make_pair(u, std::make_pair(boost::optional<Edge>(), std::make_pair(ei, ei_end))));
142 : }
143 0 : while (!stack.empty()) {
144 0 : VertexInfo& back = stack.back();
145 0 : u = back.first;
146 0 : src_e = back.second.first;
147 0 : boost::tie(ei, ei_end) = back.second.second;
148 0 : 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 0 : if (src_e) {
152 0 : call_finish_edge(vis, src_e.get(), g);
153 : }
154 0 : while (ei != ei_end) {
155 0 : Vertex v = target(*ei, g);
156 0 : vis.examine_edge(*ei, g);
157 0 : ColorValue v_color = get(color, v);
158 0 : if (v_color == Color::white()) {
159 0 : vis.tree_edge(*ei, g);
160 0 : src_e = *ei;
161 0 : stack.push_back(std::make_pair(u, std::make_pair(src_e, std::make_pair(++ei, ei_end))));
162 0 : u = v;
163 0 : put(color, u, Color::gray());
164 0 : vis.discover_vertex(u, g);
165 0 : boost::tie(ei, ei_end) = out_edges(u, g);
166 0 : if (func(u, g)) {
167 : ei = ei_end;
168 : }
169 : } else {
170 0 : if (v_color == Color::gray()) {
171 0 : vis.back_edge(*ei, g);
172 : } else {
173 0 : vis.forward_or_cross_edge(*ei, g);
174 : }
175 0 : call_finish_edge(vis, *ei, g);
176 0 : ++ei;
177 : }
178 : }
179 0 : put(color, u, Color::black());
180 0 : vis.finish_vertex(u, g);
181 : }
182 0 : }
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 0 : 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 0 : typename graph_traits<VertexListGraph>::vertex_iterator ui, ui_end;
233 0 : for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
234 0 : Vertex u = implicit_cast<Vertex>(*ui);
235 0 : put(color, u, Color::white()); vis.initialize_vertex(u, g);
236 : }
237 :
238 0 : if (start_vertex != detail::get_default_starting_vertex(g)){ vis.start_vertex(start_vertex, g);
239 0 : detail::depth_first_visit_impl(g, start_vertex, vis, color,
240 : detail::nontruth2());
241 : }
242 :
243 0 : for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
244 0 : Vertex u = implicit_cast<Vertex>(*ui);
245 0 : ColorValue u_color = get(color, u);
246 0 : if (u_color == Color::white()) { vis.start_vertex(u, g);
247 0 : detail::depth_first_visit_impl(g, u, vis, color, detail::nontruth2());
248 : }
249 : }
250 0 : }
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 0 : dfs_visitor() { }
268 0 : dfs_visitor(Visitors vis) : m_vis(vis) { }
269 :
270 : template <class Vertex, class Graph>
271 0 : void initialize_vertex(Vertex u, const Graph& g) {
272 0 : invoke_visitors(m_vis, u, g, ::boost::on_initialize_vertex());
273 : }
274 : template <class Vertex, class Graph>
275 0 : void start_vertex(Vertex u, const Graph& g) {
276 0 : invoke_visitors(m_vis, u, g, ::boost::on_start_vertex());
277 : }
278 : template <class Vertex, class Graph>
279 0 : void discover_vertex(Vertex u, const Graph& g) {
280 0 : invoke_visitors(m_vis, u, g, ::boost::on_discover_vertex());
281 : }
282 : template <class Edge, class Graph>
283 0 : void examine_edge(Edge u, const Graph& g) {
284 0 : invoke_visitors(m_vis, u, g, ::boost::on_examine_edge());
285 : }
286 : template <class Edge, class Graph>
287 0 : void tree_edge(Edge u, const Graph& g) {
288 0 : 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 0 : void forward_or_cross_edge(Edge u, const Graph& g) {
296 0 : invoke_visitors(m_vis, u, g, ::boost::on_forward_or_cross_edge());
297 : }
298 : template <class Edge, class Graph>
299 0 : void finish_edge(Edge u, const Graph& g) {
300 0 : invoke_visitors(m_vis, u, g, ::boost::on_finish_edge());
301 : }
302 : template <class Vertex, class Graph>
303 0 : 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 0 : make_dfs_visitor(Visitors vis) {
323 0 : 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 0 : void operator()(const Graph& g, const ArgPack& arg_pack) const {
335 : using namespace boost::graph::keywords;
336 0 : boost::depth_first_search(g,
337 0 : 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 0 : }
341 : };
342 : }
343 0 : BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(depth_first_search, 1, 4)
344 : }
345 :
346 0 : BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(depth_first_search, 1)
347 :
348 : template <class IncidenceGraph, class DFSVisitor, class ColorMap>
349 0 : void depth_first_visit
350 : (const IncidenceGraph& g,
351 : typename graph_traits<IncidenceGraph>::vertex_descriptor u,
352 : DFSVisitor vis, ColorMap color)
353 : {
354 0 : vis.start_vertex(u, g);
355 0 : detail::depth_first_visit_impl(g, u, vis, color, detail::nontruth2());
356 0 : }
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 :
370 : #include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/depth_first_search.hpp>)
371 :
372 : #endif
|
