1 // Copyright 2008-2010 Gordon Woodhull 2 // Distributed under the Boost Software License, Version 1.0. 3 // (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 4 5 #ifndef BOOST_MSM_MPL_GRAPH_BREADTH_FIRST_SEARCH_HPP_INCLUDED 6 #define BOOST_MSM_MPL_GRAPH_BREADTH_FIRST_SEARCH_HPP_INCLUDED 7 8 #include <boost/msm/mpl_graph/mpl_graph.hpp> 9 10 #include <boost/mpl/has_key.hpp> 11 #include <boost/mpl/insert.hpp> 12 #include <boost/mpl/pair.hpp> 13 #include <boost/mpl/map.hpp> 14 #include <boost/mpl/has_key.hpp> 15 #include <boost/mpl/pop_front.hpp> 16 #include <boost/mpl/empty.hpp> 17 #include <boost/mpl/remove.hpp> 18 19 #include "search_colors.hpp" 20 21 namespace boost { 22 namespace msm { 23 namespace mpl_graph { 24 25 // bfs takes a visitor which has all the bgl-like metafunctions encapsulated in an 26 // "operations" member class, and also a state. the operations are expected to return a new state 27 struct bfs_default_visitor_operations { 28 template<typename Vertex, typename Graph, typename State> 29 struct initialize_vertex { 30 typedef State type; 31 }; 32 33 template<typename Vertex, typename Graph, typename State> 34 struct discover_vertex { 35 typedef State type; 36 }; 37 38 template<typename Vertex, typename Graph, typename State> 39 struct examine_vertex { 40 typedef State type; 41 }; 42 43 template<typename Vertex, typename Graph, typename State> 44 struct examine_edge { 45 typedef State type; 46 }; 47 48 template<typename Edge, typename Graph, typename State> 49 struct tree_edge { 50 typedef State type; 51 }; 52 53 template<typename Edge, typename Graph, typename State> 54 struct non_tree_edge { 55 typedef State type; 56 }; 57 58 template<typename Edge, typename Graph, typename State> 59 struct gray_target { 60 typedef State type; 61 }; 62 63 template<typename Edge, typename Graph, typename State> 64 struct black_target { 65 typedef State type; 66 }; 67 68 template<typename Vertex, typename Graph, typename State> 69 struct finish_vertex { 70 typedef State type; 71 }; 72 }; 73 74 namespace detail { 75 76 template<typename Graph, typename VisitorOps, typename VCQState, typename Edge> 77 struct bfs_run_queue_examine_edge { 78 typedef typename VisitorOps::template examine_edge<Edge, Graph, typename mpl::at_c<VCQState, 0>::type>::type visitor_state; 79 typedef typename mpl::at_c<VCQState, 1>::type color_state; 80 typedef typename mpl::at_c<VCQState, 2>::type vertex_queue; 81 82 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, 83 // unseen target: tree edge, discover target, paint it gray, and enqueue 84 mpl::vector<typename VisitorOps::template discover_vertex<typename mpl_graph::target<Edge, Graph>::type, Graph, 85 typename VisitorOps::template tree_edge<Edge, Graph, visitor_state>::type>::type, 86 typename search_color_map_ops::template set_color<typename mpl_graph::target<Edge, Graph>::type, search_colors::Gray, color_state>::type, 87 typename mpl::push_back<vertex_queue, typename mpl_graph::target<Edge, Graph>::type >::type >, 88 // seen 89 mpl::vector<typename mpl::if_<typename boost::is_same<typename search_color_map_ops::template get_color<mpl_graph::target<Edge, Graph>, color_state>, 90 search_colors::Gray>::type, 91 typename VisitorOps::template gray_target<Edge, Graph, visitor_state>::type, 92 typename VisitorOps::template black_target<Edge, Graph, visitor_state>::type>::type, 93 color_state, 94 vertex_queue> 95 >::type type; 96 }; 97 98 // runs bfs on a queue, passing the new queue forward on recursion 99 // returns pair<visitor_state, color_state> 100 template<typename Graph, typename VertexQueue, typename VisitorOps, typename VisitorState, typename ColorMap> 101 struct bfs_run_queue { 102 // enter vertex 103 typedef typename mpl::front<VertexQueue>::type Vertex; 104 typedef typename mpl::pop_front<VertexQueue>::type Tail; 105 typedef typename VisitorOps::template examine_vertex<Vertex, Graph, VisitorState>::type examined_state; 106 107 // loop over out edges 108 typedef typename mpl::template 109 fold<typename mpl_graph::out_edges<Vertex, Graph>::type, 110 mpl::vector<examined_state, ColorMap, Tail>, 111 bfs_run_queue_examine_edge<Graph, VisitorOps, mpl::_1, mpl::_2> 112 >::type did_edges; 113 114 typedef typename VisitorOps::template 115 finish_vertex<Vertex, Graph, typename mpl::at_c<did_edges, 0>::type>::type 116 finished_vertex; 117 // does map insert always overwrite? i seem to remember this not working on msvc once 118 typedef typename search_color_map_ops::template 119 set_color<Vertex, search_colors::Black, typename mpl::at_c<did_edges, 1>::type>::type 120 colored_vertex; 121 typedef typename mpl::at_c<did_edges, 2>::type queued_targets; 122 123 typedef typename 124 mpl::if_<typename mpl::empty<queued_targets>::type, 125 mpl::pair<finished_vertex, colored_vertex>, 126 bfs_run_queue<Graph, queued_targets, 127 VisitorOps, finished_vertex, 128 colored_vertex> >::type::type type; 129 }; 130 131 } // namespace detail 132 133 template<typename Graph, typename VisitorOps, typename VisitorState, 134 typename Vertex, 135 typename ColorMap = create_search_color_map::type > 136 struct breadth_first_search { 137 typedef typename VisitorOps::template 138 discover_vertex<Vertex, Graph, VisitorState>::type 139 discovered_state; 140 typedef typename search_color_map_ops::template 141 set_color<Vertex, search_colors::Gray, ColorMap>::type 142 discovered_colors; 143 typedef typename detail:: 144 bfs_run_queue<Graph, mpl::vector<Vertex>, 145 VisitorOps, discovered_state, 146 discovered_colors>::type type; 147 }; 148 149 template<typename Graph, typename VisitorOps, typename VisitorState, 150 typename FirstVertex = typename mpl::front<typename mpl_graph::vertices<Graph>::type>::type, 151 typename ColorMap = create_search_color_map::type> 152 struct breadth_first_search_all : // visit "first" first, then visit any still white 153 mpl::fold<typename mpl_graph::vertices<Graph>::type, 154 typename breadth_first_search<Graph, VisitorOps, VisitorState, FirstVertex, ColorMap>::type, 155 mpl::if_<boost::is_same<search_color_map_ops::template get_color<mpl::_2, mpl::second<mpl::_1> >, 156 search_colors::White>, 157 breadth_first_search<Graph, VisitorOps, mpl::first<mpl::_1>, 158 mpl::_2, mpl::second<mpl::_1> >, 159 mpl::_1> > 160 {}; 161 162 } // namespace mpl_graph 163 } // namespace msm 164 } // namespace boost 165 166 167 #endif // BOOST_MSM_MPL_GRAPH_BREADTH_FIRST_SEARCH_HPP_INCLUDED 168