1 | //======================================================================= |
2 | // Copyright 2007 Aaron Windsor |
3 | // |
4 | // Distributed under the Boost Software License, Version 1.0. (See |
5 | // accompanying file LICENSE_1_0.txt or copy at |
6 | // http://www.boost.org/LICENSE_1_0.txt) |
7 | //======================================================================= |
8 | |
9 | #ifndef __BOYER_MYRVOLD_PLANAR_TEST_HPP__ |
10 | #define __BOYER_MYRVOLD_PLANAR_TEST_HPP__ |
11 | |
12 | #include <boost/graph/planar_detail/boyer_myrvold_impl.hpp> |
13 | #include <boost/parameter.hpp> |
14 | #include <boost/type_traits.hpp> |
15 | #include <boost/mpl/bool.hpp> |
16 | |
17 | |
18 | namespace boost |
19 | { |
20 | |
21 | struct no_kuratowski_subgraph_isolation {}; |
22 | struct no_planar_embedding {}; |
23 | |
24 | namespace boyer_myrvold_params |
25 | { |
26 | |
27 | BOOST_PARAMETER_KEYWORD(tag, graph) |
28 | BOOST_PARAMETER_KEYWORD(tag, embedding) |
29 | BOOST_PARAMETER_KEYWORD(tag, kuratowski_subgraph) |
30 | BOOST_PARAMETER_KEYWORD(tag, vertex_index_map) |
31 | BOOST_PARAMETER_KEYWORD(tag, edge_index_map) |
32 | |
33 | typedef parameter::parameters< parameter::required<tag::graph>, |
34 | tag::embedding, |
35 | tag::kuratowski_subgraph, |
36 | tag::vertex_index_map, |
37 | tag::edge_index_map |
38 | > boyer_myrvold_params_t; |
39 | |
40 | namespace core |
41 | { |
42 | |
43 | template <typename ArgumentPack> |
44 | bool dispatched_boyer_myrvold(ArgumentPack const& args, |
45 | mpl::true_, |
46 | mpl::true_ |
47 | ) |
48 | { |
49 | //Dispatch for no planar embedding, no kuratowski subgraph isolation |
50 | |
51 | typedef typename remove_const |
52 | < |
53 | typename remove_reference |
54 | < typename parameter::binding |
55 | < ArgumentPack, tag::graph>::type |
56 | >::type |
57 | >::type graph_t; |
58 | |
59 | typedef typename parameter::binding |
60 | < ArgumentPack, |
61 | tag::vertex_index_map, |
62 | typename property_map |
63 | < typename remove_reference<graph_t>::type, |
64 | vertex_index_t>::const_type |
65 | >::type vertex_index_map_t; |
66 | |
67 | boyer_myrvold_impl |
68 | <graph_t, |
69 | vertex_index_map_t, |
70 | graph::detail::no_old_handles, |
71 | graph::detail::no_embedding |
72 | > |
73 | planarity_tester(args[graph], |
74 | args[vertex_index_map | |
75 | get(vertex_index, args[graph]) |
76 | ] |
77 | ); |
78 | |
79 | return planarity_tester.is_planar() ? true : false; |
80 | } |
81 | |
82 | |
83 | |
84 | template <typename ArgumentPack> |
85 | bool dispatched_boyer_myrvold(ArgumentPack const& args, |
86 | mpl::true_, |
87 | mpl::false_ |
88 | ) |
89 | { |
90 | //Dispatch for no planar embedding, kuratowski subgraph isolation |
91 | typedef typename remove_const |
92 | < |
93 | typename remove_reference |
94 | < typename parameter::binding |
95 | < ArgumentPack, tag::graph>::type |
96 | >::type |
97 | >::type graph_t; |
98 | |
99 | typedef typename parameter::binding |
100 | < ArgumentPack, |
101 | tag::vertex_index_map, |
102 | typename property_map<graph_t, vertex_index_t>::type |
103 | >::type vertex_index_map_t; |
104 | |
105 | boyer_myrvold_impl |
106 | <graph_t, |
107 | vertex_index_map_t, |
108 | graph::detail::store_old_handles, |
109 | graph::detail::no_embedding |
110 | > |
111 | planarity_tester(args[graph], |
112 | args[vertex_index_map | |
113 | get(vertex_index, args[graph]) |
114 | ] |
115 | ); |
116 | |
117 | if (planarity_tester.is_planar()) |
118 | return true; |
119 | else |
120 | { |
121 | planarity_tester.extract_kuratowski_subgraph |
122 | (args[kuratowski_subgraph], |
123 | args[edge_index_map|get(edge_index, args[graph])] |
124 | ); |
125 | return false; |
126 | } |
127 | } |
128 | |
129 | |
130 | |
131 | |
132 | template <typename ArgumentPack> |
133 | bool dispatched_boyer_myrvold(ArgumentPack const& args, |
134 | mpl::false_, |
135 | mpl::true_ |
136 | ) |
137 | { |
138 | //Dispatch for planar embedding, no kuratowski subgraph isolation |
139 | typedef typename remove_const |
140 | < |
141 | typename remove_reference |
142 | < typename parameter::binding |
143 | < ArgumentPack, tag::graph>::type |
144 | >::type |
145 | >::type graph_t; |
146 | |
147 | typedef typename parameter::binding |
148 | < ArgumentPack, |
149 | tag::vertex_index_map, |
150 | typename property_map<graph_t, vertex_index_t>::type |
151 | >::type vertex_index_map_t; |
152 | |
153 | boyer_myrvold_impl |
154 | <graph_t, |
155 | vertex_index_map_t, |
156 | graph::detail::no_old_handles, |
157 | #ifdef BOOST_GRAPH_PREFER_STD_LIB |
158 | graph::detail::std_list |
159 | #else |
160 | graph::detail::recursive_lazy_list |
161 | #endif |
162 | > |
163 | planarity_tester(args[graph], |
164 | args[vertex_index_map | |
165 | get(vertex_index, args[graph]) |
166 | ] |
167 | ); |
168 | |
169 | if (planarity_tester.is_planar()) |
170 | { |
171 | planarity_tester.make_edge_permutation(args[embedding]); |
172 | return true; |
173 | } |
174 | else |
175 | return false; |
176 | } |
177 | |
178 | |
179 | |
180 | template <typename ArgumentPack> |
181 | bool dispatched_boyer_myrvold(ArgumentPack const& args, |
182 | mpl::false_, |
183 | mpl::false_ |
184 | ) |
185 | { |
186 | //Dispatch for planar embedding, kuratowski subgraph isolation |
187 | typedef typename remove_const |
188 | < |
189 | typename remove_reference |
190 | < typename parameter::binding |
191 | < ArgumentPack, tag::graph>::type |
192 | >::type |
193 | >::type graph_t; |
194 | |
195 | typedef typename parameter::binding |
196 | < ArgumentPack, |
197 | tag::vertex_index_map, |
198 | typename property_map<graph_t, vertex_index_t>::type |
199 | >::type vertex_index_map_t; |
200 | |
201 | boyer_myrvold_impl |
202 | <graph_t, |
203 | vertex_index_map_t, |
204 | graph::detail::store_old_handles, |
205 | #ifdef BOOST_BGL_PREFER_STD_LIB |
206 | graph::detail::std_list |
207 | #else |
208 | graph::detail::recursive_lazy_list |
209 | #endif |
210 | > |
211 | planarity_tester(args[graph], |
212 | args[vertex_index_map | |
213 | get(vertex_index, args[graph]) |
214 | ] |
215 | ); |
216 | |
217 | if (planarity_tester.is_planar()) |
218 | { |
219 | planarity_tester.make_edge_permutation(args[embedding]); |
220 | return true; |
221 | } |
222 | else |
223 | { |
224 | planarity_tester.extract_kuratowski_subgraph |
225 | (args[kuratowski_subgraph], |
226 | args[edge_index_map | get(edge_index, args[graph])] |
227 | ); |
228 | return false; |
229 | } |
230 | } |
231 | |
232 | |
233 | |
234 | |
235 | template <typename ArgumentPack> |
236 | bool boyer_myrvold_planarity_test(ArgumentPack const& args) |
237 | { |
238 | |
239 | typedef typename parameter::binding |
240 | < ArgumentPack, |
241 | tag::kuratowski_subgraph, |
242 | const no_kuratowski_subgraph_isolation& |
243 | >::type |
244 | kuratowski_arg_t; |
245 | |
246 | typedef typename parameter::binding |
247 | < ArgumentPack, |
248 | tag::embedding, |
249 | const no_planar_embedding& |
250 | >::type |
251 | embedding_arg_t; |
252 | |
253 | return dispatched_boyer_myrvold |
254 | (args, |
255 | boost::is_same |
256 | <embedding_arg_t, const no_planar_embedding&>(), |
257 | boost::is_same |
258 | <kuratowski_arg_t, const no_kuratowski_subgraph_isolation&>() |
259 | ); |
260 | } |
261 | |
262 | |
263 | |
264 | } //namespace core |
265 | |
266 | } //namespace boyer_myrvold_params |
267 | |
268 | |
269 | template <typename A0> |
270 | bool boyer_myrvold_planarity_test(A0 const& arg0) |
271 | { |
272 | return boyer_myrvold_params::core::boyer_myrvold_planarity_test |
273 | (boyer_myrvold_params::boyer_myrvold_params_t()(arg0)); |
274 | } |
275 | |
276 | template <typename A0, typename A1> |
277 | // bool boyer_myrvold_planarity_test(A0 const& arg0, A1 const& arg1) |
278 | bool boyer_myrvold_planarity_test(A0 const& arg0, A1 const& arg1) |
279 | { |
280 | return boyer_myrvold_params::core::boyer_myrvold_planarity_test |
281 | (boyer_myrvold_params::boyer_myrvold_params_t()(arg0,arg1)); |
282 | } |
283 | |
284 | template <typename A0, typename A1, typename A2> |
285 | bool boyer_myrvold_planarity_test(A0 const& arg0, |
286 | A1 const& arg1, |
287 | A2 const& arg2 |
288 | ) |
289 | { |
290 | return boyer_myrvold_params::core::boyer_myrvold_planarity_test |
291 | (boyer_myrvold_params::boyer_myrvold_params_t()(arg0,arg1,arg2)); |
292 | } |
293 | |
294 | template <typename A0, typename A1, typename A2, typename A3> |
295 | bool boyer_myrvold_planarity_test(A0 const& arg0, |
296 | A1 const& arg1, |
297 | A2 const& arg2, |
298 | A3 const& arg3 |
299 | ) |
300 | { |
301 | return boyer_myrvold_params::core::boyer_myrvold_planarity_test |
302 | (boyer_myrvold_params::boyer_myrvold_params_t()(arg0,arg1,arg2,arg3)); |
303 | } |
304 | |
305 | template <typename A0, typename A1, typename A2, typename A3, typename A4> |
306 | bool boyer_myrvold_planarity_test(A0 const& arg0, |
307 | A1 const& arg1, |
308 | A2 const& arg2, |
309 | A3 const& arg3, |
310 | A4 const& arg4 |
311 | ) |
312 | { |
313 | return boyer_myrvold_params::core::boyer_myrvold_planarity_test |
314 | (boyer_myrvold_params::boyer_myrvold_params_t() |
315 | (arg0,arg1,arg2,arg3,arg4) |
316 | ); |
317 | } |
318 | |
319 | |
320 | } |
321 | |
322 | #endif //__BOYER_MYRVOLD_PLANAR_TEST_HPP__ |
323 | |