Name	Size	Mode	Actions
detail/	-	0755	rm
adjacency_list_graph.hpp	1113	0644	editdlrm
breadth_first_search.hpp	7218	0644	editdlrm
depth_first_search.hpp	5412	0644	editdlrm
incidence_list_graph.hpp	1070	0644	editdlrm
mpl_graph.hpp	3783	0644	editdlrm
mpl_utils.hpp	1738	0644	editdlrm
search_colors.hpp	1001	0644	editdlrm

// 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 #include #include #include #include #include #include #include #include #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 struct initialize_vertex { typedef State type; }; template struct discover_vertex { typedef State type; }; template struct examine_vertex { typedef State type; }; template struct examine_edge { typedef State type; }; template struct tree_edge { typedef State type; }; template struct non_tree_edge { typedef State type; }; template struct gray_target { typedef State type; }; template struct black_target { typedef State type; }; template struct finish_vertex { typedef State type; }; }; namespace detail { template struct bfs_run_queue_examine_edge { typedef typename VisitorOps::template examine_edge::type>::type visitor_state; typedef typename mpl::at_c::type color_state; typedef typename mpl::at_c::type vertex_queue; typedef typename mpl::if_::type, color_state>::type, search_colors::White>::type, // unseen target: tree edge, discover target, paint it gray, and enqueue mpl::vector::type, Graph, typename VisitorOps::template tree_edge::type>::type, typename search_color_map_ops::template set_color::type, search_colors::Gray, color_state>::type, typename mpl::push_back::type >::type >, // seen mpl::vector, color_state>, search_colors::Gray>::type, typename VisitorOps::template gray_target::type, typename VisitorOps::template black_target::type>::type, color_state, vertex_queue> >::type type; }; // runs bfs on a queue, passing the new queue forward on recursion // returns pair template struct bfs_run_queue { // enter vertex typedef typename mpl::front::type Vertex; typedef typename mpl::pop_front::type Tail; typedef typename VisitorOps::template examine_vertex::type examined_state; // loop over out edges typedef typename mpl::template fold::type, mpl::vector, bfs_run_queue_examine_edge >::type did_edges; typedef typename VisitorOps::template finish_vertex::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::type>::type colored_vertex; typedef typename mpl::at_c::type queued_targets; typedef typename mpl::if_::type, mpl::pair, bfs_run_queue >::type::type type; }; } // namespace detail template struct breadth_first_search { typedef typename VisitorOps::template discover_vertex::type discovered_state; typedef typename search_color_map_ops::template set_color::type discovered_colors; typedef typename detail:: bfs_run_queue, VisitorOps, discovered_state, discovered_colors>::type type; }; template::type>::type, typename ColorMap = create_search_color_map::type> struct breadth_first_search_all : // visit "first" first, then visit any still white mpl::fold::type, typename breadth_first_search::type, mpl::if_ >, search_colors::White>, breadth_first_search, mpl::_2, mpl::second >, mpl::_1> > {}; } // namespace mpl_graph } // namespace msm } // namespace boost #endif // BOOST_MSM_MPL_GRAPH_BREADTH_FIRST_SEARCH_HPP_INCLUDED