Chris@16: //
Chris@16: //=======================================================================
Chris@16: // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
Chris@16: // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //=======================================================================
Chris@16: //
Chris@16: #ifndef BOOST_GRAPH_NEIGHBOR_BREADTH_FIRST_SEARCH_HPP
Chris@16: #define BOOST_GRAPH_NEIGHBOR_BREADTH_FIRST_SEARCH_HPP
Chris@16: 
Chris@16: /*
Chris@16:   Neighbor Breadth First Search
Chris@16:   Like BFS, but traverses in-edges as well as out-edges.
Chris@16:   (for directed graphs only. use normal BFS for undirected graphs)
Chris@16: */
Chris@16: #include <boost/config.hpp>
Chris@16: #include <boost/ref.hpp>
Chris@16: #include <vector>
Chris@16: #include <boost/pending/queue.hpp>
Chris@16: #include <boost/graph/graph_traits.hpp>
Chris@16: #include <boost/graph/graph_concepts.hpp>
Chris@16: #include <boost/graph/visitors.hpp>
Chris@16: #include <boost/graph/named_function_params.hpp>
Chris@16: #include <boost/concept/assert.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16:   template <class Visitor, class Graph>
Chris@16:   struct NeighborBFSVisitorConcept {
Chris@16:     void constraints() {
Chris@16:       BOOST_CONCEPT_ASSERT(( CopyConstructibleConcept<Visitor> ));
Chris@16:       vis.initialize_vertex(u, g);
Chris@16:       vis.discover_vertex(u, g);
Chris@16:       vis.examine_vertex(u, g);
Chris@16:       vis.examine_out_edge(e, g);
Chris@16:       vis.examine_in_edge(e, g);
Chris@16:       vis.tree_out_edge(e, g);
Chris@16:       vis.tree_in_edge(e, g);
Chris@16:       vis.non_tree_out_edge(e, g);
Chris@16:       vis.non_tree_in_edge(e, g);
Chris@16:       vis.gray_target(e, g);
Chris@16:       vis.black_target(e, g);
Chris@16:       vis.gray_source(e, g);
Chris@16:       vis.black_source(e, g);
Chris@16:       vis.finish_vertex(u, g);
Chris@16:     }
Chris@16:     Visitor vis;
Chris@16:     Graph g;
Chris@16:     typename graph_traits<Graph>::vertex_descriptor u;
Chris@16:     typename graph_traits<Graph>::edge_descriptor e;
Chris@16:   };
Chris@16: 
Chris@16:   template <class Visitors = null_visitor>
Chris@16:   class neighbor_bfs_visitor {
Chris@16:   public:
Chris@16:     neighbor_bfs_visitor(Visitors vis = Visitors()) : m_vis(vis) { }
Chris@16: 
Chris@16:     template <class Vertex, class Graph>
Chris@16:     void initialize_vertex(Vertex u, Graph& g) {
Chris@16:       invoke_visitors(m_vis, u, g, on_initialize_vertex());      
Chris@16:     }
Chris@16:     template <class Vertex, class Graph>
Chris@16:     void discover_vertex(Vertex u, Graph& g) {
Chris@16:       invoke_visitors(m_vis, u, g, on_discover_vertex());      
Chris@16:     }
Chris@16:     template <class Vertex, class Graph>
Chris@16:     void examine_vertex(Vertex u, Graph& g) {
Chris@16:       invoke_visitors(m_vis, u, g, on_examine_vertex());
Chris@16:     }
Chris@16:     template <class Edge, class Graph>
Chris@16:     void examine_out_edge(Edge e, Graph& g) {
Chris@16:       invoke_visitors(m_vis, e, g, on_examine_edge());
Chris@16:     }
Chris@16:     template <class Edge, class Graph>
Chris@16:     void tree_out_edge(Edge e, Graph& g) {
Chris@16:       invoke_visitors(m_vis, e, g, on_tree_edge());      
Chris@16:     }
Chris@16:     template <class Edge, class Graph>
Chris@16:     void non_tree_out_edge(Edge e, Graph& g) {
Chris@16:       invoke_visitors(m_vis, e, g, on_non_tree_edge());
Chris@16:     }
Chris@16:     template <class Edge, class Graph>
Chris@16:     void gray_target(Edge e, Graph& g) {
Chris@16:       invoke_visitors(m_vis, e, g, on_gray_target());
Chris@16:     }
Chris@16:     template <class Edge, class Graph>
Chris@16:     void black_target(Edge e, Graph& g) {
Chris@16:       invoke_visitors(m_vis, e, g, on_black_target());
Chris@16:     }
Chris@16:     template <class Edge, class Graph>
Chris@16:     void examine_in_edge(Edge e, Graph& g) {
Chris@16:       invoke_visitors(m_vis, e, g, on_examine_edge());
Chris@16:     }
Chris@16:     template <class Edge, class Graph>
Chris@16:     void tree_in_edge(Edge e, Graph& g) {
Chris@16:       invoke_visitors(m_vis, e, g, on_tree_edge());      
Chris@16:     }
Chris@16:     template <class Edge, class Graph>
Chris@16:     void non_tree_in_edge(Edge e, Graph& g) {
Chris@16:       invoke_visitors(m_vis, e, g, on_non_tree_edge());
Chris@16:     }
Chris@16:     template <class Edge, class Graph>
Chris@16:     void gray_source(Edge e, Graph& g) {
Chris@16:       invoke_visitors(m_vis, e, g, on_gray_target());
Chris@16:     }
Chris@16:     template <class Edge, class Graph>
Chris@16:     void black_source(Edge e, Graph& g) {
Chris@16:       invoke_visitors(m_vis, e, g, on_black_target());
Chris@16:     }
Chris@16:     template <class Vertex, class Graph>
Chris@16:     void finish_vertex(Vertex u, Graph& g) {
Chris@16:       invoke_visitors(m_vis, u, g, on_finish_vertex());      
Chris@16:     }
Chris@16:   protected:
Chris@16:     Visitors m_vis;
Chris@16:   };
Chris@16: 
Chris@16:   template <class Visitors>
Chris@16:   neighbor_bfs_visitor<Visitors>
Chris@16:   make_neighbor_bfs_visitor(Visitors vis) {
Chris@16:     return neighbor_bfs_visitor<Visitors>(vis);
Chris@16:   }
Chris@16: 
Chris@16:   namespace detail {
Chris@16: 
Chris@16:     template <class BidirectionalGraph, class Buffer, class BFSVisitor, 
Chris@16:               class ColorMap>
Chris@16:     void neighbor_bfs_impl
Chris@16:       (const BidirectionalGraph& g, 
Chris@16:        typename graph_traits<BidirectionalGraph>::vertex_descriptor s, 
Chris@16:        Buffer& Q, BFSVisitor vis, ColorMap color)
Chris@16: 
Chris@16:     {
Chris@16:       BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<BidirectionalGraph> ));
Chris@16:       typedef graph_traits<BidirectionalGraph> GTraits;
Chris@16:       typedef typename GTraits::vertex_descriptor Vertex;
Chris@16:       typedef typename GTraits::edge_descriptor Edge;
Chris@16:       BOOST_CONCEPT_ASSERT(( 
Chris@16:         NeighborBFSVisitorConcept<BFSVisitor, BidirectionalGraph> ));
Chris@16:       BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<ColorMap, Vertex> ));
Chris@16:       typedef typename property_traits<ColorMap>::value_type ColorValue;
Chris@16:       typedef color_traits<ColorValue> Color;
Chris@16:       
Chris@16:       put(color, s, Color::gray());
Chris@16:       vis.discover_vertex(s, g);
Chris@16:       Q.push(s);
Chris@16:       while (! Q.empty()) {
Chris@16:         Vertex u = Q.top();
Chris@16:         Q.pop(); // pop before push to avoid problem if Q is priority_queue.
Chris@16:         vis.examine_vertex(u, g);
Chris@16: 
Chris@16:         typename GTraits::out_edge_iterator ei, ei_end;
Chris@16:         for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {
Chris@16:           Edge e = *ei;
Chris@16:           vis.examine_out_edge(e, g);
Chris@16:           Vertex v = target(e, g);
Chris@16:           ColorValue v_color = get(color, v);
Chris@16:           if (v_color == Color::white()) {
Chris@16:             vis.tree_out_edge(e, g);
Chris@16:             put(color, v, Color::gray());
Chris@16:             vis.discover_vertex(v, g);
Chris@16:             Q.push(v);
Chris@16:           } else {
Chris@16:             vis.non_tree_out_edge(e, g);
Chris@16:             if (v_color == Color::gray())
Chris@16:               vis.gray_target(e, g);
Chris@16:             else
Chris@16:               vis.black_target(e, g);
Chris@16:           }
Chris@16:         } // for out-edges
Chris@16: 
Chris@16:         typename GTraits::in_edge_iterator in_ei, in_ei_end;
Chris@16:         for (boost::tie(in_ei, in_ei_end) = in_edges(u, g); 
Chris@16:              in_ei != in_ei_end; ++in_ei) {
Chris@16:           Edge e = *in_ei;
Chris@16:           vis.examine_in_edge(e, g);
Chris@16:           Vertex v = source(e, g);
Chris@16:           ColorValue v_color = get(color, v);
Chris@16:           if (v_color == Color::white()) {
Chris@16:             vis.tree_in_edge(e, g);
Chris@16:             put(color, v, Color::gray());
Chris@16:             vis.discover_vertex(v, g);
Chris@16:             Q.push(v);
Chris@16:           } else {
Chris@16:             vis.non_tree_in_edge(e, g);
Chris@16:             if (v_color == Color::gray())
Chris@16:               vis.gray_source(e, g);
Chris@16:             else
Chris@16:               vis.black_source(e, g);
Chris@16:           }
Chris@16:         } // for in-edges
Chris@16: 
Chris@16:         put(color, u, Color::black());
Chris@16:         vis.finish_vertex(u, g);
Chris@16:       } // while
Chris@16:     }
Chris@16: 
Chris@16:     
Chris@16:     template <class VertexListGraph, class ColorMap, class BFSVisitor,
Chris@16:       class P, class T, class R>
Chris@16:     void neighbor_bfs_helper
Chris@16:       (VertexListGraph& g,
Chris@16:        typename graph_traits<VertexListGraph>::vertex_descriptor s,
Chris@16:        ColorMap color, 
Chris@16:        BFSVisitor vis,
Chris@16:        const bgl_named_params<P, T, R>& params)
Chris@16:     {
Chris@16:       typedef graph_traits<VertexListGraph> Traits;
Chris@16:       // Buffer default
Chris@16:       typedef typename Traits::vertex_descriptor Vertex;
Chris@16:       typedef boost::queue<Vertex> queue_t;
Chris@16:       queue_t Q;
Chris@16:       // Initialization
Chris@16:       typedef typename property_traits<ColorMap>::value_type ColorValue;
Chris@16:       typedef color_traits<ColorValue> Color;
Chris@16:       typename boost::graph_traits<VertexListGraph>::vertex_iterator i, i_end;
Chris@16:       for (boost::tie(i, i_end) = vertices(g); i != i_end; ++i) {
Chris@16:         put(color, *i, Color::white());
Chris@16:         vis.initialize_vertex(*i, g);
Chris@16:       }
Chris@16:       neighbor_bfs_impl
Chris@16:         (g, s, 
Chris@16:          choose_param(get_param(params, buffer_param_t()), boost::ref(Q)).get(),
Chris@16:          vis, color);
Chris@16:     }
Chris@16: 
Chris@16:     //-------------------------------------------------------------------------
Chris@16:     // Choose between default color and color parameters. Using
Chris@16:     // function dispatching so that we don't require vertex index if
Chris@16:     // the color default is not being used.
Chris@16: 
Chris@16:     template <class ColorMap>
Chris@16:     struct neighbor_bfs_dispatch {
Chris@16:       template <class VertexListGraph, class P, class T, class R>
Chris@16:       static void apply
Chris@16:       (VertexListGraph& g,
Chris@16:        typename graph_traits<VertexListGraph>::vertex_descriptor s,
Chris@16:        const bgl_named_params<P, T, R>& params,
Chris@16:        ColorMap color)
Chris@16:       {
Chris@16:         neighbor_bfs_helper
Chris@16:           (g, s, color,
Chris@16:            choose_param(get_param(params, graph_visitor),
Chris@16:                         make_neighbor_bfs_visitor(null_visitor())),
Chris@16:            params);
Chris@16:       }
Chris@16:     };
Chris@16: 
Chris@16:     template <>
Chris@16:     struct neighbor_bfs_dispatch<param_not_found> {
Chris@16:       template <class VertexListGraph, class P, class T, class R>
Chris@16:       static void apply
Chris@16:       (VertexListGraph& g,
Chris@16:        typename graph_traits<VertexListGraph>::vertex_descriptor s,
Chris@16:        const bgl_named_params<P, T, R>& params,
Chris@16:        param_not_found)
Chris@16:       {
Chris@16:         std::vector<default_color_type> color_vec(num_vertices(g));
Chris@16:         null_visitor null_vis;
Chris@16:         
Chris@16:         neighbor_bfs_helper
Chris@16:           (g, s, 
Chris@16:            make_iterator_property_map
Chris@16:            (color_vec.begin(), 
Chris@16:             choose_const_pmap(get_param(params, vertex_index), 
Chris@16:                               g, vertex_index), color_vec[0]),
Chris@16:            choose_param(get_param(params, graph_visitor),
Chris@16:                         make_neighbor_bfs_visitor(null_vis)),
Chris@16:            params);
Chris@16:       }
Chris@16:     };
Chris@16: 
Chris@16:   } // namespace detail
Chris@16: 
Chris@16: 
Chris@16:   // Named Parameter Variant
Chris@16:   template <class VertexListGraph, class P, class T, class R>
Chris@16:   void neighbor_breadth_first_search
Chris@16:     (const VertexListGraph& g,
Chris@16:      typename graph_traits<VertexListGraph>::vertex_descriptor s,
Chris@16:      const bgl_named_params<P, T, R>& params)
Chris@16:   {
Chris@16:     // The graph is passed by *const* reference so that graph adaptors
Chris@16:     // (temporaries) can be passed into this function. However, the
Chris@16:     // graph is not really const since we may write to property maps
Chris@16:     // of the graph.
Chris@16:     VertexListGraph& ng = const_cast<VertexListGraph&>(g);
Chris@16:     typedef typename get_param_type< vertex_color_t, bgl_named_params<P,T,R> >::type C;
Chris@16:     detail::neighbor_bfs_dispatch<C>::apply(ng, s, params, 
Chris@16:                                             get_param(params, vertex_color));
Chris@16:   }
Chris@16: 
Chris@16: 
Chris@16:   // This version does not initialize colors, user has to.
Chris@16: 
Chris@16:   template <class IncidenceGraph, class P, class T, class R>
Chris@16:   void neighbor_breadth_first_visit
Chris@16:     (IncidenceGraph& g,
Chris@16:      typename graph_traits<IncidenceGraph>::vertex_descriptor s,
Chris@16:      const bgl_named_params<P, T, R>& params)
Chris@16:   {
Chris@16:     typedef graph_traits<IncidenceGraph> Traits;
Chris@16:     // Buffer default
Chris@16:     typedef boost::queue<typename Traits::vertex_descriptor> queue_t;
Chris@16:     queue_t Q;
Chris@16: 
Chris@16:     detail::neighbor_bfs_impl
Chris@16:       (g, s,
Chris@16:        choose_param(get_param(params, buffer_param_t()), boost::ref(Q)).get(),
Chris@16:        choose_param(get_param(params, graph_visitor),
Chris@16:                     make_neighbor_bfs_visitor(null_visitor())),
Chris@16:        choose_pmap(get_param(params, vertex_color), g, vertex_color)
Chris@16:        );
Chris@16:   }
Chris@16: 
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #endif // BOOST_GRAPH_NEIGHBOR_BREADTH_FIRST_SEARCH_HPP
Chris@16: