| // 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) |
| |
| #include <boost/msm/mpl_graph/breadth_first_search.hpp> |
| #include <boost/msm/mpl_graph/adjacency_list_graph.hpp> |
| #include <boost/msm/mpl_graph/incidence_list_graph.hpp> |
| |
| #include <iostream> |
| |
| namespace mpl_graph = boost::msm::mpl_graph; |
| namespace mpl = boost::mpl; |
| |
| // vertices |
| struct A{}; struct B{}; struct C{}; struct D{}; struct E{}; struct F{}; struct G{}; |
| |
| // edges |
| struct A_B{}; struct B_C{}; struct C_D{}; struct C_E{}; struct C_F{}; struct B_F{}; |
| |
| |
| |
| /* |
| incidence list test graph: |
| A -> B -> C -\--> D |
| \ |--> E |
| \ \--> F |
| \-----/ |
| */ |
| |
| typedef mpl::vector<mpl::vector<A_B,A,B>, |
| mpl::vector<B_C,B,C>, |
| mpl::vector<C_D,C,D>, |
| mpl::vector<C_E,C,E>, |
| mpl::vector<C_F,C,F>, |
| mpl::vector<B_F,B,F> > |
| some_incidence_list; |
| typedef mpl_graph::incidence_list_graph<some_incidence_list> some_incidence_list_graph; |
| |
| |
| |
| /* |
| adjacency list test graph: |
| A -> B -> C -\--> D |
| \ |--> E |
| \ \--> F |
| \-----/ |
| G |
| */ |
| |
| typedef mpl::vector< |
| mpl::pair<A, mpl::vector<mpl::pair<A_B, B> > >, |
| mpl::pair<B, mpl::vector<mpl::pair<B_C, C>, |
| mpl::pair<B_F, F> > >, |
| mpl::pair<C, mpl::vector<mpl::pair<C_D, D>, |
| mpl::pair<C_E, E>, |
| mpl::pair<C_F, F> > >, |
| mpl::pair<G, mpl::vector<> > > |
| some_adjacency_list; |
| typedef mpl_graph::adjacency_list_graph<some_adjacency_list> some_adjacency_list_graph; |
| |
| |
| struct preordering_visitor : mpl_graph::bfs_default_visitor_operations { |
| template<typename Vertex, typename Graph, typename State> |
| struct discover_vertex : |
| mpl::push_back<State, Vertex> |
| {}; |
| }; |
| |
| struct postordering_visitor : mpl_graph::bfs_default_visitor_operations { |
| template<typename Vertex, typename Graph, typename State> |
| struct finish_vertex : |
| mpl::push_back<State, Vertex> |
| {}; |
| }; |
| |
| struct examine_edge_visitor : mpl_graph::bfs_default_visitor_operations { |
| template<typename Edge, typename Graph, typename State> |
| struct examine_edge : |
| mpl::push_back<State, Edge> |
| {}; |
| }; |
| |
| struct tree_edge_visitor : mpl_graph::bfs_default_visitor_operations { |
| template<typename Edge, typename Graph, typename State> |
| struct tree_edge : |
| mpl::push_back<State, Edge> |
| {}; |
| }; |
| |
| // adjacency list tests |
| |
| // preordering, start from A |
| typedef mpl::first<mpl_graph:: |
| breadth_first_search<some_adjacency_list_graph, |
| preordering_visitor, |
| mpl::vector<>, |
| A>::type>::type |
| preorder_adj_a; |
| BOOST_MPL_ASSERT(( mpl::equal<preorder_adj_a::type, mpl::vector<A,B,C,F,D,E> > )); |
| |
| // examine edges, start from A |
| typedef mpl::first<mpl_graph:: |
| breadth_first_search<some_adjacency_list_graph, |
| examine_edge_visitor, |
| mpl::vector<>, |
| A>::type>::type |
| ex_edges_adj_a; |
| BOOST_MPL_ASSERT(( mpl::equal<ex_edges_adj_a::type, mpl::vector<A_B,B_C,B_F,C_D,C_E,C_F> > )); |
| |
| // tree edges, start from A |
| typedef mpl::first<mpl_graph:: |
| breadth_first_search<some_adjacency_list_graph, |
| tree_edge_visitor, |
| mpl::vector<>, |
| A>::type>::type |
| tree_edges_adj_a; |
| BOOST_MPL_ASSERT(( mpl::equal<tree_edges_adj_a::type, mpl::vector<A_B,B_C,B_F,C_D,C_E> > )); |
| |
| // preordering, search all, default start node (first) |
| typedef mpl::first<mpl_graph:: |
| breadth_first_search_all<some_adjacency_list_graph, |
| preordering_visitor, |
| mpl::vector<> >::type>::type |
| preorder_adj; |
| BOOST_MPL_ASSERT(( mpl::equal<preorder_adj::type, mpl::vector<A,B,C,F,D,E,G> > )); |
| |
| // postordering, starting at A (same as preordering because BFS fully processes one vertex b4 moving to next) |
| typedef mpl::first<mpl_graph:: |
| breadth_first_search<some_adjacency_list_graph, |
| postordering_visitor, |
| mpl::vector<>, |
| A>::type>::type |
| postorder_adj_a; |
| BOOST_MPL_ASSERT(( mpl::equal<postorder_adj_a::type, mpl::vector<A,B,C,F,D,E> > )); |
| |
| // postordering, default start node (same as preordering because BFS fully processes one vertex b4 moving to next) |
| typedef mpl::first<mpl_graph:: |
| breadth_first_search_all<some_adjacency_list_graph, |
| postordering_visitor, |
| mpl::vector<> >::type>::type |
| postorder_adj; |
| BOOST_MPL_ASSERT(( mpl::equal<postorder_adj::type, mpl::vector<A,B,C,F,D,E,G> > )); |
| |
| // preordering starting at C |
| typedef mpl::first<mpl_graph:: |
| breadth_first_search<some_adjacency_list_graph, |
| preordering_visitor, |
| mpl::vector<>, |
| C>::type>::type |
| preorder_adj_from_c; |
| BOOST_MPL_ASSERT(( mpl::equal<preorder_adj_from_c::type, mpl::vector<C,D,E,F> > )); |
| |
| // preordering, search all, starting at C |
| typedef mpl::first<mpl_graph:: |
| breadth_first_search_all<some_adjacency_list_graph, |
| preordering_visitor, |
| mpl::vector<>, |
| C>::type>::type |
| preorder_adj_from_c_all; |
| BOOST_MPL_ASSERT(( mpl::equal<preorder_adj_from_c_all::type, mpl::vector<C,D,E,F,A,B,G> > )); |
| |
| |
| // incidence list tests |
| |
| // preordering, start from A |
| typedef mpl::first<mpl_graph:: |
| breadth_first_search<some_incidence_list_graph, |
| preordering_visitor, |
| mpl::vector<>, |
| A>::type>::type |
| preorder_inc_a; |
| BOOST_MPL_ASSERT(( mpl::equal<preorder_inc_a::type, mpl::vector<A,B,C,F,D,E> > )); |
| |
| // preordering, start from C |
| typedef mpl::first<mpl_graph:: |
| breadth_first_search<some_incidence_list_graph, |
| preordering_visitor, |
| mpl::vector<>, |
| C>::type>::type |
| preorder_inc_c; |
| BOOST_MPL_ASSERT(( mpl::equal<preorder_inc_c::type, mpl::vector<C,D,E,F> > )); |
| |
| // preordering, default start node (first) |
| typedef mpl::first<mpl_graph:: |
| breadth_first_search_all<some_incidence_list_graph, |
| preordering_visitor, |
| mpl::vector<> >::type>::type |
| preorder_inc; |
| BOOST_MPL_ASSERT(( mpl::equal<preorder_inc::type, mpl::vector<A,B,C,F,D,E> > )); |
| |
| // postordering, default start node |
| typedef mpl::first<mpl_graph:: |
| breadth_first_search_all<some_incidence_list_graph, |
| postordering_visitor, |
| mpl::vector<> >::type>::type |
| postorder_inc; |
| BOOST_MPL_ASSERT(( mpl::equal<postorder_inc::type, mpl::vector<A,B,C,F,D,E> > )); |
| |
| // preordering, search all, starting at C |
| typedef mpl::first<mpl_graph:: |
| breadth_first_search_all<some_incidence_list_graph, |
| preordering_visitor, |
| mpl::vector<>, |
| C>::type>::type |
| preorder_inc_from_c; |
| BOOST_MPL_ASSERT(( mpl::equal<preorder_inc_from_c::type, mpl::vector<C,D,E,F,A,B> > )); |
| |
| |
| int main() { |
| return 0; |
| } |