]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | #ifndef BOOST_MSM_MPL_GRAPH_DEPTH_FIRST_SEARCH_HPP_INCLUDED | |
6 | #define BOOST_MSM_MPL_GRAPH_DEPTH_FIRST_SEARCH_HPP_INCLUDED | |
7 | ||
8 | #include <boost/msm/mpl_graph/mpl_graph.hpp> | |
9 | ||
10 | #include <boost/mpl/has_key.hpp> | |
11 | #include <boost/mpl/insert.hpp> | |
12 | #include <boost/mpl/pair.hpp> | |
13 | #include <boost/mpl/map.hpp> | |
14 | #include <boost/mpl/has_key.hpp> | |
15 | ||
16 | #include "search_colors.hpp" | |
17 | ||
18 | namespace boost { | |
19 | namespace msm { | |
20 | namespace mpl_graph { | |
21 | ||
22 | // dfs takes a visitor which has all the bgl-like metafunctions encapsulated in an | |
23 | // "operations" member class, and also a state. the operations are expected to return a new state | |
24 | // in addition, the visitor operations are expected to update the colors of vertices | |
25 | // and need to support a new metafunction get_color<Vertex, State> | |
26 | ||
27 | struct dfs_default_visitor_operations { | |
28 | template<typename Vertex, typename Graph, typename State> | |
29 | struct initialize_vertex { | |
30 | typedef State type; | |
31 | }; | |
32 | ||
33 | template<typename Vertex, typename Graph, typename State> | |
34 | struct discover_vertex { | |
35 | typedef State type; | |
36 | }; | |
37 | ||
38 | template<typename Vertex, typename Graph, typename State> | |
39 | struct finish_vertex { | |
40 | typedef State type; | |
41 | }; | |
42 | ||
43 | template<typename Edge, typename Graph, typename State> | |
44 | struct tree_edge { | |
45 | typedef State type; | |
46 | }; | |
47 | ||
48 | template<typename Edge, typename Graph, typename State> | |
49 | struct back_edge { | |
50 | typedef State type; | |
51 | }; | |
52 | ||
53 | template<typename Edge, typename Graph, typename State> | |
54 | struct forward_or_cross_edge { | |
55 | typedef State type; | |
56 | }; | |
57 | }; | |
58 | ||
59 | // requires IncidenceGraph | |
60 | // returns pair<VisitorState, ColorState> | |
61 | template<typename Graph, typename VisitorOps, typename VisitorState, | |
62 | typename Vertex, | |
63 | typename ColorState = create_search_color_map::type > | |
64 | struct depth_first_search { | |
65 | // enter vertex | |
66 | typedef typename VisitorOps::template | |
67 | discover_vertex<Vertex, Graph, VisitorState>::type | |
68 | discovered_state; | |
69 | typedef typename search_color_map_ops::template | |
70 | set_color<Vertex, search_colors::Gray, ColorState>::type | |
71 | discovered_colors; | |
72 | ||
73 | // loop over out edges | |
74 | typedef typename | |
75 | mpl::fold<typename mpl_graph::out_edges<Vertex, Graph>::type, | |
76 | mpl::pair<discovered_state, discovered_colors>, | |
77 | mpl::if_<boost::is_same<search_color_map_ops::get_color<mpl_graph::target<mpl::_2, Graph>, mpl::second<mpl::_1> >, | |
78 | search_colors::White>, | |
79 | // unseen target: recurse | |
80 | depth_first_search<Graph, | |
81 | VisitorOps, typename VisitorOps::template tree_edge<mpl::_2, Graph, mpl::first<mpl::_1> >, | |
82 | mpl_graph::target<mpl::_2, Graph>, | |
83 | mpl::second<mpl::_1> >, | |
84 | // seen: back or forward edge | |
85 | mpl::pair<mpl::if_<boost::is_same<typename search_color_map_ops::template | |
86 | get_color<mpl_graph::target<mpl::_2, Graph>, mpl::second<mpl::_1 > >, | |
87 | search_colors::Gray>, | |
88 | typename VisitorOps::template back_edge<mpl::_2, Graph, mpl::first<mpl::_1> >, | |
89 | typename VisitorOps::template forward_or_cross_edge<mpl::_2, Graph, mpl::first<mpl::_1> > >, // Black | |
90 | mpl::second<mpl::_1> > > | |
91 | >::type after_outedges; | |
92 | ||
93 | // leave vertex, and done! | |
94 | typedef mpl::pair<typename VisitorOps::template finish_vertex<Vertex, Graph, typename mpl::first<after_outedges>::type >::type, | |
95 | typename search_color_map_ops::template set_color<Vertex, search_colors::Black, typename mpl::second<after_outedges>::type>::type> type; | |
96 | }; | |
97 | ||
98 | // requires IncidenceGraph, VertexListGraph | |
99 | template<typename Graph, typename VisitorOps, typename VisitorState, | |
100 | typename FirstVertex = typename mpl::front<typename mpl_graph::vertices<Graph>::type>::type, | |
101 | typename ColorState = create_search_color_map::type> | |
102 | struct depth_first_search_all : // visit first then rest | |
103 | mpl::fold<typename mpl_graph::vertices<Graph>::type, | |
104 | typename depth_first_search<Graph, | |
105 | VisitorOps, VisitorState, | |
106 | FirstVertex, | |
107 | ColorState>::type, | |
108 | mpl::if_<boost::is_same<search_color_map_ops::get_color<mpl::_2, mpl::second<mpl::_1> >, | |
109 | search_colors::White>, // visit any yet unvisited | |
110 | depth_first_search<Graph, | |
111 | VisitorOps, mpl::first<mpl::_1>, | |
112 | mpl::_2, | |
113 | mpl::second<mpl::_1> >, | |
114 | mpl::_1> > | |
115 | {}; | |
116 | ||
117 | } // namespace mpl_graph | |
118 | } // namespace msm | |
119 | } // namespace boost | |
120 | ||
121 | ||
122 | #endif // BOOST_MSM_MPL_GRAPH_DEPTH_FIRST_SEARCH_HPP_INCLUDED |