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_BREADTH_FIRST_SEARCH_HPP
Chris@16: #define BOOST_GRAPH_BREADTH_FIRST_SEARCH_HPP
Chris@16: 
Chris@16: /*
Chris@16:   Breadth First Search Algorithm (Cormen, Leiserson, and Rivest p. 470)
Chris@16: */
Chris@16: #include <boost/config.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/graph/overloading.hpp>
Chris@16: #include <boost/graph/graph_concepts.hpp>
Chris@16: #include <boost/graph/two_bit_color_map.hpp>
Chris@16: #include <boost/concept/assert.hpp>
Chris@16: 
Chris@16: #ifdef BOOST_GRAPH_USE_MPI
Chris@16: #include <boost/graph/distributed/concepts.hpp>
Chris@16: #endif // BOOST_GRAPH_USE_MPI
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16:   template <class Visitor, class Graph>
Chris@16:   struct BFSVisitorConcept {
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_edge(e, g);
Chris@16:       vis.tree_edge(e, g);
Chris@16:       vis.non_tree_edge(e, g);
Chris@16:       vis.gray_target(e, g);
Chris@16:       vis.black_target(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: 
Chris@16:   // Multiple-source version
Chris@16:   template <class IncidenceGraph, class Buffer, class BFSVisitor,
Chris@16:             class ColorMap, class SourceIterator>
Chris@16:   void breadth_first_visit
Chris@16:     (const IncidenceGraph& g,
Chris@16:      SourceIterator sources_begin, SourceIterator sources_end,
Chris@16:      Buffer& Q, BFSVisitor vis, ColorMap color)
Chris@16:   {
Chris@16:     BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<IncidenceGraph> ));
Chris@16:     typedef graph_traits<IncidenceGraph> GTraits;
Chris@16:     typedef typename GTraits::vertex_descriptor Vertex;
Chris@16:     BOOST_CONCEPT_ASSERT(( BFSVisitorConcept<BFSVisitor, IncidenceGraph> ));
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:     typename GTraits::out_edge_iterator ei, ei_end;
Chris@16: 
Chris@16:     for (; sources_begin != sources_end; ++sources_begin) {
Chris@16:       Vertex s = *sources_begin;
Chris@16:       put(color, s, Color::gray());           vis.discover_vertex(s, g);
Chris@16:       Q.push(s);
Chris@16:     }
Chris@16:     while (! Q.empty()) {
Chris@16:       Vertex u = Q.top(); Q.pop();            vis.examine_vertex(u, g);
Chris@16:       for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {
Chris@16:         Vertex v = target(*ei, g);            vis.examine_edge(*ei, g);
Chris@16:         ColorValue v_color = get(color, v);
Chris@16:         if (v_color == Color::white()) {      vis.tree_edge(*ei, g);
Chris@16:           put(color, v, Color::gray());       vis.discover_vertex(v, g);
Chris@16:           Q.push(v);
Chris@16:         } else {                              vis.non_tree_edge(*ei, g);
Chris@16:           if (v_color == Color::gray())       vis.gray_target(*ei, g);
Chris@16:           else                                vis.black_target(*ei, g);
Chris@16:         }
Chris@16:       } // end for
Chris@16:       put(color, u, Color::black());          vis.finish_vertex(u, g);
Chris@16:     } // end while
Chris@16:   } // breadth_first_visit
Chris@16: 
Chris@16:   // Single-source version
Chris@16:   template <class IncidenceGraph, class Buffer, class BFSVisitor,
Chris@16:             class ColorMap>
Chris@16:   void breadth_first_visit
Chris@16:     (const IncidenceGraph& g,
Chris@16:      typename graph_traits<IncidenceGraph>::vertex_descriptor s,
Chris@16:      Buffer& Q, BFSVisitor vis, ColorMap color)
Chris@16:   {
Chris@16:     typename graph_traits<IncidenceGraph>::vertex_descriptor sources[1] = {s};
Chris@16:     breadth_first_visit(g, sources, sources + 1, Q, vis, color);
Chris@16:   }
Chris@16: 
Chris@16: 
Chris@16:   template <class VertexListGraph, class SourceIterator,
Chris@16:             class Buffer, class BFSVisitor,
Chris@16:             class ColorMap>
Chris@16:   void breadth_first_search
Chris@16:     (const VertexListGraph& g,
Chris@16:      SourceIterator sources_begin, SourceIterator sources_end,
Chris@16:      Buffer& Q, BFSVisitor vis, ColorMap color)
Chris@16:   {
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:       vis.initialize_vertex(*i, g);
Chris@16:       put(color, *i, Color::white());
Chris@16:     }
Chris@16:     breadth_first_visit(g, sources_begin, sources_end, Q, vis, color);
Chris@16:   }
Chris@16: 
Chris@16:   template <class VertexListGraph, class Buffer, class BFSVisitor,
Chris@16:             class ColorMap>
Chris@16:   void breadth_first_search
Chris@16:     (const VertexListGraph& g,
Chris@16:      typename graph_traits<VertexListGraph>::vertex_descriptor s,
Chris@16:      Buffer& Q, BFSVisitor vis, ColorMap color)
Chris@16:   {
Chris@16:     typename graph_traits<VertexListGraph>::vertex_descriptor sources[1] = {s};
Chris@16:     breadth_first_search(g, sources, sources + 1, Q, vis, color);
Chris@16:   }
Chris@16: 
Chris@16:   namespace graph { struct bfs_visitor_event_not_overridden {}; }
Chris@16: 
Chris@16: 
Chris@16:   template <class Visitors = null_visitor>
Chris@16:   class bfs_visitor {
Chris@16:   public:
Chris@16:     bfs_visitor() { }
Chris@16:     bfs_visitor(Visitors vis) : m_vis(vis) { }
Chris@16: 
Chris@16:     template <class Vertex, class Graph>
Chris@16:     graph::bfs_visitor_event_not_overridden
Chris@16:     initialize_vertex(Vertex u, Graph& g)
Chris@16:     {
Chris@16:       invoke_visitors(m_vis, u, g, ::boost::on_initialize_vertex());
Chris@16:       return graph::bfs_visitor_event_not_overridden();
Chris@16:     }
Chris@16: 
Chris@16:     template <class Vertex, class Graph>
Chris@16:     graph::bfs_visitor_event_not_overridden
Chris@16:     discover_vertex(Vertex u, Graph& g)
Chris@16:     {
Chris@16:       invoke_visitors(m_vis, u, g, ::boost::on_discover_vertex());
Chris@16:       return graph::bfs_visitor_event_not_overridden();
Chris@16:     }
Chris@16: 
Chris@16:     template <class Vertex, class Graph>
Chris@16:     graph::bfs_visitor_event_not_overridden
Chris@16:     examine_vertex(Vertex u, Graph& g)
Chris@16:     {
Chris@16:       invoke_visitors(m_vis, u, g, ::boost::on_examine_vertex());
Chris@16:       return graph::bfs_visitor_event_not_overridden();
Chris@16:     }
Chris@16: 
Chris@16:     template <class Edge, class Graph>
Chris@16:     graph::bfs_visitor_event_not_overridden
Chris@16:     examine_edge(Edge e, Graph& g)
Chris@16:     {
Chris@16:       invoke_visitors(m_vis, e, g, ::boost::on_examine_edge());
Chris@16:       return graph::bfs_visitor_event_not_overridden();
Chris@16:     }
Chris@16: 
Chris@16:     template <class Edge, class Graph>
Chris@16:     graph::bfs_visitor_event_not_overridden
Chris@16:     tree_edge(Edge e, Graph& g)
Chris@16:     {
Chris@16:       invoke_visitors(m_vis, e, g, ::boost::on_tree_edge());
Chris@16:       return graph::bfs_visitor_event_not_overridden();
Chris@16:     }
Chris@16: 
Chris@16:     template <class Edge, class Graph>
Chris@16:     graph::bfs_visitor_event_not_overridden
Chris@16:     non_tree_edge(Edge e, Graph& g)
Chris@16:     {
Chris@16:       invoke_visitors(m_vis, e, g, ::boost::on_non_tree_edge());
Chris@16:       return graph::bfs_visitor_event_not_overridden();
Chris@16:     }
Chris@16: 
Chris@16:     template <class Edge, class Graph>
Chris@16:     graph::bfs_visitor_event_not_overridden
Chris@16:     gray_target(Edge e, Graph& g)
Chris@16:     {
Chris@16:       invoke_visitors(m_vis, e, g, ::boost::on_gray_target());
Chris@16:       return graph::bfs_visitor_event_not_overridden();
Chris@16:     }
Chris@16: 
Chris@16:     template <class Edge, class Graph>
Chris@16:     graph::bfs_visitor_event_not_overridden
Chris@16:     black_target(Edge e, Graph& g)
Chris@16:     {
Chris@16:       invoke_visitors(m_vis, e, g, ::boost::on_black_target());
Chris@16:       return graph::bfs_visitor_event_not_overridden();
Chris@16:     }
Chris@16: 
Chris@16:     template <class Vertex, class Graph>
Chris@16:     graph::bfs_visitor_event_not_overridden
Chris@16:     finish_vertex(Vertex u, Graph& g)
Chris@16:     {
Chris@16:       invoke_visitors(m_vis, u, g, ::boost::on_finish_vertex());
Chris@16:       return graph::bfs_visitor_event_not_overridden();
Chris@16:     }
Chris@16: 
Chris@16:     BOOST_GRAPH_EVENT_STUB(on_initialize_vertex,bfs)
Chris@16:     BOOST_GRAPH_EVENT_STUB(on_discover_vertex,bfs)
Chris@16:     BOOST_GRAPH_EVENT_STUB(on_examine_vertex,bfs)
Chris@16:     BOOST_GRAPH_EVENT_STUB(on_examine_edge,bfs)
Chris@16:     BOOST_GRAPH_EVENT_STUB(on_tree_edge,bfs)
Chris@16:     BOOST_GRAPH_EVENT_STUB(on_non_tree_edge,bfs)
Chris@16:     BOOST_GRAPH_EVENT_STUB(on_gray_target,bfs)
Chris@16:     BOOST_GRAPH_EVENT_STUB(on_black_target,bfs)
Chris@16:     BOOST_GRAPH_EVENT_STUB(on_finish_vertex,bfs)
Chris@16: 
Chris@16:   protected:
Chris@16:     Visitors m_vis;
Chris@16:   };
Chris@16:   template <class Visitors>
Chris@16:   bfs_visitor<Visitors>
Chris@16:   make_bfs_visitor(Visitors vis) {
Chris@16:     return bfs_visitor<Visitors>(vis);
Chris@16:   }
Chris@16:   typedef bfs_visitor<> default_bfs_visitor;
Chris@16: 
Chris@16: 
Chris@16:   namespace detail {
Chris@16: 
Chris@16:     template <class VertexListGraph, class ColorMap, class BFSVisitor,
Chris@16:       class P, class T, class R>
Chris@16:     void 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:        boost::mpl::false_)
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:       breadth_first_search
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: #ifdef BOOST_GRAPH_USE_MPI
Chris@16:     template <class DistributedGraph, class ColorMap, class BFSVisitor,
Chris@16:               class P, class T, class R>
Chris@16:     void bfs_helper
Chris@16:       (DistributedGraph& g,
Chris@16:        typename graph_traits<DistributedGraph>::vertex_descriptor s,
Chris@16:        ColorMap color,
Chris@16:        BFSVisitor vis,
Chris@16:        const bgl_named_params<P, T, R>& params,
Chris@16:        boost::mpl::true_);
Chris@16: #endif // BOOST_GRAPH_USE_MPI
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 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:         bfs_helper
Chris@16:           (g, s, color,
Chris@16:            choose_param(get_param(params, graph_visitor),
Chris@16:                         make_bfs_visitor(null_visitor())),
Chris@16:            params,
Chris@16:            boost::mpl::bool_<
Chris@16:              boost::is_base_and_derived<
Chris@16:                distributed_graph_tag,
Chris@16:                typename graph_traits<VertexListGraph>::traversal_category>::value>());
Chris@16:       }
Chris@16:     };
Chris@16: 
Chris@16:     template <>
Chris@16:     struct 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:         null_visitor null_vis;
Chris@16: 
Chris@16:         bfs_helper
Chris@16:           (g, s,
Chris@16:            make_two_bit_color_map
Chris@16:            (num_vertices(g),
Chris@16:             choose_const_pmap(get_param(params, vertex_index),
Chris@16:                               g, vertex_index)),
Chris@16:            choose_param(get_param(params, graph_visitor),
Chris@16:                         make_bfs_visitor(null_vis)),
Chris@16:            params,
Chris@16:            boost::mpl::bool_<
Chris@16:              boost::is_base_and_derived<
Chris@16:                distributed_graph_tag,
Chris@16:                typename graph_traits<VertexListGraph>::traversal_category>::value>());
Chris@16:       }
Chris@16:     };
Chris@16: 
Chris@16:   } // namespace detail
Chris@16: 
Chris@16: #if 1
Chris@16:   // Named Parameter Variant
Chris@16:   template <class VertexListGraph, class P, class T, class R>
Chris@16:   void 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::bfs_dispatch<C>::apply(ng, s, params,
Chris@16:                                    get_param(params, vertex_color));
Chris@16:   }
Chris@16: #endif
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 breadth_first_visit
Chris@16:     (const 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:     // 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:     IncidenceGraph& ng = const_cast<IncidenceGraph&>(g);
Chris@16: 
Chris@16:     typedef graph_traits<IncidenceGraph> Traits;
Chris@16:     // Buffer default
Chris@16:     typedef typename Traits::vertex_descriptor vertex_descriptor;
Chris@16:     typedef boost::queue<vertex_descriptor> queue_t;
Chris@16:     queue_t Q;
Chris@16: 
Chris@16:     breadth_first_visit
Chris@16:       (ng, 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_bfs_visitor(null_visitor())),
Chris@16:        choose_pmap(get_param(params, vertex_color), ng, vertex_color)
Chris@16:        );
Chris@16:   }
Chris@16: 
Chris@16:   namespace graph {
Chris@16:     namespace detail {
Chris@16:       template <typename Graph, typename Source>
Chris@16:       struct breadth_first_search_impl {
Chris@16:         typedef void result_type;
Chris@16:         template <typename ArgPack>
Chris@16:         void operator()(const Graph& g, const Source& source, const ArgPack& arg_pack) {
Chris@16:           using namespace boost::graph::keywords;
Chris@16:           typename boost::graph_traits<Graph>::vertex_descriptor sources[1] = {source};
Chris@16:           boost::queue<typename boost::graph_traits<Graph>::vertex_descriptor> Q;
Chris@16:           boost::breadth_first_search(g,
Chris@16:                                       &sources[0],
Chris@16:                                       &sources[1], 
Chris@16:                                       boost::unwrap_ref(arg_pack[_buffer | boost::ref(Q)]),
Chris@16:                                       arg_pack[_visitor | make_bfs_visitor(null_visitor())],
Chris@16:                                       boost::detail::make_color_map_from_arg_pack(g, arg_pack));
Chris@16:         }
Chris@16:       };
Chris@16:     }
Chris@16:     BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(breadth_first_search, 2, 4)
Chris@16:   }
Chris@16: 
Chris@16: #if 0
Chris@16:   // Named Parameter Variant
Chris@16:   BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(breadth_first_search, 2)
Chris@16: #endif
Chris@16: 
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #ifdef BOOST_GRAPH_USE_MPI
Chris@16: #  include <boost/graph/distributed/breadth_first_search.hpp>
Chris@16: #endif
Chris@16: 
Chris@16: #endif // BOOST_GRAPH_BREADTH_FIRST_SEARCH_HPP
Chris@16: