1 // Copyright 2008-2010 Gordon Woodhull
2 // Distributed under the Boost Software License, Version 1.0.
3 // (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
4
5 #include <boost/msm/mpl_graph/depth_first_search.hpp>
6 #include <boost/msm/mpl_graph/adjacency_list_graph.hpp>
7 #include <boost/msm/mpl_graph/incidence_list_graph.hpp>
8
9 #include <iostream>
10
11 namespace mpl_graph = boost::msm::mpl_graph;
12 namespace mpl = boost::mpl;
13
14 // vertices
15 struct A{}; struct B{}; struct C{}; struct D{}; struct E{}; struct F{}; struct G{};
16
17 // edges
18 struct A_B{}; struct B_C{}; struct C_D{}; struct C_E{}; struct C_F{}; struct B_F{};
19
20
21
22 /*
23 incidence list test graph:
24 A -> B -> C -\--> D
25 \ |--> E
26 \ \--> F
27 \-----/
28 G
29 */
30
31 typedef mpl::vector<mpl::vector<A_B,A,B>,
32 mpl::vector<B_C,B,C>,
33 mpl::vector<C_D,C,D>,
34 mpl::vector<C_E,C,E>,
35 mpl::vector<C_F,C,F>,
36 mpl::vector<B_F,B,F> >
37 some_incidence_list;
38 typedef mpl_graph::incidence_list_graph<some_incidence_list> some_incidence_list_graph;
39
40
41
42 /*
43 adjacency list test graph:
44 A -> B -> C -\--> D
45 \ |--> E
46 \ \--> F
47 \-----/
48 G
49 */
50
51 typedef mpl::vector<
52 mpl::pair<A, mpl::vector<mpl::pair<A_B, B> > >,
53 mpl::pair<B, mpl::vector<mpl::pair<B_C, C>,
54 mpl::pair<B_F, F> > >,
55 mpl::pair<C, mpl::vector<mpl::pair<C_D, D>,
56 mpl::pair<C_E, E>,
57 mpl::pair<C_F, F> > >,
58 mpl::pair<G, mpl::vector<> > >
59 some_adjacency_list;
60 typedef mpl_graph::adjacency_list_graph<some_adjacency_list> some_adjacency_list_graph;
61
62
63 struct preordering_visitor : mpl_graph::dfs_default_visitor_operations {
64 template<typename Node, typename Graph, typename State>
65 struct discover_vertex :
66 mpl::push_back<State, Node>
67 {};
68 };
69
70 struct postordering_visitor : mpl_graph::dfs_default_visitor_operations {
71 template<typename Node, typename Graph, typename State>
72 struct finish_vertex :
73 mpl::push_back<State, Node>
74 {};
75 };
76
77 // adjacency list tests
78
79 // preordering, default start node (first)
80 typedef mpl::first<mpl_graph::
81 depth_first_search_all<some_adjacency_list_graph,
82 preordering_visitor,
83 mpl::vector<> >::type>::type
84 preorder_adj;
85 BOOST_MPL_ASSERT(( mpl::equal<preorder_adj::type, mpl::vector<A,B,C,D,E,F,G> > ));
86
87 // postordering, default start node
88 typedef mpl::first<mpl_graph::
89 depth_first_search_all<some_adjacency_list_graph,
90 postordering_visitor,
91 mpl::vector<> >::type>::type
92 postorder_adj;
93 BOOST_MPL_ASSERT(( mpl::equal<postorder_adj::type, mpl::vector<D,E,F,C,B,A,G> > ));
94
95 // preordering all starting at C
96 typedef mpl::first<mpl_graph::
97 depth_first_search_all<some_adjacency_list_graph,
98 preordering_visitor,
99 mpl::vector<>,
100 C>::type>::type
101 preorder_adj_all_from_c;
102 BOOST_MPL_ASSERT(( mpl::equal<preorder_adj_all_from_c::type, mpl::vector<C,D,E,F,A,B,G> > ));
103
104 // preordering just those starting at C
105 typedef mpl::first<mpl_graph::
106 depth_first_search<some_adjacency_list_graph,
107 preordering_visitor,
108 mpl::vector<>,
109 C>::type>::type
110 preorder_adj_from_c;
111 BOOST_MPL_ASSERT(( mpl::equal<preorder_adj_from_c::type, mpl::vector<C,D,E,F> > ));
112
113
114 // incidence list tests
115
116 // preordering, default start node (first)
117 typedef mpl::first<mpl_graph::
118 depth_first_search_all<some_incidence_list_graph,
119 preordering_visitor,
120 mpl::vector<> >::type>::type
121 preorder_inc;
122 BOOST_MPL_ASSERT(( mpl::equal<preorder_inc::type, mpl::vector<A,B,C,D,E,F> > ));
123
124 // postordering, default start node
125 typedef mpl::first<mpl_graph::
126 depth_first_search_all<some_incidence_list_graph,
127 postordering_visitor,
128 mpl::vector<> >::type>::type
129 postorder_inc;
130 BOOST_MPL_ASSERT(( mpl::equal<postorder_inc::type, mpl::vector<D,E,F,C,B,A> > ));
131
132 // preordering starting at C
133 typedef mpl::first<mpl_graph::
134 depth_first_search_all<some_incidence_list_graph,
135 preordering_visitor,
136 mpl::vector<>,
137 C>::type>::type
138 preorder_inc_all_from_c;
139 BOOST_MPL_ASSERT(( mpl::equal<preorder_inc_all_from_c::type, mpl::vector<C,D,E,F,A,B> > ));
140
141 // preordering starting at B
142 typedef mpl::first<mpl_graph::
143 depth_first_search<some_incidence_list_graph,
144 preordering_visitor,
145 mpl::vector<>,
146 B>::type>::type
147 preorder_inc_from_b;
148 BOOST_MPL_ASSERT(( mpl::equal<preorder_inc_from_b::type, mpl::vector<B,C,D,E,F> > ));
149
150
main()151 int main() {
152 return 0;
153 }