ceph/src/boost/boost/msm/mpl_graph/depth_first_search.hpp

   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