]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | |
2 | #include <boost/parameter.hpp> | |
7c673cae FG |
3 | |
4 | BOOST_PARAMETER_NAME((_graph, graphs) graph) | |
5 | BOOST_PARAMETER_NAME((_visitor, graphs) visitor) | |
92f5a8d4 TL |
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 | |
7c673cae | 18 | { |
92f5a8d4 TL |
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 | }; | |
7c673cae FG |
36 | }; |
37 | ||
92f5a8d4 TL |
38 | #include <boost/mpl/eval_if.hpp> |
39 | ||
40 | struct graph_predicate | |
7c673cae | 41 | { |
92f5a8d4 TL |
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 | }; | |
7c673cae FG |
61 | }; |
62 | ||
92f5a8d4 TL |
63 | #include <boost/property_map/property_map.hpp> |
64 | #include <boost/type_traits/is_same.hpp> | |
65 | ||
66 | struct color_map_predicate | |
7c673cae | 67 | { |
92f5a8d4 TL |
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 | }; | |
7c673cae FG |
85 | }; |
86 | ||
92f5a8d4 TL |
87 | #include <boost/type_traits/is_integral.hpp> |
88 | ||
89 | struct index_map_predicate | |
7c673cae | 90 | { |
92f5a8d4 TL |
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 | }; | |
7c673cae FG |
114 | }; |
115 | ||
92f5a8d4 TL |
116 | #include <boost/graph/properties.hpp> |
117 | #include <vector> | |
118 | ||
119 | template <typename Size, typename IndexMap> | |
7c673cae | 120 | boost::iterator_property_map< |
92f5a8d4 TL |
121 | std::vector<boost::default_color_type>::iterator |
122 | , IndexMap | |
123 | , boost::default_color_type | |
124 | , boost::default_color_type& | |
125 | >& | |
126 | default_color_map(Size num_vertices, IndexMap const& index_map) | |
7c673cae | 127 | { |
92f5a8d4 TL |
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; | |
7c673cae FG |
136 | } |
137 | ||
92f5a8d4 | 138 | #include <boost/graph/depth_first_search.hpp> |
7c673cae | 139 | |
92f5a8d4 TL |
140 | BOOST_PARAMETER_FUNCTION((void), depth_first_search, graphs, |
141 | (required | |
142 | (graph, *(graph_predicate)) | |
143 | ) | |
7c673cae | 144 | (optional |
92f5a8d4 TL |
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 | ) | |
7c673cae FG |
161 | ) |
162 | ) | |
92f5a8d4 TL |
163 | { |
164 | } | |
165 | ||
166 | #include <boost/core/lightweight_test.hpp> | |
167 | #include <boost/graph/adjacency_list.hpp> | |
168 | #include <utility> | |
7c673cae FG |
169 | |
170 | int main() | |
171 | { | |
92f5a8d4 TL |
172 | typedef boost::adjacency_list< |
173 | boost::vecS | |
174 | , boost::vecS | |
175 | , boost::directedS | |
176 | > G; | |
7c673cae | 177 | enum {u, v, w, x, y, z, N}; |
92f5a8d4 TL |
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 | }; | |
7c673cae FG |
183 | G g(edges, edges + sizeof(edges) / sizeof(E), N); |
184 | ||
185 | ::depth_first_search(g); | |
92f5a8d4 TL |
186 | ::depth_first_search(g, _root_vertex = static_cast<std::size_t>(x)); |
187 | return boost::report_errors(); | |
7c673cae FG |
188 | } |
189 |