// 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
|
