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