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 { constraintsboost::NeighborBFSVisitorConcept33 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: neighbor_bfs_visitor(Visitors vis=Visitors ())59 neighbor_bfs_visitor(Visitors vis = Visitors()) : m_vis(vis) { } 60 61 template <class Vertex, class Graph> initialize_vertex(Vertex u,Graph & g)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> discover_vertex(Vertex u,Graph & g)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> examine_vertex(Vertex u,Graph & g)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> examine_out_edge(Edge e,Graph & g)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> tree_out_edge(Edge e,Graph & g)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> non_tree_out_edge(Edge e,Graph & g)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> gray_target(Edge e,Graph & g)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> black_target(Edge e,Graph & g)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> examine_in_edge(Edge e,Graph & g)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> tree_in_edge(Edge e,Graph & g)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> non_tree_in_edge(Edge e,Graph & g)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> gray_source(Edge e,Graph & g)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> black_source(Edge e,Graph & g)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> finish_vertex(Vertex u,Graph & g)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> make_neighbor_bfs_visitor(Visitors vis)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> neighbor_bfs_impl(const BidirectionalGraph & g,typename graph_traits<BidirectionalGraph>::vertex_descriptor s,Buffer & Q,BFSVisitor vis,ColorMap color)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> neighbor_bfs_helper(VertexListGraph & g,typename graph_traits<VertexListGraph>::vertex_descriptor s,ColorMap color,BFSVisitor vis,const bgl_named_params<P,T,R> & params)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> applyboost::detail::neighbor_bfs_dispatch238 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> applyboost::detail::neighbor_bfs_dispatch255 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> neighbor_breadth_first_search(const VertexListGraph & g,typename graph_traits<VertexListGraph>::vertex_descriptor s,const bgl_named_params<P,T,R> & params)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> neighbor_breadth_first_visit(IncidenceGraph & g,typename graph_traits<IncidenceGraph>::vertex_descriptor s,const bgl_named_params<P,T,R> & params)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 323