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 

    25 namespace 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       vis.initialize_vertex(*i, g);

    98       put(color, *i, Color::white());

    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