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_DEPTH_FIRST_SEARCH_HPP_INCLUDED 6 #define BOOST_MSM_MPL_GRAPH_DEPTH_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 16 #include "search_colors.hpp" 17 18 namespace boost { 19 namespace msm { 20 namespace mpl_graph { 21 22 // dfs takes a visitor which has all the bgl-like metafunctions encapsulated in an 23 // "operations" member class, and also a state. the operations are expected to return a new state 24 // in addition, the visitor operations are expected to update the colors of vertices 25 // and need to support a new metafunction get_color<Vertex, State> 26 27 struct dfs_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 finish_vertex { 40 typedef State type; 41 }; 42 43 template<typename Edge, typename Graph, typename State> 44 struct tree_edge { 45 typedef State type; 46 }; 47 48 template<typename Edge, typename Graph, typename State> 49 struct back_edge { 50 typedef State type; 51 }; 52 53 template<typename Edge, typename Graph, typename State> 54 struct forward_or_cross_edge { 55 typedef State type; 56 }; 57 }; 58 59 // requires IncidenceGraph 60 // returns pair<VisitorState, ColorState> 61 template<typename Graph, typename VisitorOps, typename VisitorState, 62 typename Vertex, 63 typename ColorState = create_search_color_map::type > 64 struct depth_first_search { 65 // enter vertex 66 typedef typename VisitorOps::template 67 discover_vertex<Vertex, Graph, VisitorState>::type 68 discovered_state; 69 typedef typename search_color_map_ops::template 70 set_color<Vertex, search_colors::Gray, ColorState>::type 71 discovered_colors; 72 73 // loop over out edges 74 typedef typename 75 mpl::fold<typename mpl_graph::out_edges<Vertex, Graph>::type, 76 mpl::pair<discovered_state, discovered_colors>, 77 mpl::if_<boost::is_same<search_color_map_ops::get_color<mpl_graph::target<mpl::_2, Graph>, mpl::second<mpl::_1> >, 78 search_colors::White>, 79 // unseen target: recurse 80 depth_first_search<Graph, 81 VisitorOps, typename VisitorOps::template tree_edge<mpl::_2, Graph, mpl::first<mpl::_1> >, 82 mpl_graph::target<mpl::_2, Graph>, 83 mpl::second<mpl::_1> >, 84 // seen: back or forward edge 85 mpl::pair<mpl::if_<boost::is_same<typename search_color_map_ops::template 86 get_color<mpl_graph::target<mpl::_2, Graph>, mpl::second<mpl::_1 > >, 87 search_colors::Gray>, 88 typename VisitorOps::template back_edge<mpl::_2, Graph, mpl::first<mpl::_1> >, 89 typename VisitorOps::template forward_or_cross_edge<mpl::_2, Graph, mpl::first<mpl::_1> > >, // Black 90 mpl::second<mpl::_1> > > 91 >::type after_outedges; 92 93 // leave vertex, and done! 94 typedef mpl::pair<typename VisitorOps::template finish_vertex<Vertex, Graph, typename mpl::first<after_outedges>::type >::type, 95 typename search_color_map_ops::template set_color<Vertex, search_colors::Black, typename mpl::second<after_outedges>::type>::type> type; 96 }; 97 98 // requires IncidenceGraph, VertexListGraph 99 template<typename Graph, typename VisitorOps, typename VisitorState, 100 typename FirstVertex = typename mpl::front<typename mpl_graph::vertices<Graph>::type>::type, 101 typename ColorState = create_search_color_map::type> 102 struct depth_first_search_all : // visit first then rest 103 mpl::fold<typename mpl_graph::vertices<Graph>::type, 104 typename depth_first_search<Graph, 105 VisitorOps, VisitorState, 106 FirstVertex, 107 ColorState>::type, 108 mpl::if_<boost::is_same<search_color_map_ops::get_color<mpl::_2, mpl::second<mpl::_1> >, 109 search_colors::White>, // visit any yet unvisited 110 depth_first_search<Graph, 111 VisitorOps, mpl::first<mpl::_1>, 112 mpl::_2, 113 mpl::second<mpl::_1> >, 114 mpl::_1> > 115 {}; 116 117 } // namespace mpl_graph 118 } // namespace msm 119 } // namespace boost 120 121 122 #endif // BOOST_MSM_MPL_GRAPH_DEPTH_FIRST_SEARCH_HPP_INCLUDED 123