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

Revision 857, 10.4 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_BREADTH_FIRST_SEARCH_HPP
12#define BOOST_GRAPH_BREADTH_FIRST_SEARCH_HPP
13
14/*
15  Breadth First Search Algorithm (Cormen, Leiserson, and Rivest p. 470)
16*/
17#include <boost/config.hpp>
18#include <vector>
19#include <boost/pending/queue.hpp>
20#include <boost/graph/graph_traits.hpp>
21#include <boost/graph/graph_concepts.hpp>
22#include <boost/graph/visitors.hpp>
23#include <boost/graph/named_function_params.hpp>
24
25namespace boost {
26
27  template <class Visitor, class Graph>
28  struct BFSVisitorConcept {
29    void constraints() {
30      function_requires< CopyConstructibleConcept<Visitor> >();
31      vis.initialize_vertex(u, g);
32      vis.discover_vertex(u, g);
33      vis.examine_vertex(u, g);
34      vis.examine_edge(e, g);
35      vis.tree_edge(e, g);
36      vis.non_tree_edge(e, g);
37      vis.gray_target(e, g);
38      vis.black_target(e, g);
39      vis.finish_vertex(u, g);
40    }
41    Visitor vis;
42    Graph g;
43    typename graph_traits<Graph>::vertex_descriptor u;
44    typename graph_traits<Graph>::edge_descriptor e;
45  };
46
47
48  template <class IncidenceGraph, class Buffer, class BFSVisitor,
49            class ColorMap>
50  void breadth_first_visit
51    (const IncidenceGraph& g,
52     typename graph_traits<IncidenceGraph>::vertex_descriptor s,
53     Buffer& Q, BFSVisitor vis, ColorMap color)
54  {
55    function_requires< IncidenceGraphConcept<IncidenceGraph> >();
56    typedef graph_traits<IncidenceGraph> GTraits;
57    typedef typename GTraits::vertex_descriptor Vertex;
58    typedef typename GTraits::edge_descriptor Edge;
59    function_requires< BFSVisitorConcept<BFSVisitor, IncidenceGraph> >();
60    function_requires< ReadWritePropertyMapConcept<ColorMap, Vertex> >();
61    typedef typename property_traits<ColorMap>::value_type ColorValue;
62    typedef color_traits<ColorValue> Color;
63    typename GTraits::out_edge_iterator ei, ei_end;
64
65    put(color, s, Color::gray());             vis.discover_vertex(s, g);
66    Q.push(s);
67    while (! Q.empty()) {
68      Vertex u = Q.top(); Q.pop();            vis.examine_vertex(u, g);
69      for (tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {
70        Vertex v = target(*ei, g);            vis.examine_edge(*ei, g);
71        ColorValue v_color = get(color, v);
72        if (v_color == Color::white()) {      vis.tree_edge(*ei, g);
73          put(color, v, Color::gray());       vis.discover_vertex(v, g);
74          Q.push(v);
75        } else {                              vis.non_tree_edge(*ei, g);
76          if (v_color == Color::gray())       vis.gray_target(*ei, g);
77          else                                vis.black_target(*ei, g);
78        }
79      } // end for
80      put(color, u, Color::black());          vis.finish_vertex(u, g);
81    } // end while
82  } // breadth_first_visit
83
84
85  template <class VertexListGraph, class Buffer, class BFSVisitor,
86            class ColorMap>
87  void breadth_first_search
88    (const VertexListGraph& g,
89     typename graph_traits<VertexListGraph>::vertex_descriptor s,
90     Buffer& Q, BFSVisitor vis, ColorMap color)
91  {
92    // Initialization
93    typedef typename property_traits<ColorMap>::value_type ColorValue;
94    typedef color_traits<ColorValue> Color;
95    typename boost::graph_traits<VertexListGraph>::vertex_iterator i, i_end;
96    for (tie(i, i_end) = vertices(g); i != i_end; ++i) {
97      put(color, *i, Color::white());
98      vis.initialize_vertex(*i, g);
99    }
100    breadth_first_visit(g, s, Q, vis, color);
101  }
102
103
104  template <class Visitors = null_visitor>
105  class bfs_visitor {
106  public:
107    bfs_visitor() { }
108    bfs_visitor(Visitors vis) : m_vis(vis) { }
109
110    template <class Vertex, class Graph>
111    void initialize_vertex(Vertex u, Graph& g) {
112      invoke_visitors(m_vis, u, g, ::boost::on_initialize_vertex());
113    }
114    template <class Vertex, class Graph>
115    void discover_vertex(Vertex u, Graph& g) {
116      invoke_visitors(m_vis, u, g, ::boost::on_discover_vertex());
117    }
118    template <class Vertex, class Graph>
119    void examine_vertex(Vertex u, Graph& g) {
120      invoke_visitors(m_vis, u, g, ::boost::on_examine_vertex());
121    }
122    template <class Edge, class Graph>
123    void examine_edge(Edge e, Graph& g) {
124      invoke_visitors(m_vis, e, g, ::boost::on_examine_edge());
125    }
126    template <class Edge, class Graph>
127    void tree_edge(Edge e, Graph& g) {
128      invoke_visitors(m_vis, e, g, ::boost::on_tree_edge());
129    }
130    template <class Edge, class Graph>
131    void non_tree_edge(Edge e, Graph& g) {
132      invoke_visitors(m_vis, e, g, ::boost::on_non_tree_edge());
133    }
134    template <class Edge, class Graph>
135    void gray_target(Edge e, Graph& g) {
136      invoke_visitors(m_vis, e, g, ::boost::on_gray_target());
137    }
138    template <class Edge, class Graph>
139    void black_target(Edge e, Graph& g) {
140      invoke_visitors(m_vis, e, g, ::boost::on_black_target());
141    }
142    template <class Vertex, class Graph>
143    void finish_vertex(Vertex u, Graph& g) {
144      invoke_visitors(m_vis, u, g, ::boost::on_finish_vertex());
145    }
146
147    BOOST_GRAPH_EVENT_STUB(on_initialize_vertex,bfs)
148    BOOST_GRAPH_EVENT_STUB(on_discover_vertex,bfs)
149    BOOST_GRAPH_EVENT_STUB(on_examine_vertex,bfs)
150    BOOST_GRAPH_EVENT_STUB(on_examine_edge,bfs)
151    BOOST_GRAPH_EVENT_STUB(on_tree_edge,bfs)
152    BOOST_GRAPH_EVENT_STUB(on_non_tree_edge,bfs)
153    BOOST_GRAPH_EVENT_STUB(on_gray_target,bfs)
154    BOOST_GRAPH_EVENT_STUB(on_black_target,bfs)
155    BOOST_GRAPH_EVENT_STUB(on_finish_vertex,bfs)
156
157  protected:
158    Visitors m_vis;
159  };
160  template <class Visitors>
161  bfs_visitor<Visitors>
162  make_bfs_visitor(Visitors vis) {
163    return bfs_visitor<Visitors>(vis);
164  }
165  typedef bfs_visitor<> default_bfs_visitor;
166
167
168  namespace detail {
169
170    template <class VertexListGraph, class ColorMap, class BFSVisitor,
171      class P, class T, class R>
172    void bfs_helper
173      (VertexListGraph& g,
174       typename graph_traits<VertexListGraph>::vertex_descriptor s,
175       ColorMap color,
176       BFSVisitor vis,
177       const bgl_named_params<P, T, R>& params)
178    {
179      typedef graph_traits<VertexListGraph> Traits;
180      // Buffer default
181      typedef typename Traits::vertex_descriptor Vertex;
182      typedef boost::queue<Vertex> queue_t;
183      queue_t Q;
184      detail::wrap_ref<queue_t> Qref(Q);
185      breadth_first_search
186        (g, s,
187         choose_param(get_param(params, buffer_param_t()), Qref).ref,
188         vis, color);
189    }
190
191    //-------------------------------------------------------------------------
192    // Choose between default color and color parameters. Using
193    // function dispatching so that we don't require vertex index if
194    // the color default is not being used.
195
196    template <class ColorMap>
197    struct bfs_dispatch {
198      template <class VertexListGraph, class P, class T, class R>
199      static void apply
200      (VertexListGraph& g,
201       typename graph_traits<VertexListGraph>::vertex_descriptor s,
202       const bgl_named_params<P, T, R>& params,
203       ColorMap color)
204      {
205        bfs_helper
206          (g, s, color,
207           choose_param(get_param(params, graph_visitor),
208                        make_bfs_visitor(null_visitor())),
209           params);
210      }
211    };
212
213    template <>
214    struct bfs_dispatch<detail::error_property_not_found> {
215      template <class VertexListGraph, class P, class T, class R>
216      static void apply
217      (VertexListGraph& g,
218       typename graph_traits<VertexListGraph>::vertex_descriptor s,
219       const bgl_named_params<P, T, R>& params,
220       detail::error_property_not_found)
221      {
222        std::vector<default_color_type> color_vec(num_vertices(g));
223        default_color_type c = white_color;
224        null_visitor null_vis;
225
226        bfs_helper
227          (g, s,
228           make_iterator_property_map
229           (color_vec.begin(),
230            choose_const_pmap(get_param(params, vertex_index),
231                              g, vertex_index), c),
232           choose_param(get_param(params, graph_visitor),
233                        make_bfs_visitor(null_vis)),
234           params);
235      }
236    };
237
238  } // namespace detail
239
240
241  // Named Parameter Variant
242  template <class VertexListGraph, class P, class T, class R>
243  void breadth_first_search
244    (const VertexListGraph& g,
245     typename graph_traits<VertexListGraph>::vertex_descriptor s,
246     const bgl_named_params<P, T, R>& params)
247  {
248    // The graph is passed by *const* reference so that graph adaptors
249    // (temporaries) can be passed into this function. However, the
250    // graph is not really const since we may write to property maps
251    // of the graph.
252    VertexListGraph& ng = const_cast<VertexListGraph&>(g);
253    typedef typename property_value< bgl_named_params<P,T,R>,
254      vertex_color_t>::type C;
255    detail::bfs_dispatch<C>::apply(ng, s, params,
256                                   get_param(params, vertex_color));
257  }
258
259
260  // This version does not initialize colors, user has to.
261
262  template <class IncidenceGraph, class P, class T, class R>
263  void breadth_first_visit
264    (const IncidenceGraph& g,
265     typename graph_traits<IncidenceGraph>::vertex_descriptor s,
266     const bgl_named_params<P, T, R>& params)
267  {
268    // The graph is passed by *const* reference so that graph adaptors
269    // (temporaries) can be passed into this function. However, the
270    // graph is not really const since we may write to property maps
271    // of the graph.
272    IncidenceGraph& ng = const_cast<IncidenceGraph&>(g);
273
274    typedef graph_traits<IncidenceGraph> Traits;
275    // Buffer default
276    typedef typename Traits::vertex_descriptor vertex_descriptor;
277    typedef boost::queue<vertex_descriptor> queue_t;
278    queue_t Q;
279    detail::wrap_ref<queue_t> Qref(Q);
280
281    breadth_first_visit
282      (ng, s,
283       choose_param(get_param(params, buffer_param_t()), Qref).ref,
284       choose_param(get_param(params, graph_visitor),
285                    make_bfs_visitor(null_visitor())),
286       choose_pmap(get_param(params, vertex_color), ng, vertex_color)
287       );
288  }
289
290} // namespace boost
291
292#endif // BOOST_GRAPH_BREADTH_FIRST_SEARCH_HPP
293
Note: See TracBrowser for help on using the repository browser.