123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167 |
- // Copyright 2008-2010 Gordon Woodhull
- // Distributed under the Boost Software License, Version 1.0.
- // (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
- #ifndef BOOST_MSM_MPL_GRAPH_BREADTH_FIRST_SEARCH_HPP_INCLUDED
- #define BOOST_MSM_MPL_GRAPH_BREADTH_FIRST_SEARCH_HPP_INCLUDED
- #include <boost/msm/mpl_graph/mpl_graph.hpp>
- #include <boost/mpl/has_key.hpp>
- #include <boost/mpl/insert.hpp>
- #include <boost/mpl/pair.hpp>
- #include <boost/mpl/map.hpp>
- #include <boost/mpl/has_key.hpp>
- #include <boost/mpl/pop_front.hpp>
- #include <boost/mpl/empty.hpp>
- #include <boost/mpl/remove.hpp>
- #include "search_colors.hpp"
- namespace boost {
- namespace msm {
- namespace mpl_graph {
- // bfs takes a visitor which has all the bgl-like metafunctions encapsulated in an
- // "operations" member class, and also a state. the operations are expected to return a new state
- struct bfs_default_visitor_operations {
- template<typename Vertex, typename Graph, typename State>
- struct initialize_vertex {
- typedef State type;
- };
-
- template<typename Vertex, typename Graph, typename State>
- struct discover_vertex {
- typedef State type;
- };
-
- template<typename Vertex, typename Graph, typename State>
- struct examine_vertex {
- typedef State type;
- };
-
- template<typename Vertex, typename Graph, typename State>
- struct examine_edge {
- typedef State type;
- };
-
- template<typename Edge, typename Graph, typename State>
- struct tree_edge {
- typedef State type;
- };
-
- template<typename Edge, typename Graph, typename State>
- struct non_tree_edge {
- typedef State type;
- };
-
- template<typename Edge, typename Graph, typename State>
- struct gray_target {
- typedef State type;
- };
-
- template<typename Edge, typename Graph, typename State>
- struct black_target {
- typedef State type;
- };
-
- template<typename Vertex, typename Graph, typename State>
- struct finish_vertex {
- typedef State type;
- };
- };
- namespace detail {
- template<typename Graph, typename VisitorOps, typename VCQState, typename Edge>
- struct bfs_run_queue_examine_edge {
- typedef typename VisitorOps::template examine_edge<Edge, Graph, typename mpl::at_c<VCQState, 0>::type>::type visitor_state;
- typedef typename mpl::at_c<VCQState, 1>::type color_state;
- typedef typename mpl::at_c<VCQState, 2>::type vertex_queue;
- 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,
- // unseen target: tree edge, discover target, paint it gray, and enqueue
- mpl::vector<typename VisitorOps::template discover_vertex<typename mpl_graph::target<Edge, Graph>::type, Graph,
- typename VisitorOps::template tree_edge<Edge, Graph, visitor_state>::type>::type,
- typename search_color_map_ops::template set_color<typename mpl_graph::target<Edge, Graph>::type, search_colors::Gray, color_state>::type,
- typename mpl::push_back<vertex_queue, typename mpl_graph::target<Edge, Graph>::type >::type >,
- // seen
- mpl::vector<typename mpl::if_<typename boost::is_same<typename search_color_map_ops::template get_color<mpl_graph::target<Edge, Graph>, color_state>,
- search_colors::Gray>::type,
- typename VisitorOps::template gray_target<Edge, Graph, visitor_state>::type,
- typename VisitorOps::template black_target<Edge, Graph, visitor_state>::type>::type,
- color_state,
- vertex_queue>
- >::type type;
- };
- // runs bfs on a queue, passing the new queue forward on recursion
- // returns pair<visitor_state, color_state>
- template<typename Graph, typename VertexQueue, typename VisitorOps, typename VisitorState, typename ColorMap>
- struct bfs_run_queue {
- // enter vertex
- typedef typename mpl::front<VertexQueue>::type Vertex;
- typedef typename mpl::pop_front<VertexQueue>::type Tail;
- typedef typename VisitorOps::template examine_vertex<Vertex, Graph, VisitorState>::type examined_state;
-
- // loop over out edges
- typedef typename mpl::template
- fold<typename mpl_graph::out_edges<Vertex, Graph>::type,
- mpl::vector<examined_state, ColorMap, Tail>,
- bfs_run_queue_examine_edge<Graph, VisitorOps, mpl::_1, mpl::_2>
- >::type did_edges;
-
- typedef typename VisitorOps::template
- finish_vertex<Vertex, Graph, typename mpl::at_c<did_edges, 0>::type>::type
- finished_vertex;
- // does map insert always overwrite? i seem to remember this not working on msvc once
- typedef typename search_color_map_ops::template
- set_color<Vertex, search_colors::Black, typename mpl::at_c<did_edges, 1>::type>::type
- colored_vertex;
- typedef typename mpl::at_c<did_edges, 2>::type queued_targets;
- typedef typename
- mpl::if_<typename mpl::empty<queued_targets>::type,
- mpl::pair<finished_vertex, colored_vertex>,
- bfs_run_queue<Graph, queued_targets,
- VisitorOps, finished_vertex,
- colored_vertex> >::type::type type;
- };
- } // namespace detail
- template<typename Graph, typename VisitorOps, typename VisitorState,
- typename Vertex,
- typename ColorMap = create_search_color_map::type >
- struct breadth_first_search {
- typedef typename VisitorOps::template
- discover_vertex<Vertex, Graph, VisitorState>::type
- discovered_state;
- typedef typename search_color_map_ops::template
- set_color<Vertex, search_colors::Gray, ColorMap>::type
- discovered_colors;
- typedef typename detail::
- bfs_run_queue<Graph, mpl::vector<Vertex>,
- VisitorOps, discovered_state,
- discovered_colors>::type type;
- };
- template<typename Graph, typename VisitorOps, typename VisitorState,
- typename FirstVertex = typename mpl::front<typename mpl_graph::vertices<Graph>::type>::type,
- typename ColorMap = create_search_color_map::type>
- struct breadth_first_search_all : // visit "first" first, then visit any still white
- mpl::fold<typename mpl_graph::vertices<Graph>::type,
- typename breadth_first_search<Graph, VisitorOps, VisitorState, FirstVertex, ColorMap>::type,
- mpl::if_<boost::is_same<search_color_map_ops::template get_color<mpl::_2, mpl::second<mpl::_1> >,
- search_colors::White>,
- breadth_first_search<Graph, VisitorOps, mpl::first<mpl::_1>,
- mpl::_2, mpl::second<mpl::_1> >,
- mpl::_1> >
- {};
- } // namespace mpl_graph
- } // namespace msm
- } // namespace boost
- #endif // BOOST_MSM_MPL_GRAPH_BREADTH_FIRST_SEARCH_HPP_INCLUDED
|