1
2 #include <boost/parameter.hpp>
3
4 BOOST_PARAMETER_NAME((_graph, graphs) graph)
5 BOOST_PARAMETER_NAME((_visitor, graphs) visitor)
6 BOOST_PARAMETER_NAME((_root_vertex, graphs) in(root_vertex))
7 BOOST_PARAMETER_NAME((_index_map, graphs) in(index_map))
8 BOOST_PARAMETER_NAME((_color_map, graphs) in_out(color_map))
9
10 #include <boost/graph/graph_traits.hpp>
11 #include <boost/mpl/bool.hpp>
12 #include <boost/mpl/if.hpp>
13 #include <boost/type_traits/is_convertible.hpp>
14 #include <boost/type_traits/is_integral.hpp>
15 #include <boost/type_traits/is_same.hpp>
16
17 struct vertex_descriptor_predicate
18 {
19 template <typename T, typename Args>
20 struct apply
21 : boost::mpl::if_<
22 boost::is_convertible<
23 T
24 , typename boost::graph_traits<
25 typename boost::parameter::value_type<
26 Args
27 , graphs::graph
28 >::type
29 >::vertex_descriptor
30 >
31 , boost::mpl::true_
32 , boost::mpl::false_
33 >
34 {
35 };
36 };
37
38 #include <boost/mpl/eval_if.hpp>
39
40 struct graph_predicate
41 {
42 template <typename T, typename Args>
43 struct apply
44 : boost::mpl::eval_if<
45 boost::is_convertible<
46 typename boost::graph_traits<T>::traversal_category
47 , boost::incidence_graph_tag
48 >
49 , boost::mpl::if_<
50 boost::is_convertible<
51 typename boost::graph_traits<T>::traversal_category
52 , boost::vertex_list_graph_tag
53 >
54 , boost::mpl::true_
55 , boost::mpl::false_
56 >
57 , boost::mpl::false_
58 >
59 {
60 };
61 };
62
63 #include <boost/property_map/property_map.hpp>
64 #include <boost/type_traits/is_same.hpp>
65
66 struct color_map_predicate
67 {
68 template <typename T, typename Args>
69 struct apply
70 : boost::mpl::if_<
71 boost::is_same<
72 typename boost::property_traits<T>::key_type
73 , typename boost::graph_traits<
74 typename boost::parameter::value_type<
75 Args
76 , graphs::graph
77 >::type
78 >::vertex_descriptor
79 >
80 , boost::mpl::true_
81 , boost::mpl::false_
82 >
83 {
84 };
85 };
86
87 #include <boost/type_traits/is_integral.hpp>
88
89 struct index_map_predicate
90 {
91 template <typename T, typename Args>
92 struct apply
93 : boost::mpl::eval_if<
94 boost::is_integral<
95 typename boost::property_traits<T>::value_type
96 >
97 , boost::mpl::if_<
98 boost::is_same<
99 typename boost::property_traits<T>::key_type
100 , typename boost::graph_traits<
101 typename boost::parameter::value_type<
102 Args
103 , graphs::graph
104 >::type
105 >::vertex_descriptor
106 >
107 , boost::mpl::true_
108 , boost::mpl::false_
109 >
110 , boost::mpl::false_
111 >
112 {
113 };
114 };
115
116 #include <boost/graph/properties.hpp>
117 #include <vector>
118
119 template <typename Size, typename IndexMap>
120 boost::iterator_property_map<
121 std::vector<boost::default_color_type>::iterator
122 , IndexMap
123 , boost::default_color_type
124 , boost::default_color_type&
125 >&
default_color_map(Size num_vertices,IndexMap const & index_map)126 default_color_map(Size num_vertices, IndexMap const& index_map)
127 {
128 static std::vector<boost::default_color_type> colors(num_vertices);
129 static boost::iterator_property_map<
130 std::vector<boost::default_color_type>::iterator
131 , IndexMap
132 , boost::default_color_type
133 , boost::default_color_type&
134 > m(colors.begin(), index_map);
135 return m;
136 }
137
138 #include <boost/graph/depth_first_search.hpp>
139
140 BOOST_PARAMETER_FUNCTION((void), depth_first_search, graphs,
141 (required
142 (graph, *(graph_predicate))
143 )
144 (optional
145 (visitor
146 , * // not easily checkable
147 , boost::dfs_visitor<>()
148 )
149 (root_vertex
150 , *(vertex_descriptor_predicate)
151 , *vertices(graph).first
152 )
153 (index_map
154 , *(index_map_predicate)
155 , get(boost::vertex_index, graph)
156 )
157 (color_map
158 , *(color_map_predicate)
159 , default_color_map(num_vertices(graph), index_map)
160 )
161 )
162 )
163 {
164 }
165
166 #include <boost/core/lightweight_test.hpp>
167 #include <boost/graph/adjacency_list.hpp>
168 #include <utility>
169
main()170 int main()
171 {
172 typedef boost::adjacency_list<
173 boost::vecS
174 , boost::vecS
175 , boost::directedS
176 > G;
177 enum {u, v, w, x, y, z, N};
178 typedef std::pair<std::size_t,std::size_t> E;
179 E edges[] = {
180 E(u, v), E(u, x), E(x, v), E(y, x),
181 E(v, y), E(w, y), E(w, z), E(z, z)
182 };
183 G g(edges, edges + sizeof(edges) / sizeof(E), N);
184
185 ::depth_first_search(g);
186 ::depth_first_search(g, _root_vertex = static_cast<std::size_t>(x));
187 return boost::report_errors();
188 }
189
190