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_DEPTH_FIRST_SEARCH_HPP_INCLUDED
Chris@16: #define BOOST_MSM_MPL_GRAPH_DEPTH_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: 
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: // dfs 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: // in addition, the visitor operations are expected to update the colors of vertices
Chris@16: // and need to support a new metafunction get_color<Vertex, State>
Chris@16: 
Chris@16: struct dfs_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 finish_vertex {
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 back_edge {
Chris@16:         typedef State type;
Chris@16:     };
Chris@16:     
Chris@16:     template<typename Edge, typename Graph, typename State>
Chris@16:     struct forward_or_cross_edge {
Chris@16:         typedef State type;
Chris@16:     };  
Chris@16: };
Chris@16: 
Chris@16: // requires IncidenceGraph
Chris@16: // returns pair<VisitorState, ColorState>
Chris@16: template<typename Graph, typename VisitorOps, typename VisitorState,
Chris@16:          typename Vertex, 
Chris@16:          typename ColorState = create_search_color_map::type >
Chris@16: struct depth_first_search {
Chris@16:     // enter vertex
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, ColorState>::type 
Chris@16:             discovered_colors;
Chris@16:             
Chris@16:     // loop over out edges
Chris@16:     typedef typename 
Chris@16:         mpl::fold<typename mpl_graph::out_edges<Vertex, Graph>::type, 
Chris@16:                   mpl::pair<discovered_state, discovered_colors>,
Chris@16:                   mpl::if_<boost::is_same<search_color_map_ops::get_color<mpl_graph::target<mpl::_2, Graph>, mpl::second<mpl::_1> >, 
Chris@16:                                           search_colors::White>,
Chris@16:                            // unseen target: recurse
Chris@16:                            depth_first_search<Graph, 
Chris@16:                                               VisitorOps, typename VisitorOps::template tree_edge<mpl::_2, Graph, mpl::first<mpl::_1> >, 
Chris@16:                                               mpl_graph::target<mpl::_2, Graph>, 
Chris@16:                                               mpl::second<mpl::_1> >,
Chris@16:                            // seen: back or forward edge
Chris@16:                            mpl::pair<mpl::if_<boost::is_same<typename search_color_map_ops::template 
Chris@16:                                                  get_color<mpl_graph::target<mpl::_2, Graph>, mpl::second<mpl::_1 > >, 
Chris@16:                                                  search_colors::Gray>,
Chris@16:                                               typename VisitorOps::template back_edge<mpl::_2, Graph, mpl::first<mpl::_1> >,
Chris@16:                                               typename VisitorOps::template forward_or_cross_edge<mpl::_2, Graph, mpl::first<mpl::_1> > >,  // Black
Chris@16:                                      mpl::second<mpl::_1> > > 
Chris@16:                  >::type after_outedges;
Chris@16:                  
Chris@16:     // leave vertex, and done!
Chris@16:     typedef mpl::pair<typename VisitorOps::template finish_vertex<Vertex, Graph, typename mpl::first<after_outedges>::type >::type,
Chris@16:                       typename search_color_map_ops::template set_color<Vertex, search_colors::Black, typename mpl::second<after_outedges>::type>::type> type;
Chris@16: };
Chris@16: 
Chris@16: // requires IncidenceGraph, VertexListGraph
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 ColorState = create_search_color_map::type>
Chris@16: struct depth_first_search_all : // visit first then rest
Chris@16:     mpl::fold<typename mpl_graph::vertices<Graph>::type,
Chris@16:               typename depth_first_search<Graph, 
Chris@16:                                           VisitorOps, VisitorState, 
Chris@16:                                           FirstVertex, 
Chris@16:                                           ColorState>::type, 
Chris@16:               mpl::if_<boost::is_same<search_color_map_ops::get_color<mpl::_2, mpl::second<mpl::_1> >,
Chris@16:                                       search_colors::White>, // visit any yet unvisited
Chris@16:                        depth_first_search<Graph,
Chris@16:                                  VisitorOps, mpl::first<mpl::_1>,
Chris@16:                                  mpl::_2,
Chris@16:                                  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_DEPTH_FIRST_SEARCH_HPP_INCLUDED