123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211 |
- // 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;
- }
|