Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / depth_first_search.hpp
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
23 #include <boost/ref.hpp>
24 #include <boost/implicit_cast.hpp>
25
26 #include <vector>
27 #include <utility>
28
29 namespace boost {
30
31   template <class Visitor, class Graph>
32   class DFSVisitorConcept {
33   public:
34     void constraints() {
35       function_requires< CopyConstructibleConcept<Visitor> >();
36       vis.initialize_vertex(u, g);
37       vis.start_vertex(u, g);
38       vis.discover_vertex(u, g);
39       vis.examine_edge(e, g);
40       vis.tree_edge(e, g);
41       vis.back_edge(e, g);
42       vis.forward_or_cross_edge(e, g);
43       vis.finish_vertex(u, g);
44     }
45   private:
46     Visitor vis;
47     Graph g;
48     typename graph_traits<Graph>::vertex_descriptor u;
49     typename graph_traits<Graph>::edge_descriptor e;
50   };
51
52   namespace detail {
53
54     struct nontruth2 {
55       template<class T, class T2>
56       bool operator()(const T&, const T2&) const { return false; }
57     };
58
59
60 // Define BOOST_RECURSIVE_DFS to use older, recursive version.
61 // It is retained for a while in order to perform performance
62 // comparison.
63 #ifndef BOOST_RECURSIVE_DFS
64
65     // If the vertex u and the iterators ei and ei_end are thought of as the
66     // context of the algorithm, each push and pop from the stack could
67     // be thought of as a context shift.
68     // Each pass through "while (ei != ei_end)" may refer to the out-edges of
69     // an entirely different vertex, because the context of the algorithm
70     // shifts every time a white adjacent vertex is discovered.
71     // The corresponding context shift back from the adjacent vertex occurs
72     // after all of its out-edges have been examined.
73     //
74     // See http://lists.boost.org/MailArchives/boost/msg48752.php for FAQ.
75
76     template <class IncidenceGraph, class DFSVisitor, class ColorMap,
77             class TerminatorFunc>
78     void depth_first_visit_impl
79       (const IncidenceGraph& g,
80        typename graph_traits<IncidenceGraph>::vertex_descriptor u,
81        DFSVisitor& vis,
82        ColorMap color, TerminatorFunc func = TerminatorFunc())
83     {
84       function_requires<IncidenceGraphConcept<IncidenceGraph> >();
85       function_requires<DFSVisitorConcept<DFSVisitor, IncidenceGraph> >();
86       typedef typename graph_traits<IncidenceGraph>::vertex_descriptor Vertex;
87       function_requires< ReadWritePropertyMapConcept<ColorMap, Vertex> >();
88       typedef typename property_traits<ColorMap>::value_type ColorValue;
89       function_requires< ColorValueConcept<ColorValue> >();
90       typedef color_traits<ColorValue> Color;
91       typedef typename graph_traits<IncidenceGraph>::out_edge_iterator Iter;
92       typedef std::pair<Vertex, std::pair<Iter, Iter> > VertexInfo;
93
94       Iter ei, ei_end;
95       std::vector<VertexInfo> stack;
96
97       // Possible optimization for vector
98       //stack.reserve(num_vertices(g));
99
100       typedef typename unwrap_reference<TerminatorFunc>::type TF;
101
102       put(color, u, Color::gray());
103       vis.discover_vertex(u, g);
104       tie(ei, ei_end) = out_edges(u, g);
105       // Variable is needed to workaround a borland bug.
106       TF& fn = static_cast<TF&>(func);
107       if (fn(u, g)) {
108           // If this vertex terminates the search, we push empty range
109           stack.push_back(std::make_pair(u, std::make_pair(ei_end, ei_end)));
110       } else {
111           stack.push_back(std::make_pair(u, std::make_pair(ei, ei_end)));
112       }
113       while (!stack.empty()) {
114         VertexInfo& back = stack.back();
115         u = back.first;
116         tie(ei, ei_end) = back.second;
117         stack.pop_back();
118         while (ei != ei_end) {
119           Vertex v = target(*ei, g);
120           vis.examine_edge(*ei, g);
121           ColorValue v_color = get(color, v);
122           if (v_color == Color::white()) {
123             vis.tree_edge(*ei, g);
124             stack.push_back(std::make_pair(u, std::make_pair(++ei, ei_end)));
125             u = v;
126             put(color, u, Color::gray());
127             vis.discover_vertex(u, g);
128             tie(ei, ei_end) = out_edges(u, g);
129             if (fn(u, g)) {
130                 ei = ei_end;
131             }
132           } else if (v_color == Color::gray()) {
133             vis.back_edge(*ei, g);
134             ++ei;
135           } else {
136             vis.forward_or_cross_edge(*ei, g);
137             ++ei;
138           }
139         }
140         put(color, u, Color::black());
141         vis.finish_vertex(u, g);
142       }
143     }
144
145 #else // BOOST_RECURSIVE_DFS is defined
146
147     template <class IncidenceGraph, class DFSVisitor, class ColorMap,
148               class TerminatorFunc>
149     void depth_first_visit_impl
150       (const IncidenceGraph& g,
151        typename graph_traits<IncidenceGraph>::vertex_descriptor u,
152        DFSVisitor& vis,  // pass-by-reference here, important!
153        ColorMap color, TerminatorFunc func)
154     {
155       function_requires<IncidenceGraphConcept<IncidenceGraph> >();
156       function_requires<DFSVisitorConcept<DFSVisitor, IncidenceGraph> >();
157       typedef typename graph_traits<IncidenceGraph>::vertex_descriptor Vertex;
158       function_requires< ReadWritePropertyMapConcept<ColorMap, Vertex> >();
159       typedef typename property_traits<ColorMap>::value_type ColorValue;
160       function_requires< ColorValueConcept<ColorValue> >();
161       typedef color_traits<ColorValue> Color;
162       typename graph_traits<IncidenceGraph>::out_edge_iterator ei, ei_end;
163
164       put(color, u, Color::gray());          vis.discover_vertex(u, g);
165
166       typedef typename unwrap_reference<TerminatorFunc>::type TF;
167       // Variable is needed to workaround a borland bug.
168       TF& fn = static_cast<TF&>(func);
169       if (!fn(u, g))
170         for (tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {
171           Vertex v = target(*ei, g);           vis.examine_edge(*ei, g);
172           ColorValue v_color = get(color, v);
173           if (v_color == Color::white()) {     vis.tree_edge(*ei, g);
174           depth_first_visit_impl(g, v, vis, color, func);
175           } else if (v_color == Color::gray()) vis.back_edge(*ei, g);
176           else                                 vis.forward_or_cross_edge(*ei, g);
177         }
178       put(color, u, Color::black());         vis.finish_vertex(u, g);
179     }
180
181 #endif
182
183   } // namespace detail
184
185   template <class VertexListGraph, class DFSVisitor, class ColorMap>
186   void
187   depth_first_search(const VertexListGraph& g, DFSVisitor vis, ColorMap color,
188                      typename graph_traits<VertexListGraph>::vertex_descriptor start_vertex)
189   {
190     typedef typename graph_traits<VertexListGraph>::vertex_descriptor Vertex;
191     function_requires<DFSVisitorConcept<DFSVisitor, VertexListGraph> >();
192     typedef typename property_traits<ColorMap>::value_type ColorValue;
193     typedef color_traits<ColorValue> Color;
194
195     typename graph_traits<VertexListGraph>::vertex_iterator ui, ui_end;
196     for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
197       put(color, *ui, Color::white());       vis.initialize_vertex(*ui, g);
198     }
199
200     if (start_vertex != implicit_cast<Vertex>(*vertices(g).first)){ vis.start_vertex(start_vertex, g);
201       detail::depth_first_visit_impl(g, start_vertex, vis, color,
202                                      detail::nontruth2());
203     }
204
205     for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
206       ColorValue u_color = get(color, *ui);
207       if (u_color == Color::white()) {       vis.start_vertex(*ui, g);
208         detail::depth_first_visit_impl(g, *ui, vis, color, detail::nontruth2());
209       }
210     }
211   }
212
213   template <class VertexListGraph, class DFSVisitor, class ColorMap>
214   void
215   depth_first_search(const VertexListGraph& g, DFSVisitor vis, ColorMap color)
216   {
217     depth_first_search(g, vis, color, *vertices(g).first);
218   }
219
220   namespace detail {
221     template <class ColorMap>
222     struct dfs_dispatch {
223
224       template <class VertexListGraph, class Vertex, class DFSVisitor,
225                 class P, class T, class R>
226       static void
227       apply(const VertexListGraph& g, DFSVisitor vis, Vertex start_vertex,
228             const bgl_named_params<P, T, R>&,
229             ColorMap color)
230       {
231         depth_first_search(g, vis, color, start_vertex);
232       }
233     };
234
235     template <>
236     struct dfs_dispatch<detail::error_property_not_found> {
237       template <class VertexListGraph, class Vertex, class DFSVisitor,
238                 class P, class T, class R>
239       static void
240       apply(const VertexListGraph& g, DFSVisitor vis, Vertex start_vertex,
241             const bgl_named_params<P, T, R>& params,
242             detail::error_property_not_found)
243       {
244         std::vector<default_color_type> color_vec(num_vertices(g));
245         default_color_type c = white_color; // avoid warning about un-init
246         depth_first_search
247           (g, vis, make_iterator_property_map
248            (color_vec.begin(),
249             choose_const_pmap(get_param(params, vertex_index),
250                               g, vertex_index), c),
251            start_vertex);
252       }
253     };
254   } // namespace detail
255
256
257   template <class Visitors = null_visitor>
258   class dfs_visitor {
259   public:
260     dfs_visitor() { }
261     dfs_visitor(Visitors vis) : m_vis(vis) { }
262
263     template <class Vertex, class Graph>
264     void initialize_vertex(Vertex u, const Graph& g) {
265       invoke_visitors(m_vis, u, g, ::boost::on_initialize_vertex());
266     }
267     template <class Vertex, class Graph>
268     void start_vertex(Vertex u, const Graph& g) {
269       invoke_visitors(m_vis, u, g, ::boost::on_start_vertex());
270     }
271     template <class Vertex, class Graph>
272     void discover_vertex(Vertex u, const Graph& g) {
273       invoke_visitors(m_vis, u, g, ::boost::on_discover_vertex());
274     }
275     template <class Edge, class Graph>
276     void examine_edge(Edge u, const Graph& g) {
277       invoke_visitors(m_vis, u, g, ::boost::on_examine_edge());
278     }
279     template <class Edge, class Graph>
280     void tree_edge(Edge u, const Graph& g) {
281       invoke_visitors(m_vis, u, g, ::boost::on_tree_edge());
282     }
283     template <class Edge, class Graph>
284     void back_edge(Edge u, const Graph& g) {
285       invoke_visitors(m_vis, u, g, ::boost::on_back_edge());
286     }
287     template <class Edge, class Graph>
288     void forward_or_cross_edge(Edge u, const Graph& g) {
289       invoke_visitors(m_vis, u, g, ::boost::on_forward_or_cross_edge());
290     }
291     template <class Vertex, class Graph>
292     void finish_vertex(Vertex u, const Graph& g) {
293       invoke_visitors(m_vis, u, g, ::boost::on_finish_vertex());
294     }
295
296     BOOST_GRAPH_EVENT_STUB(on_initialize_vertex,dfs)
297     BOOST_GRAPH_EVENT_STUB(on_start_vertex,dfs)
298     BOOST_GRAPH_EVENT_STUB(on_discover_vertex,dfs)
299     BOOST_GRAPH_EVENT_STUB(on_examine_edge,dfs)
300     BOOST_GRAPH_EVENT_STUB(on_tree_edge,dfs)
301     BOOST_GRAPH_EVENT_STUB(on_back_edge,dfs)
302     BOOST_GRAPH_EVENT_STUB(on_forward_or_cross_edge,dfs)
303     BOOST_GRAPH_EVENT_STUB(on_finish_vertex,dfs)
304
305   protected:
306     Visitors m_vis;
307   };
308   template <class Visitors>
309   dfs_visitor<Visitors>
310   make_dfs_visitor(Visitors vis) {
311     return dfs_visitor<Visitors>(vis);
312   }
313   typedef dfs_visitor<> default_dfs_visitor;
314
315
316   // Named Parameter Variant
317   template <class VertexListGraph, class P, class T, class R>
318   void
319   depth_first_search(const VertexListGraph& g,
320                      const bgl_named_params<P, T, R>& params)
321   {
322     typedef typename property_value< bgl_named_params<P, T, R>,
323       vertex_color_t>::type C;
324     detail::dfs_dispatch<C>::apply
325       (g,
326        choose_param(get_param(params, graph_visitor),
327                     make_dfs_visitor(null_visitor())),
328        choose_param(get_param(params, root_vertex_t()),
329                     *vertices(g).first),
330        params,
331        get_param(params, vertex_color)
332        );
333   }
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
356
357 } // namespace boost
358
359
360 #endif