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