source: NonGTP/Boost/boost/graph/neighbor_bfs.hpp @ 857

Revision 857, 11.3 KB checked in by igarcia, 19 years ago (diff)
Line 
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
27namespace 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
Note: See TracBrowser for help on using the repository browser.