// 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/depth_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 \-----/ G */ 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::dfs_default_visitor_operations { template<typename Node, typename Graph, typename State> struct discover_vertex : mpl::push_back<State, Node> {}; }; struct postordering_visitor : mpl_graph::dfs_default_visitor_operations { template<typename Node, typename Graph, typename State> struct finish_vertex : mpl::push_back<State, Node> {}; }; // adjacency list tests // preordering, default start node (first) typedef mpl::first<mpl_graph:: depth_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,D,E,F,G> > )); // postordering, default start node typedef mpl::first<mpl_graph:: depth_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<D,E,F,C,B,A,G> > )); // preordering all starting at C typedef mpl::first<mpl_graph:: depth_first_search_all<some_adjacency_list_graph, preordering_visitor, mpl::vector<>, C>::type>::type preorder_adj_all_from_c; BOOST_MPL_ASSERT(( mpl::equal<preorder_adj_all_from_c::type, mpl::vector<C,D,E,F,A,B,G> > )); // preordering just those starting at C typedef mpl::first<mpl_graph:: depth_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> > )); // incidence list tests // preordering, default start node (first) typedef mpl::first<mpl_graph:: depth_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,D,E,F> > )); // postordering, default start node typedef mpl::first<mpl_graph:: depth_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<D,E,F,C,B,A> > )); // preordering starting at C typedef mpl::first<mpl_graph:: depth_first_search_all<some_incidence_list_graph, preordering_visitor, mpl::vector<>, C>::type>::type preorder_inc_all_from_c; BOOST_MPL_ASSERT(( mpl::equal<preorder_inc_all_from_c::type, mpl::vector<C,D,E,F,A,B> > )); // preordering starting at B typedef mpl::first<mpl_graph:: depth_first_search<some_incidence_list_graph, preordering_visitor, mpl::vector<>, B>::type>::type preorder_inc_from_b; BOOST_MPL_ASSERT(( mpl::equal<preorder_inc_from_b::type, mpl::vector<B,C,D,E,F> > )); int main() { return 0; }