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
18namespace boost {
19namespace msm {
20namespace 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
27struct 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>
61template<typename Graph, typename VisitorOps, typename VisitorState,
62 typename Vertex,
63 typename ColorState = create_search_color_map::type >
64struct 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
99template<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>
102struct 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
123

source code of boost/libs/msm/include/boost/msm/mpl_graph/depth_first_search.hpp