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