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/breadth_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 */
29
30 typedef mpl::vector<mpl::vector<A_B,A,B>,
31 mpl::vector<B_C,B,C>,
32 mpl::vector<C_D,C,D>,
33 mpl::vector<C_E,C,E>,
34 mpl::vector<C_F,C,F>,
35 mpl::vector<B_F,B,F> >
36 some_incidence_list;
37 typedef mpl_graph::incidence_list_graph<some_incidence_list> some_incidence_list_graph;
38
39
40
41 /*
42 adjacency list test graph:
43 A -> B -> C -\--> D
44 \ |--> E
45 \ \--> F
46 \-----/
47 G
48 */
49
50 typedef mpl::vector<
51 mpl::pair<A, mpl::vector<mpl::pair<A_B, B> > >,
52 mpl::pair<B, mpl::vector<mpl::pair<B_C, C>,
53 mpl::pair<B_F, F> > >,
54 mpl::pair<C, mpl::vector<mpl::pair<C_D, D>,
55 mpl::pair<C_E, E>,
56 mpl::pair<C_F, F> > >,
57 mpl::pair<G, mpl::vector<> > >
58 some_adjacency_list;
59 typedef mpl_graph::adjacency_list_graph<some_adjacency_list> some_adjacency_list_graph;
60
61
62 struct preordering_visitor : mpl_graph::bfs_default_visitor_operations {
63 template<typename Vertex, typename Graph, typename State>
64 struct discover_vertex :
65 mpl::push_back<State, Vertex>
66 {};
67 };
68
69 struct postordering_visitor : mpl_graph::bfs_default_visitor_operations {
70 template<typename Vertex, typename Graph, typename State>
71 struct finish_vertex :
72 mpl::push_back<State, Vertex>
73 {};
74 };
75
76 struct examine_edge_visitor : mpl_graph::bfs_default_visitor_operations {
77 template<typename Edge, typename Graph, typename State>
78 struct examine_edge :
79 mpl::push_back<State, Edge>
80 {};
81 };
82
83 struct tree_edge_visitor : mpl_graph::bfs_default_visitor_operations {
84 template<typename Edge, typename Graph, typename State>
85 struct tree_edge :
86 mpl::push_back<State, Edge>
87 {};
88 };
89
90 // adjacency list tests
91
92 // preordering, start from A
93 typedef mpl::first<mpl_graph::
94 breadth_first_search<some_adjacency_list_graph,
95 preordering_visitor,
96 mpl::vector<>,
97 A>::type>::type
98 preorder_adj_a;
99 BOOST_MPL_ASSERT(( mpl::equal<preorder_adj_a::type, mpl::vector<A,B,C,F,D,E> > ));
100
101 // examine edges, start from A
102 typedef mpl::first<mpl_graph::
103 breadth_first_search<some_adjacency_list_graph,
104 examine_edge_visitor,
105 mpl::vector<>,
106 A>::type>::type
107 ex_edges_adj_a;
108 BOOST_MPL_ASSERT(( mpl::equal<ex_edges_adj_a::type, mpl::vector<A_B,B_C,B_F,C_D,C_E,C_F> > ));
109
110 // tree edges, start from A
111 typedef mpl::first<mpl_graph::
112 breadth_first_search<some_adjacency_list_graph,
113 tree_edge_visitor,
114 mpl::vector<>,
115 A>::type>::type
116 tree_edges_adj_a;
117 BOOST_MPL_ASSERT(( mpl::equal<tree_edges_adj_a::type, mpl::vector<A_B,B_C,B_F,C_D,C_E> > ));
118
119 // preordering, search all, default start node (first)
120 typedef mpl::first<mpl_graph::
121 breadth_first_search_all<some_adjacency_list_graph,
122 preordering_visitor,
123 mpl::vector<> >::type>::type
124 preorder_adj;
125 BOOST_MPL_ASSERT(( mpl::equal<preorder_adj::type, mpl::vector<A,B,C,F,D,E,G> > ));
126
127 // postordering, starting at A (same as preordering because BFS fully processes one vertex b4 moving to next)
128 typedef mpl::first<mpl_graph::
129 breadth_first_search<some_adjacency_list_graph,
130 postordering_visitor,
131 mpl::vector<>,
132 A>::type>::type
133 postorder_adj_a;
134 BOOST_MPL_ASSERT(( mpl::equal<postorder_adj_a::type, mpl::vector<A,B,C,F,D,E> > ));
135
136 // postordering, default start node (same as preordering because BFS fully processes one vertex b4 moving to next)
137 typedef mpl::first<mpl_graph::
138 breadth_first_search_all<some_adjacency_list_graph,
139 postordering_visitor,
140 mpl::vector<> >::type>::type
141 postorder_adj;
142 BOOST_MPL_ASSERT(( mpl::equal<postorder_adj::type, mpl::vector<A,B,C,F,D,E,G> > ));
143
144 // preordering starting at C
145 typedef mpl::first<mpl_graph::
146 breadth_first_search<some_adjacency_list_graph,
147 preordering_visitor,
148 mpl::vector<>,
149 C>::type>::type
150 preorder_adj_from_c;
151 BOOST_MPL_ASSERT(( mpl::equal<preorder_adj_from_c::type, mpl::vector<C,D,E,F> > ));
152
153 // preordering, search all, starting at C
154 typedef mpl::first<mpl_graph::
155 breadth_first_search_all<some_adjacency_list_graph,
156 preordering_visitor,
157 mpl::vector<>,
158 C>::type>::type
159 preorder_adj_from_c_all;
160 BOOST_MPL_ASSERT(( mpl::equal<preorder_adj_from_c_all::type, mpl::vector<C,D,E,F,A,B,G> > ));
161
162
163 // incidence list tests
164
165 // preordering, start from A
166 typedef mpl::first<mpl_graph::
167 breadth_first_search<some_incidence_list_graph,
168 preordering_visitor,
169 mpl::vector<>,
170 A>::type>::type
171 preorder_inc_a;
172 BOOST_MPL_ASSERT(( mpl::equal<preorder_inc_a::type, mpl::vector<A,B,C,F,D,E> > ));
173
174 // preordering, start from C
175 typedef mpl::first<mpl_graph::
176 breadth_first_search<some_incidence_list_graph,
177 preordering_visitor,
178 mpl::vector<>,
179 C>::type>::type
180 preorder_inc_c;
181 BOOST_MPL_ASSERT(( mpl::equal<preorder_inc_c::type, mpl::vector<C,D,E,F> > ));
182
183 // preordering, default start node (first)
184 typedef mpl::first<mpl_graph::
185 breadth_first_search_all<some_incidence_list_graph,
186 preordering_visitor,
187 mpl::vector<> >::type>::type
188 preorder_inc;
189 BOOST_MPL_ASSERT(( mpl::equal<preorder_inc::type, mpl::vector<A,B,C,F,D,E> > ));
190
191 // postordering, default start node
192 typedef mpl::first<mpl_graph::
193 breadth_first_search_all<some_incidence_list_graph,
194 postordering_visitor,
195 mpl::vector<> >::type>::type
196 postorder_inc;
197 BOOST_MPL_ASSERT(( mpl::equal<postorder_inc::type, mpl::vector<A,B,C,F,D,E> > ));
198
199 // preordering, search all, starting at C
200 typedef mpl::first<mpl_graph::
201 breadth_first_search_all<some_incidence_list_graph,
202 preordering_visitor,
203 mpl::vector<>,
204 C>::type>::type
205 preorder_inc_from_c;
206 BOOST_MPL_ASSERT(( mpl::equal<preorder_inc_from_c::type, mpl::vector<C,D,E,F,A,B> > ));
207
208
main()209 int main() {
210 return 0;
211 }