Chris@16: // Copyright 2008-2010 Gordon Woodhull
Chris@16: // Distributed under the Boost Software License, Version 1.0. 
Chris@16: // (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_MSM_MPL_GRAPH_BREADTH_FIRST_SEARCH_HPP_INCLUDED
Chris@16: #define BOOST_MSM_MPL_GRAPH_BREADTH_FIRST_SEARCH_HPP_INCLUDED
Chris@16: 
Chris@16: #include <boost/msm/mpl_graph/mpl_graph.hpp>
Chris@16: 
Chris@16: #include <boost/mpl/has_key.hpp>
Chris@16: #include <boost/mpl/insert.hpp>
Chris@16: #include <boost/mpl/pair.hpp>
Chris@16: #include <boost/mpl/map.hpp>
Chris@16: #include <boost/mpl/has_key.hpp>
Chris@16: #include <boost/mpl/pop_front.hpp>
Chris@16: #include <boost/mpl/empty.hpp>
Chris@16: #include <boost/mpl/remove.hpp>
Chris@16: 
Chris@16: #include "search_colors.hpp"
Chris@16: 
Chris@16: namespace boost {
Chris@16: namespace msm {
Chris@16: namespace mpl_graph {
Chris@16: 
Chris@16: // bfs takes a visitor which has all the bgl-like metafunctions encapsulated in an 
Chris@16: // "operations" member class, and also a state.  the operations are expected to return a new state
Chris@16: struct bfs_default_visitor_operations {
Chris@16:     template<typename Vertex, typename Graph, typename State>
Chris@16:     struct initialize_vertex {
Chris@16:         typedef State type;       
Chris@16:     };
Chris@16:     
Chris@16:     template<typename Vertex, typename Graph, typename State>
Chris@16:     struct discover_vertex {
Chris@16:         typedef State type;       
Chris@16:     };
Chris@16:     
Chris@16:     template<typename Vertex, typename Graph, typename State>
Chris@16:     struct examine_vertex {
Chris@16:         typedef State type;       
Chris@16:     };
Chris@16:     
Chris@16:     template<typename Vertex, typename Graph, typename State>
Chris@16:     struct examine_edge {
Chris@16:         typedef State type;       
Chris@16:     };
Chris@16:         
Chris@16:     template<typename Edge, typename Graph, typename State>
Chris@16:     struct tree_edge {
Chris@16:         typedef State type;
Chris@16:     };
Chris@16:     
Chris@16:     template<typename Edge, typename Graph, typename State>
Chris@16:     struct non_tree_edge {
Chris@16:         typedef State type;
Chris@16:     };
Chris@16:     
Chris@16:     template<typename Edge, typename Graph, typename State>
Chris@16:     struct gray_target {
Chris@16:         typedef State type;
Chris@16:     };  
Chris@16:     
Chris@16:     template<typename Edge, typename Graph, typename State>
Chris@16:     struct black_target {
Chris@16:         typedef State type;
Chris@16:     };  
Chris@16:     
Chris@16:     template<typename Vertex, typename Graph, typename State>
Chris@16:     struct finish_vertex {
Chris@16:         typedef State type;       
Chris@16:     };
Chris@16: };
Chris@16: 
Chris@16: namespace detail {
Chris@16: 
Chris@16: template<typename Graph, typename VisitorOps, typename VCQState, typename Edge>
Chris@16: struct bfs_run_queue_examine_edge {
Chris@16:     typedef typename VisitorOps::template examine_edge<Edge, Graph, typename mpl::at_c<VCQState, 0>::type>::type visitor_state;
Chris@16:     typedef typename mpl::at_c<VCQState, 1>::type color_state;
Chris@16:     typedef typename mpl::at_c<VCQState, 2>::type vertex_queue;
Chris@16: 
Chris@16:     typedef typename mpl::if_<typename boost::is_same<typename search_color_map_ops::template get_color<typename mpl_graph::target<Edge, Graph>::type, color_state>::type, search_colors::White>::type,
Chris@16:          // unseen target: tree edge, discover target, paint it gray, and enqueue
Chris@16:          mpl::vector<typename VisitorOps::template discover_vertex<typename mpl_graph::target<Edge, Graph>::type, Graph,
Chris@16:                                                                             typename VisitorOps::template tree_edge<Edge, Graph, visitor_state>::type>::type,
Chris@16:                      typename search_color_map_ops::template set_color<typename mpl_graph::target<Edge, Graph>::type, search_colors::Gray, color_state>::type,
Chris@16:                      typename mpl::push_back<vertex_queue, typename mpl_graph::target<Edge, Graph>::type >::type >,
Chris@16:          // seen
Chris@16:          mpl::vector<typename mpl::if_<typename boost::is_same<typename search_color_map_ops::template get_color<mpl_graph::target<Edge, Graph>, color_state>, 
Chris@16:                                              search_colors::Gray>::type,
Chris@16:                               typename VisitorOps::template gray_target<Edge, Graph, visitor_state>::type,
Chris@16:                               typename VisitorOps::template black_target<Edge, Graph, visitor_state>::type>::type,
Chris@16:                      color_state,
Chris@16:                      vertex_queue> 
Chris@16:          >::type type; 
Chris@16: };
Chris@16: 
Chris@16: // runs bfs on a queue, passing the new queue forward on recursion
Chris@16: // returns pair<visitor_state, color_state>
Chris@16: template<typename Graph, typename VertexQueue, typename VisitorOps, typename VisitorState, typename ColorMap>
Chris@16: struct bfs_run_queue {
Chris@16:     // enter vertex
Chris@16:     typedef typename mpl::front<VertexQueue>::type Vertex;
Chris@16:     typedef typename mpl::pop_front<VertexQueue>::type Tail;
Chris@16:     typedef typename VisitorOps::template examine_vertex<Vertex, Graph, VisitorState>::type examined_state;
Chris@16:     
Chris@16:     // loop over out edges
Chris@16:     typedef typename mpl::template 
Chris@16:         fold<typename mpl_graph::out_edges<Vertex, Graph>::type, 
Chris@16:              mpl::vector<examined_state, ColorMap, Tail>,
Chris@16:              bfs_run_queue_examine_edge<Graph, VisitorOps, mpl::_1, mpl::_2>
Chris@16:             >::type did_edges;
Chris@16:             
Chris@16:     typedef typename VisitorOps::template 
Chris@16:         finish_vertex<Vertex, Graph, typename mpl::at_c<did_edges, 0>::type>::type 
Chris@16:             finished_vertex; 
Chris@16:     // does map insert always overwrite?  i seem to remember this not working on msvc once
Chris@16:     typedef typename search_color_map_ops::template 
Chris@16:         set_color<Vertex, search_colors::Black, typename mpl::at_c<did_edges, 1>::type>::type 
Chris@16:             colored_vertex;
Chris@16:     typedef typename mpl::at_c<did_edges, 2>::type queued_targets;
Chris@16: 
Chris@16:     typedef typename 
Chris@16:         mpl::if_<typename mpl::empty<queued_targets>::type,
Chris@16:                  mpl::pair<finished_vertex, colored_vertex>,
Chris@16:                  bfs_run_queue<Graph, queued_targets,
Chris@16:                                VisitorOps, finished_vertex,
Chris@16:                                colored_vertex> >::type::type type;
Chris@16: };
Chris@16: 
Chris@16: } // namespace detail
Chris@16: 
Chris@16: template<typename Graph, typename VisitorOps, typename VisitorState, 
Chris@16:          typename Vertex, 
Chris@16:          typename ColorMap = create_search_color_map::type >
Chris@16: struct breadth_first_search {
Chris@16:     typedef typename VisitorOps::template 
Chris@16:         discover_vertex<Vertex, Graph, VisitorState>::type 
Chris@16:             discovered_state;
Chris@16:     typedef typename search_color_map_ops::template 
Chris@16:         set_color<Vertex, search_colors::Gray, ColorMap>::type 
Chris@16:             discovered_colors;
Chris@16:     typedef typename detail::
Chris@16:         bfs_run_queue<Graph, mpl::vector<Vertex>, 
Chris@16:                       VisitorOps, discovered_state, 
Chris@16:                       discovered_colors>::type type;
Chris@16: };
Chris@16: 
Chris@16: template<typename Graph, typename VisitorOps, typename VisitorState,
Chris@16:          typename FirstVertex = typename mpl::front<typename mpl_graph::vertices<Graph>::type>::type,
Chris@16:          typename ColorMap = create_search_color_map::type>
Chris@16: struct breadth_first_search_all : // visit "first" first, then visit any still white
Chris@16:     mpl::fold<typename mpl_graph::vertices<Graph>::type,
Chris@16:               typename breadth_first_search<Graph, VisitorOps, VisitorState, FirstVertex, ColorMap>::type,
Chris@16:               mpl::if_<boost::is_same<search_color_map_ops::template get_color<mpl::_2, mpl::second<mpl::_1> >,
Chris@16:                                       search_colors::White>,
Chris@16:                        breadth_first_search<Graph, VisitorOps, mpl::first<mpl::_1>,
Chris@16:                                             mpl::_2, mpl::second<mpl::_1> >,
Chris@16:                        mpl::_1> >   
Chris@16: {};
Chris@16: 
Chris@16: } // namespace mpl_graph
Chris@16: } // namespace msm
Chris@16: } // namespace boost
Chris@16: 
Chris@16: 
Chris@16: #endif // BOOST_MSM_MPL_GRAPH_BREADTH_FIRST_SEARCH_HPP_INCLUDED