boost/graph/neighbor_bfs.hpp

0001 //
0002 //=======================================================================
0003 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
0004 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
0005 //
0006 // Distributed under the Boost Software License, Version 1.0. (See
0007 // accompanying file LICENSE_1_0.txt or copy at
0008 // http://www.boost.org/LICENSE_1_0.txt)
0009 //=======================================================================
0010 //
0011 #ifndef BOOST_GRAPH_NEIGHBOR_BREADTH_FIRST_SEARCH_HPP
0012 #define BOOST_GRAPH_NEIGHBOR_BREADTH_FIRST_SEARCH_HPP
0013
0014 /*
0015   Neighbor Breadth First Search
0016   Like BFS, but traverses in-edges as well as out-edges.
0017   (for directed graphs only. use normal BFS for undirected graphs)
0018 */
0019 #include <boost/config.hpp>
0020 #include <boost/ref.hpp>
0021 #include <vector>
0022 #include <boost/pending/queue.hpp>
0023 #include <boost/graph/graph_traits.hpp>
0024 #include <boost/graph/graph_concepts.hpp>
0025 #include <boost/graph/visitors.hpp>
0026 #include <boost/graph/named_function_params.hpp>
0027 #include <boost/concept/assert.hpp>
0028
0029 namespace boost
0030 {
0031
0032 template < class Visitor, class Graph > struct NeighborBFSVisitorConcept
0033 {
0034     void constraints()
0035     {
0036         BOOST_CONCEPT_ASSERT((CopyConstructibleConcept< Visitor >));
0037         vis.initialize_vertex(u, g);
0038         vis.discover_vertex(u, g);
0039         vis.examine_vertex(u, g);
0040         vis.examine_out_edge(e, g);
0041         vis.examine_in_edge(e, g);
0042         vis.tree_out_edge(e, g);
0043         vis.tree_in_edge(e, g);
0044         vis.non_tree_out_edge(e, g);
0045         vis.non_tree_in_edge(e, g);
0046         vis.gray_target(e, g);
0047         vis.black_target(e, g);
0048         vis.gray_source(e, g);
0049         vis.black_source(e, g);
0050         vis.finish_vertex(u, g);
0051     }
0052     Visitor vis;
0053     Graph g;
0054     typename graph_traits< Graph >::vertex_descriptor u;
0055     typename graph_traits< Graph >::edge_descriptor e;
0056 };
0057
0058 template < class Visitors = null_visitor > class neighbor_bfs_visitor
0059 {
0060 public:
0061     neighbor_bfs_visitor(Visitors vis = Visitors()) : m_vis(vis) {}
0062
0063     template < class Vertex, class Graph >
0064     void initialize_vertex(Vertex u, Graph& g)
0065     {
0066         invoke_visitors(m_vis, u, g, on_initialize_vertex());
0067     }
0068     template < class Vertex, class Graph >
0069     void discover_vertex(Vertex u, Graph& g)
0070     {
0071         invoke_visitors(m_vis, u, g, on_discover_vertex());
0072     }
0073     template < class Vertex, class Graph >
0074     void examine_vertex(Vertex u, Graph& g)
0075     {
0076         invoke_visitors(m_vis, u, g, on_examine_vertex());
0077     }
0078     template < class Edge, class Graph > void examine_out_edge(Edge e, Graph& g)
0079     {
0080         invoke_visitors(m_vis, e, g, on_examine_edge());
0081     }
0082     template < class Edge, class Graph > void tree_out_edge(Edge e, Graph& g)
0083     {
0084         invoke_visitors(m_vis, e, g, on_tree_edge());
0085     }
0086     template < class Edge, class Graph >
0087     void non_tree_out_edge(Edge e, Graph& g)
0088     {
0089         invoke_visitors(m_vis, e, g, on_non_tree_edge());
0090     }
0091     template < class Edge, class Graph > void gray_target(Edge e, Graph& g)
0092     {
0093         invoke_visitors(m_vis, e, g, on_gray_target());
0094     }
0095     template < class Edge, class Graph > void black_target(Edge e, Graph& g)
0096     {
0097         invoke_visitors(m_vis, e, g, on_black_target());
0098     }
0099     template < class Edge, class Graph > void examine_in_edge(Edge e, Graph& g)
0100     {
0101         invoke_visitors(m_vis, e, g, on_examine_edge());
0102     }
0103     template < class Edge, class Graph > void tree_in_edge(Edge e, Graph& g)
0104     {
0105         invoke_visitors(m_vis, e, g, on_tree_edge());
0106     }
0107     template < class Edge, class Graph > void non_tree_in_edge(Edge e, Graph& g)
0108     {
0109         invoke_visitors(m_vis, e, g, on_non_tree_edge());
0110     }
0111     template < class Edge, class Graph > void gray_source(Edge e, Graph& g)
0112     {
0113         invoke_visitors(m_vis, e, g, on_gray_target());
0114     }
0115     template < class Edge, class Graph > void black_source(Edge e, Graph& g)
0116     {
0117         invoke_visitors(m_vis, e, g, on_black_target());
0118     }
0119     template < class Vertex, class Graph >
0120     void finish_vertex(Vertex u, Graph& g)
0121     {
0122         invoke_visitors(m_vis, u, g, on_finish_vertex());
0123     }
0124
0125 protected:
0126     Visitors m_vis;
0127 };
0128
0129 template < class Visitors >
0130 neighbor_bfs_visitor< Visitors > make_neighbor_bfs_visitor(Visitors vis)
0131 {
0132     return neighbor_bfs_visitor< Visitors >(vis);
0133 }
0134
0135 namespace detail
0136 {
0137
0138     template < class BidirectionalGraph, class Buffer, class BFSVisitor,
0139         class ColorMap >
0140     void neighbor_bfs_impl(const BidirectionalGraph& g,
0141         typename graph_traits< BidirectionalGraph >::vertex_descriptor s,
0142         Buffer& Q, BFSVisitor vis, ColorMap color)
0143
0144     {
0145         BOOST_CONCEPT_ASSERT((BidirectionalGraphConcept< BidirectionalGraph >));
0146         typedef graph_traits< BidirectionalGraph > GTraits;
0147         typedef typename GTraits::vertex_descriptor Vertex;
0148         typedef typename GTraits::edge_descriptor Edge;
0149         BOOST_CONCEPT_ASSERT(
0150             (NeighborBFSVisitorConcept< BFSVisitor, BidirectionalGraph >));
0151         BOOST_CONCEPT_ASSERT((ReadWritePropertyMapConcept< ColorMap, Vertex >));
0152         typedef typename property_traits< ColorMap >::value_type ColorValue;
0153         typedef color_traits< ColorValue > Color;
0154
0155         put(color, s, Color::gray());
0156         vis.discover_vertex(s, g);
0157         Q.push(s);
0158         while (!Q.empty())
0159         {
0160             Vertex u = Q.top();
0161             Q.pop(); // pop before push to avoid problem if Q is priority_queue.
0162             vis.examine_vertex(u, g);
0163
0164             typename GTraits::out_edge_iterator ei, ei_end;
0165             for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei)
0166             {
0167                 Edge e = *ei;
0168                 vis.examine_out_edge(e, g);
0169                 Vertex v = target(e, g);
0170                 ColorValue v_color = get(color, v);
0171                 if (v_color == Color::white())
0172                 {
0173                     vis.tree_out_edge(e, g);
0174                     put(color, v, Color::gray());
0175                     vis.discover_vertex(v, g);
0176                     Q.push(v);
0177                 }
0178                 else
0179                 {
0180                     vis.non_tree_out_edge(e, g);
0181                     if (v_color == Color::gray())
0182                         vis.gray_target(e, g);
0183                     else
0184                         vis.black_target(e, g);
0185                 }
0186             } // for out-edges
0187
0188             typename GTraits::in_edge_iterator in_ei, in_ei_end;
0189             for (boost::tie(in_ei, in_ei_end) = in_edges(u, g);
0190                  in_ei != in_ei_end; ++in_ei)
0191             {
0192                 Edge e = *in_ei;
0193                 vis.examine_in_edge(e, g);
0194                 Vertex v = source(e, g);
0195                 ColorValue v_color = get(color, v);
0196                 if (v_color == Color::white())
0197                 {
0198                     vis.tree_in_edge(e, g);
0199                     put(color, v, Color::gray());
0200                     vis.discover_vertex(v, g);
0201                     Q.push(v);
0202                 }
0203                 else
0204                 {
0205                     vis.non_tree_in_edge(e, g);
0206                     if (v_color == Color::gray())
0207                         vis.gray_source(e, g);
0208                     else
0209                         vis.black_source(e, g);
0210                 }
0211             } // for in-edges
0212
0213             put(color, u, Color::black());
0214             vis.finish_vertex(u, g);
0215         } // while
0216     }
0217
0218     template < class VertexListGraph, class ColorMap, class BFSVisitor, class P,
0219         class T, class R >
0220     void neighbor_bfs_helper(VertexListGraph& g,
0221         typename graph_traits< VertexListGraph >::vertex_descriptor s,
0222         ColorMap color, BFSVisitor vis,
0223         const bgl_named_params< P, T, R >& params)
0224     {
0225         typedef graph_traits< VertexListGraph > Traits;
0226         // Buffer default
0227         typedef typename Traits::vertex_descriptor Vertex;
0228         typedef boost::queue< Vertex > queue_t;
0229         queue_t Q;
0230         // Initialization
0231         typedef typename property_traits< ColorMap >::value_type ColorValue;
0232         typedef color_traits< ColorValue > Color;
0233         typename boost::graph_traits< VertexListGraph >::vertex_iterator i,
0234             i_end;
0235         for (boost::tie(i, i_end) = vertices(g); i != i_end; ++i)
0236         {
0237             put(color, *i, Color::white());
0238             vis.initialize_vertex(*i, g);
0239         }
0240         neighbor_bfs_impl(g, s,
0241             choose_param(get_param(params, buffer_param_t()), boost::ref(Q))
0242                 .get(),
0243             vis, color);
0244     }
0245
0246     //-------------------------------------------------------------------------
0247     // Choose between default color and color parameters. Using
0248     // function dispatching so that we don't require vertex index if
0249     // the color default is not being used.
0250
0251     template < class ColorMap > struct neighbor_bfs_dispatch
0252     {
0253         template < class VertexListGraph, class P, class T, class R >
0254         static void apply(VertexListGraph& g,
0255             typename graph_traits< VertexListGraph >::vertex_descriptor s,
0256             const bgl_named_params< P, T, R >& params, ColorMap color)
0257         {
0258             neighbor_bfs_helper(g, s, color,
0259                 choose_param(get_param(params, graph_visitor),
0260                     make_neighbor_bfs_visitor(null_visitor())),
0261                 params);
0262         }
0263     };
0264
0265     template <> struct neighbor_bfs_dispatch< param_not_found >
0266     {
0267         template < class VertexListGraph, class P, class T, class R >
0268         static void apply(VertexListGraph& g,
0269             typename graph_traits< VertexListGraph >::vertex_descriptor s,
0270             const bgl_named_params< P, T, R >& params, param_not_found)
0271         {
0272             std::vector< default_color_type > color_vec(num_vertices(g));
0273             null_visitor null_vis;
0274
0275             neighbor_bfs_helper(g, s,
0276                 make_iterator_property_map(color_vec.begin(),
0277                     choose_const_pmap(
0278                         get_param(params, vertex_index), g, vertex_index),
0279                     color_vec[0]),
0280                 choose_param(get_param(params, graph_visitor),
0281                     make_neighbor_bfs_visitor(null_vis)),
0282                 params);
0283         }
0284     };
0285
0286 } // namespace detail
0287
0288 // Named Parameter Variant
0289 template < class VertexListGraph, class P, class T, class R >
0290 void neighbor_breadth_first_search(const VertexListGraph& g,
0291     typename graph_traits< VertexListGraph >::vertex_descriptor s,
0292     const bgl_named_params< P, T, R >& params)
0293 {
0294     // The graph is passed by *const* reference so that graph adaptors
0295     // (temporaries) can be passed into this function. However, the
0296     // graph is not really const since we may write to property maps
0297     // of the graph.
0298     VertexListGraph& ng = const_cast< VertexListGraph& >(g);
0299     typedef typename get_param_type< vertex_color_t,
0300         bgl_named_params< P, T, R > >::type C;
0301     detail::neighbor_bfs_dispatch< C >::apply(
0302         ng, s, params, get_param(params, vertex_color));
0303 }
0304
0305 // This version does not initialize colors, user has to.
0306
0307 template < class IncidenceGraph, class P, class T, class R >
0308 void neighbor_breadth_first_visit(IncidenceGraph& g,
0309     typename graph_traits< IncidenceGraph >::vertex_descriptor s,
0310     const bgl_named_params< P, T, R >& params)
0311 {
0312     typedef graph_traits< IncidenceGraph > Traits;
0313     // Buffer default
0314     typedef boost::queue< typename Traits::vertex_descriptor > queue_t;
0315     queue_t Q;
0316
0317     detail::neighbor_bfs_impl(g, s,
0318         choose_param(get_param(params, buffer_param_t()), boost::ref(Q)).get(),
0319         choose_param(get_param(params, graph_visitor),
0320             make_neighbor_bfs_visitor(null_visitor())),
0321         choose_pmap(get_param(params, vertex_color), g, vertex_color));
0322 }
0323
0324 } // namespace boost
0325
0326 #endif // BOOST_GRAPH_NEIGHBOR_BREADTH_FIRST_SEARCH_HPP