msm/mpl_graph/depth_first_search.hpp

0001 // Copyright 2008-2010 Gordon Woodhull
0002 // Distributed under the Boost Software License, Version 1.0.
0003 // (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0004
0005 #ifndef BOOST_MSM_MPL_GRAPH_DEPTH_FIRST_SEARCH_HPP_INCLUDED
0006 #define BOOST_MSM_MPL_GRAPH_DEPTH_FIRST_SEARCH_HPP_INCLUDED
0007
0008 #include <boost/msm/mpl_graph/mpl_graph.hpp>
0009
0010 #include <boost/mpl/has_key.hpp>
0011 #include <boost/mpl/insert.hpp>
0012 #include <boost/mpl/pair.hpp>
0013 #include <boost/mpl/map.hpp>
0014 #include <boost/mpl/has_key.hpp>
0015
0016 #include "search_colors.hpp"
0017
0018 namespace boost {
0019 namespace msm {
0020 namespace mpl_graph {
0021
0022 // dfs takes a visitor which has all the bgl-like metafunctions encapsulated in an
0023 // "operations" member class, and also a state.  the operations are expected to return a new state
0024 // in addition, the visitor operations are expected to update the colors of vertices
0025 // and need to support a new metafunction get_color<Vertex, State>
0026
0027 struct dfs_default_visitor_operations {
0028     template<typename Vertex, typename Graph, typename State>
0029     struct initialize_vertex {
0030         typedef State type;
0031     };
0032
0033     template<typename Vertex, typename Graph, typename State>
0034     struct discover_vertex {
0035         typedef State type;
0036     };
0037
0038     template<typename Vertex, typename Graph, typename State>
0039     struct finish_vertex {
0040         typedef State type;
0041     };
0042
0043     template<typename Edge, typename Graph, typename State>
0044     struct tree_edge {
0045         typedef State type;
0046     };
0047
0048     template<typename Edge, typename Graph, typename State>
0049     struct back_edge {
0050         typedef State type;
0051     };
0052
0053     template<typename Edge, typename Graph, typename State>
0054     struct forward_or_cross_edge {
0055         typedef State type;
0056     };
0057 };
0058
0059 // requires IncidenceGraph
0060 // returns pair<VisitorState, ColorState>
0061 template<typename Graph, typename VisitorOps, typename VisitorState,
0062          typename Vertex,
0063          typename ColorState = create_search_color_map::type >
0064 struct depth_first_search {
0065     // enter vertex
0066     typedef typename VisitorOps::template
0067         discover_vertex<Vertex, Graph, VisitorState>::type
0068             discovered_state;
0069     typedef typename search_color_map_ops::template
0070         set_color<Vertex, search_colors::Gray, ColorState>::type
0071             discovered_colors;
0072
0073     // loop over out edges
0074     typedef typename
0075         mpl::fold<typename mpl_graph::out_edges<Vertex, Graph>::type,
0076                   mpl::pair<discovered_state, discovered_colors>,
0077                   mpl::if_<boost::is_same<search_color_map_ops::get_color<mpl_graph::target<mpl::_2, Graph>, mpl::second<mpl::_1> >,
0078                                           search_colors::White>,
0079                            // unseen target: recurse
0080                            depth_first_search<Graph,
0081                                               VisitorOps, typename VisitorOps::template tree_edge<mpl::_2, Graph, mpl::first<mpl::_1> >,
0082                                               mpl_graph::target<mpl::_2, Graph>,
0083                                               mpl::second<mpl::_1> >,
0084                            // seen: back or forward edge
0085                            mpl::pair<mpl::if_<boost::is_same<typename search_color_map_ops::template
0086                                                  get_color<mpl_graph::target<mpl::_2, Graph>, mpl::second<mpl::_1 > >,
0087                                                  search_colors::Gray>,
0088                                               typename VisitorOps::template back_edge<mpl::_2, Graph, mpl::first<mpl::_1> >,
0089                                               typename VisitorOps::template forward_or_cross_edge<mpl::_2, Graph, mpl::first<mpl::_1> > >,  // Black
0090                                      mpl::second<mpl::_1> > >
0091                  >::type after_outedges;
0092
0093     // leave vertex, and done!
0094     typedef mpl::pair<typename VisitorOps::template finish_vertex<Vertex, Graph, typename mpl::first<after_outedges>::type >::type,
0095                       typename search_color_map_ops::template set_color<Vertex, search_colors::Black, typename mpl::second<after_outedges>::type>::type> type;
0096 };
0097
0098 // requires IncidenceGraph, VertexListGraph
0099 template<typename Graph, typename VisitorOps, typename VisitorState,
0100          typename FirstVertex = typename mpl::front<typename mpl_graph::vertices<Graph>::type>::type,
0101          typename ColorState = create_search_color_map::type>
0102 struct depth_first_search_all : // visit first then rest
0103     mpl::fold<typename mpl_graph::vertices<Graph>::type,
0104               typename depth_first_search<Graph,
0105                                           VisitorOps, VisitorState,
0106                                           FirstVertex,
0107                                           ColorState>::type,
0108               mpl::if_<boost::is_same<search_color_map_ops::get_color<mpl::_2, mpl::second<mpl::_1> >,
0109                                       search_colors::White>, // visit any yet unvisited
0110                        depth_first_search<Graph,
0111                                  VisitorOps, mpl::first<mpl::_1>,
0112                                  mpl::_2,
0113                                  mpl::second<mpl::_1> >,
0114                        mpl::_1> >
0115 {};
0116
0117 } // namespace mpl_graph
0118 } // namespace msm
0119 } // namespace boost
0120
0121
0122 #endif // BOOST_MSM_MPL_GRAPH_DEPTH_FIRST_SEARCH_HPP_INCLUDED