Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / neighbor_bfs.hpp
1 //
2 //=======================================================================
3 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
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 #ifndef BOOST_GRAPH_NEIGHBOR_BREADTH_FIRST_SEARCH_HPP
12 #define BOOST_GRAPH_NEIGHBOR_BREADTH_FIRST_SEARCH_HPP
13
14 /*
15   Neighbor Breadth First Search
16   Like BFS, but traverses in-edges as well as out-edges.
17   (for directed graphs only. use normal BFS for undirected graphs)
18 */
19 #include <boost/config.hpp>
20 #include <vector>
21 #include <boost/pending/queue.hpp>
22 #include <boost/graph/graph_traits.hpp>
23 #include <boost/graph/graph_concepts.hpp>
24 #include <boost/graph/visitors.hpp>
25 #include <boost/graph/named_function_params.hpp>
26
27 namespace boost {
28
29   template <class Visitor, class Graph>
30   struct NeighborBFSVisitorConcept {
31     void constraints() {
32       function_requires< CopyConstructibleConcept<Visitor> >();
33       vis.initialize_vertex(u, g);
34       vis.discover_vertex(u, g);
35       vis.examine_vertex(u, g);
36       vis.examine_out_edge(e, g);
37       vis.examine_in_edge(e, g);
38       vis.tree_out_edge(e, g);
39       vis.tree_in_edge(e, g);
40       vis.non_tree_out_edge(e, g);
41       vis.non_tree_in_edge(e, g);
42       vis.gray_target(e, g);
43       vis.black_target(e, g);
44       vis.gray_source(e, g);
45       vis.black_source(e, g);
46       vis.finish_vertex(u, g);
47     }
48     Visitor vis;
49     Graph g;
50     typename graph_traits<Graph>::vertex_descriptor u;
51     typename graph_traits<Graph>::edge_descriptor e;
52   };
53
54   template <class Visitors = null_visitor>
55   class neighbor_bfs_visitor {
56   public:
57     neighbor_bfs_visitor(Visitors vis = Visitors()) : m_vis(vis) { }
58
59     template <class Vertex, class Graph>
60     void initialize_vertex(Vertex u, Graph& g) {
61       invoke_visitors(m_vis, u, g, on_initialize_vertex());      
62     }
63     template <class Vertex, class Graph>
64     void discover_vertex(Vertex u, Graph& g) {
65       invoke_visitors(m_vis, u, g, on_discover_vertex());      
66     }
67     template <class Vertex, class Graph>
68     void examine_vertex(Vertex u, Graph& g) {
69       invoke_visitors(m_vis, u, g, on_examine_vertex());
70     }
71     template <class Edge, class Graph>
72     void examine_out_edge(Edge e, Graph& g) {
73       invoke_visitors(m_vis, e, g, on_examine_edge());
74     }
75     template <class Edge, class Graph>
76     void tree_out_edge(Edge e, Graph& g) {
77       invoke_visitors(m_vis, e, g, on_tree_edge());      
78     }
79     template <class Edge, class Graph>
80     void non_tree_out_edge(Edge e, Graph& g) {
81       invoke_visitors(m_vis, e, g, on_non_tree_edge());
82     }
83     template <class Edge, class Graph>
84     void gray_target(Edge e, Graph& g) {
85       invoke_visitors(m_vis, e, g, on_gray_target());
86     }
87     template <class Edge, class Graph>
88     void black_target(Edge e, Graph& g) {
89       invoke_visitors(m_vis, e, g, on_black_target());
90     }
91     template <class Edge, class Graph>
92     void examine_in_edge(Edge e, Graph& g) {
93       invoke_visitors(m_vis, e, g, on_examine_edge());
94     }
95     template <class Edge, class Graph>
96     void tree_in_edge(Edge e, Graph& g) {
97       invoke_visitors(m_vis, e, g, on_tree_edge());      
98     }
99     template <class Edge, class Graph>
100     void non_tree_in_edge(Edge e, Graph& g) {
101       invoke_visitors(m_vis, e, g, on_non_tree_edge());
102     }
103     template <class Edge, class Graph>
104     void gray_source(Edge e, Graph& g) {
105       invoke_visitors(m_vis, e, g, on_gray_target());
106     }
107     template <class Edge, class Graph>
108     void black_source(Edge e, Graph& g) {
109       invoke_visitors(m_vis, e, g, on_black_target());
110     }
111     template <class Vertex, class Graph>
112     void finish_vertex(Vertex u, Graph& g) {
113       invoke_visitors(m_vis, u, g, on_finish_vertex());      
114     }
115   protected:
116     Visitors m_vis;
117   };
118
119   template <class Visitors>
120   neighbor_bfs_visitor<Visitors>
121   make_neighbor_bfs_visitor(Visitors vis) {
122     return neighbor_bfs_visitor<Visitors>(vis);
123   }
124
125   namespace detail {
126
127     template <class BidirectionalGraph, class Buffer, class BFSVisitor, 
128               class ColorMap>
129     void neighbor_bfs_impl
130       (const BidirectionalGraph& g, 
131        typename graph_traits<BidirectionalGraph>::vertex_descriptor s, 
132        Buffer& Q, BFSVisitor vis, ColorMap color)
133
134     {
135       function_requires< BidirectionalGraphConcept<BidirectionalGraph> >();
136       typedef graph_traits<BidirectionalGraph> GTraits;
137       typedef typename GTraits::vertex_descriptor Vertex;
138       typedef typename GTraits::edge_descriptor Edge;
139       function_requires< 
140         NeighborBFSVisitorConcept<BFSVisitor, BidirectionalGraph> >();
141       function_requires< ReadWritePropertyMapConcept<ColorMap, Vertex> >();
142       typedef typename property_traits<ColorMap>::value_type ColorValue;
143       typedef color_traits<ColorValue> Color;
144       
145       put(color, s, Color::gray());
146       vis.discover_vertex(s, g);
147       Q.push(s);
148       while (! Q.empty()) {
149         Vertex u = Q.top();
150         Q.pop(); // pop before push to avoid problem if Q is priority_queue.
151         vis.examine_vertex(u, g);
152
153         typename GTraits::out_edge_iterator ei, ei_end;
154         for (tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {
155           Edge e = *ei;
156           vis.examine_out_edge(e, g);
157           Vertex v = target(e, g);
158           ColorValue v_color = get(color, v);
159           if (v_color == Color::white()) {
160             vis.tree_out_edge(e, g);
161             put(color, v, Color::gray());
162             vis.discover_vertex(v, g);
163             Q.push(v);
164           } else {
165             vis.non_tree_out_edge(e, g);
166             if (v_color == Color::gray())
167               vis.gray_target(e, g);
168             else
169               vis.black_target(e, g);
170           }
171         } // for out-edges
172
173         typename GTraits::in_edge_iterator in_ei, in_ei_end;
174         for (tie(in_ei, in_ei_end) = in_edges(u, g); 
175              in_ei != in_ei_end; ++in_ei) {
176           Edge e = *in_ei;
177           vis.examine_in_edge(e, g);
178           Vertex v = source(e, g);
179           ColorValue v_color = get(color, v);
180           if (v_color == Color::white()) {
181             vis.tree_in_edge(e, g);
182             put(color, v, Color::gray());
183             vis.discover_vertex(v, g);
184             Q.push(v);
185           } else {
186             vis.non_tree_in_edge(e, g);
187             if (v_color == Color::gray())
188               vis.gray_source(e, g);
189             else
190               vis.black_source(e, g);
191           }
192         } // for in-edges
193
194         put(color, u, Color::black());
195         vis.finish_vertex(u, g);
196       } // while
197     }
198
199     
200     template <class VertexListGraph, class ColorMap, class BFSVisitor,
201       class P, class T, class R>
202     void neighbor_bfs_helper
203       (VertexListGraph& g,
204        typename graph_traits<VertexListGraph>::vertex_descriptor s,
205        ColorMap color, 
206        BFSVisitor vis,
207        const bgl_named_params<P, T, R>& params)
208     {
209       typedef graph_traits<VertexListGraph> Traits;
210       // Buffer default
211       typedef typename Traits::vertex_descriptor Vertex;
212       typedef boost::queue<Vertex> queue_t;
213       queue_t Q;
214       detail::wrap_ref<queue_t> Qref(Q);
215       // Initialization
216       typedef typename property_traits<ColorMap>::value_type ColorValue;
217       typedef color_traits<ColorValue> Color;
218       typename boost::graph_traits<VertexListGraph>::vertex_iterator i, i_end;
219       for (tie(i, i_end) = vertices(g); i != i_end; ++i) {
220         put(color, *i, Color::white());
221         vis.initialize_vertex(*i, g);
222       }
223       neighbor_bfs_impl
224         (g, s, 
225          choose_param(get_param(params, buffer_param_t()), Qref).ref,
226          vis, color);
227     }
228
229     //-------------------------------------------------------------------------
230     // Choose between default color and color parameters. Using
231     // function dispatching so that we don't require vertex index if
232     // the color default is not being used.
233
234     template <class ColorMap>
235     struct neighbor_bfs_dispatch {
236       template <class VertexListGraph, class P, class T, class R>
237       static void apply
238       (VertexListGraph& g,
239        typename graph_traits<VertexListGraph>::vertex_descriptor s,
240        const bgl_named_params<P, T, R>& params,
241        ColorMap color)
242       {
243         neighbor_bfs_helper
244           (g, s, color,
245            choose_param(get_param(params, graph_visitor),
246                         make_neighbor_bfs_visitor(null_visitor())),
247            params);
248       }
249     };
250
251     template <>
252     struct neighbor_bfs_dispatch<detail::error_property_not_found> {
253       template <class VertexListGraph, class P, class T, class R>
254       static void apply
255       (VertexListGraph& g,
256        typename graph_traits<VertexListGraph>::vertex_descriptor s,
257        const bgl_named_params<P, T, R>& params,
258        detail::error_property_not_found)
259       {
260         std::vector<default_color_type> color_vec(num_vertices(g));
261         null_visitor null_vis;
262         
263         neighbor_bfs_helper
264           (g, s, 
265            make_iterator_property_map
266            (color_vec.begin(), 
267             choose_const_pmap(get_param(params, vertex_index), 
268                               g, vertex_index), color_vec[0]),
269            choose_param(get_param(params, graph_visitor),
270                         make_neighbor_bfs_visitor(null_vis)),
271            params);
272       }
273     };
274
275   } // namespace detail
276
277
278   // Named Parameter Variant
279   template <class VertexListGraph, class P, class T, class R>
280   void neighbor_breadth_first_search
281     (const VertexListGraph& g,
282      typename graph_traits<VertexListGraph>::vertex_descriptor s,
283      const bgl_named_params<P, T, R>& params)
284   {
285     // The graph is passed by *const* reference so that graph adaptors
286     // (temporaries) can be passed into this function. However, the
287     // graph is not really const since we may write to property maps
288     // of the graph.
289     VertexListGraph& ng = const_cast<VertexListGraph&>(g);
290     typedef typename property_value< bgl_named_params<P,T,R>, 
291       vertex_color_t>::type C;
292     detail::neighbor_bfs_dispatch<C>::apply(ng, s, params, 
293                                             get_param(params, vertex_color));
294   }
295
296
297   // This version does not initialize colors, user has to.
298
299   template <class IncidenceGraph, class P, class T, class R>
300   void neighbor_breadth_first_visit
301     (IncidenceGraph& g,
302      typename graph_traits<IncidenceGraph>::vertex_descriptor s,
303      const bgl_named_params<P, T, R>& params)
304   {
305     typedef graph_traits<IncidenceGraph> Traits;
306     // Buffer default
307     typedef boost::queue<typename Traits::vertex_descriptor> queue_t;
308     queue_t Q;
309     detail::wrap_ref<queue_t> Qref(Q);
310
311     detail::neighbor_bfs_impl
312       (g, s,
313        choose_param(get_param(params, buffer_param_t()), Qref).ref,
314        choose_param(get_param(params, graph_visitor),
315                     make_neighbor_bfs_visitor(null_visitor())),
316        choose_pmap(get_param(params, vertex_color), g, vertex_color)
317        );
318   }
319
320 } // namespace boost
321
322 #endif // BOOST_GRAPH_NEIGHBOR_BREADTH_FIRST_SEARCH_HPP
323