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
11namespace mpl_graph = boost::msm::mpl_graph;
12namespace mpl = boost::mpl;
13
14// vertices
15struct A{}; struct B{}; struct C{}; struct D{}; struct E{}; struct F{}; struct G{};
16
17// edges
18struct 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
31typedef 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;
38typedef 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
51typedef 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;
60typedef mpl_graph::adjacency_list_graph<some_adjacency_list> some_adjacency_list_graph;
61
62
63struct 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
70struct 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)
80typedef mpl::first<mpl_graph::
81 depth_first_search_all<some_adjacency_list_graph,
82 preordering_visitor,
83 mpl::vector<> >::type>::type
84 preorder_adj;
85BOOST_MPL_ASSERT(( mpl::equal<preorder_adj::type, mpl::vector<A,B,C,D,E,F,G> > ));
86
87// postordering, default start node
88typedef mpl::first<mpl_graph::
89 depth_first_search_all<some_adjacency_list_graph,
90 postordering_visitor,
91 mpl::vector<> >::type>::type
92 postorder_adj;
93BOOST_MPL_ASSERT(( mpl::equal<postorder_adj::type, mpl::vector<D,E,F,C,B,A,G> > ));
94
95// preordering all starting at C
96typedef 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;
102BOOST_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
105typedef 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;
111BOOST_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)
117typedef mpl::first<mpl_graph::
118 depth_first_search_all<some_incidence_list_graph,
119 preordering_visitor,
120 mpl::vector<> >::type>::type
121 preorder_inc;
122BOOST_MPL_ASSERT(( mpl::equal<preorder_inc::type, mpl::vector<A,B,C,D,E,F> > ));
123
124// postordering, default start node
125typedef mpl::first<mpl_graph::
126 depth_first_search_all<some_incidence_list_graph,
127 postordering_visitor,
128 mpl::vector<> >::type>::type
129 postorder_inc;
130BOOST_MPL_ASSERT(( mpl::equal<postorder_inc::type, mpl::vector<D,E,F,C,B,A> > ));
131
132// preordering starting at C
133typedef 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;
139BOOST_MPL_ASSERT(( mpl::equal<preorder_inc_all_from_c::type, mpl::vector<C,D,E,F,A,B> > ));
140
141// preordering starting at B
142typedef 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;
148BOOST_MPL_ASSERT(( mpl::equal<preorder_inc_from_b::type, mpl::vector<B,C,D,E,F> > ));
149
150
151int main() {
152 return 0;
153}

source code of boost/libs/msm/example/mpl_graph/depth_first_search.cpp