msm/mpl_graph/breadth_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_BREADTH_FIRST_SEARCH_HPP_INCLUDED
0006 #define BOOST_MSM_MPL_GRAPH_BREADTH_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 #include <boost/mpl/pop_front.hpp>
0016 #include <boost/mpl/empty.hpp>
0017 #include <boost/mpl/remove.hpp>
0018
0019 #include "search_colors.hpp"
0020
0021 namespace boost {
0022 namespace msm {
0023 namespace mpl_graph {
0024
0025 // bfs takes a visitor which has all the bgl-like metafunctions encapsulated in an
0026 // "operations" member class, and also a state.  the operations are expected to return a new state
0027 struct bfs_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 examine_vertex {
0040         typedef State type;
0041     };
0042
0043     template<typename Vertex, typename Graph, typename State>
0044     struct examine_edge {
0045         typedef State type;
0046     };
0047
0048     template<typename Edge, typename Graph, typename State>
0049     struct tree_edge {
0050         typedef State type;
0051     };
0052
0053     template<typename Edge, typename Graph, typename State>
0054     struct non_tree_edge {
0055         typedef State type;
0056     };
0057
0058     template<typename Edge, typename Graph, typename State>
0059     struct gray_target {
0060         typedef State type;
0061     };
0062
0063     template<typename Edge, typename Graph, typename State>
0064     struct black_target {
0065         typedef State type;
0066     };
0067
0068     template<typename Vertex, typename Graph, typename State>
0069     struct finish_vertex {
0070         typedef State type;
0071     };
0072 };
0073
0074 namespace detail {
0075
0076 template<typename Graph, typename VisitorOps, typename VCQState, typename Edge>
0077 struct bfs_run_queue_examine_edge {
0078     typedef typename VisitorOps::template examine_edge<Edge, Graph, typename mpl::at_c<VCQState, 0>::type>::type visitor_state;
0079     typedef typename mpl::at_c<VCQState, 1>::type color_state;
0080     typedef typename mpl::at_c<VCQState, 2>::type vertex_queue;
0081
0082     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,
0083          // unseen target: tree edge, discover target, paint it gray, and enqueue
0084          mpl::vector<typename VisitorOps::template discover_vertex<typename mpl_graph::target<Edge, Graph>::type, Graph,
0085                                                                             typename VisitorOps::template tree_edge<Edge, Graph, visitor_state>::type>::type,
0086                      typename search_color_map_ops::template set_color<typename mpl_graph::target<Edge, Graph>::type, search_colors::Gray, color_state>::type,
0087                      typename mpl::push_back<vertex_queue, typename mpl_graph::target<Edge, Graph>::type >::type >,
0088          // seen
0089          mpl::vector<typename mpl::if_<typename boost::is_same<typename search_color_map_ops::template get_color<mpl_graph::target<Edge, Graph>, color_state>,
0090                                              search_colors::Gray>::type,
0091                               typename VisitorOps::template gray_target<Edge, Graph, visitor_state>::type,
0092                               typename VisitorOps::template black_target<Edge, Graph, visitor_state>::type>::type,
0093                      color_state,
0094                      vertex_queue>
0095          >::type type;
0096 };
0097
0098 // runs bfs on a queue, passing the new queue forward on recursion
0099 // returns pair<visitor_state, color_state>
0100 template<typename Graph, typename VertexQueue, typename VisitorOps, typename VisitorState, typename ColorMap>
0101 struct bfs_run_queue {
0102     // enter vertex
0103     typedef typename mpl::front<VertexQueue>::type Vertex;
0104     typedef typename mpl::pop_front<VertexQueue>::type Tail;
0105     typedef typename VisitorOps::template examine_vertex<Vertex, Graph, VisitorState>::type examined_state;
0106
0107     // loop over out edges
0108     typedef typename mpl::template
0109         fold<typename mpl_graph::out_edges<Vertex, Graph>::type,
0110              mpl::vector<examined_state, ColorMap, Tail>,
0111              bfs_run_queue_examine_edge<Graph, VisitorOps, mpl::_1, mpl::_2>
0112             >::type did_edges;
0113
0114     typedef typename VisitorOps::template
0115         finish_vertex<Vertex, Graph, typename mpl::at_c<did_edges, 0>::type>::type
0116             finished_vertex;
0117     // does map insert always overwrite?  i seem to remember this not working on msvc once
0118     typedef typename search_color_map_ops::template
0119         set_color<Vertex, search_colors::Black, typename mpl::at_c<did_edges, 1>::type>::type
0120             colored_vertex;
0121     typedef typename mpl::at_c<did_edges, 2>::type queued_targets;
0122
0123     typedef typename
0124         mpl::if_<typename mpl::empty<queued_targets>::type,
0125                  mpl::pair<finished_vertex, colored_vertex>,
0126                  bfs_run_queue<Graph, queued_targets,
0127                                VisitorOps, finished_vertex,
0128                                colored_vertex> >::type::type type;
0129 };
0130
0131 } // namespace detail
0132
0133 template<typename Graph, typename VisitorOps, typename VisitorState,
0134          typename Vertex,
0135          typename ColorMap = create_search_color_map::type >
0136 struct breadth_first_search {
0137     typedef typename VisitorOps::template
0138         discover_vertex<Vertex, Graph, VisitorState>::type
0139             discovered_state;
0140     typedef typename search_color_map_ops::template
0141         set_color<Vertex, search_colors::Gray, ColorMap>::type
0142             discovered_colors;
0143     typedef typename detail::
0144         bfs_run_queue<Graph, mpl::vector<Vertex>,
0145                       VisitorOps, discovered_state,
0146                       discovered_colors>::type type;
0147 };
0148
0149 template<typename Graph, typename VisitorOps, typename VisitorState,
0150          typename FirstVertex = typename mpl::front<typename mpl_graph::vertices<Graph>::type>::type,
0151          typename ColorMap = create_search_color_map::type>
0152 struct breadth_first_search_all : // visit "first" first, then visit any still white
0153     mpl::fold<typename mpl_graph::vertices<Graph>::type,
0154               typename breadth_first_search<Graph, VisitorOps, VisitorState, FirstVertex, ColorMap>::type,
0155               mpl::if_<boost::is_same<search_color_map_ops::template get_color<mpl::_2, mpl::second<mpl::_1> >,
0156                                       search_colors::White>,
0157                        breadth_first_search<Graph, VisitorOps, mpl::first<mpl::_1>,
0158                                             mpl::_2, mpl::second<mpl::_1> >,
0159                        mpl::_1> >
0160 {};
0161
0162 } // namespace mpl_graph
0163 } // namespace msm
0164 } // namespace boost
0165
0166
0167 #endif // BOOST_MSM_MPL_GRAPH_BREADTH_FIRST_SEARCH_HPP_INCLUDED