]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
92f5a8d4 TL |
51 | typedef typename remove_const< |
52 | typename parameter::value_type<ArgumentPack, tag::graph>::type | |
53 | >::type graph_t; | |
54 | ||
55 | typedef typename property_map< | |
56 | graph_t, | |
57 | vertex_index_t | |
58 | >::const_type vertex_default_index_map_t; | |
59 | ||
60 | typedef typename parameter::value_type< | |
61 | ArgumentPack, | |
7c673cae | 62 | tag::vertex_index_map, |
92f5a8d4 TL |
63 | vertex_default_index_map_t |
64 | >::type vertex_index_map_t; | |
7c673cae | 65 | |
92f5a8d4 TL |
66 | graph_t const& g = args[graph]; |
67 | vertex_default_index_map_t v_d_map = get(vertex_index, g); | |
68 | vertex_index_map_t v_i_map = args[vertex_index_map | v_d_map]; | |
7c673cae FG |
69 | boyer_myrvold_impl |
70 | <graph_t, | |
71 | vertex_index_map_t, | |
72 | graph::detail::no_old_handles, | |
73 | graph::detail::no_embedding | |
74 | > | |
92f5a8d4 | 75 | planarity_tester(g, v_i_map); |
7c673cae FG |
76 | |
77 | return planarity_tester.is_planar() ? true : false; | |
78 | } | |
79 | ||
80 | ||
81 | ||
82 | template <typename ArgumentPack> | |
83 | bool dispatched_boyer_myrvold(ArgumentPack const& args, | |
84 | mpl::true_, | |
85 | mpl::false_ | |
86 | ) | |
87 | { | |
88 | //Dispatch for no planar embedding, kuratowski subgraph isolation | |
92f5a8d4 TL |
89 | typedef typename remove_const< |
90 | typename parameter::value_type<ArgumentPack, tag::graph>::type | |
91 | >::type graph_t; | |
92 | ||
93 | typedef typename property_map< | |
94 | graph_t, | |
95 | vertex_index_t | |
96 | >::const_type vertex_default_index_map_t; | |
97 | ||
98 | typedef typename parameter::value_type< | |
99 | ArgumentPack, | |
7c673cae | 100 | tag::vertex_index_map, |
92f5a8d4 TL |
101 | vertex_default_index_map_t |
102 | >::type vertex_index_map_t; | |
103 | ||
104 | typedef typename property_map< | |
105 | graph_t, | |
106 | edge_index_t | |
107 | >::const_type edge_default_index_map_t; | |
108 | ||
109 | typedef typename parameter::value_type< | |
110 | ArgumentPack, | |
111 | tag::edge_index_map, | |
112 | edge_default_index_map_t | |
113 | >::type edge_index_map_t; | |
114 | ||
115 | graph_t const& g = args[graph]; | |
116 | vertex_default_index_map_t v_d_map = get(vertex_index, g); | |
117 | vertex_index_map_t v_i_map = args[vertex_index_map | v_d_map]; | |
118 | edge_default_index_map_t e_d_map = get(edge_index, g); | |
119 | edge_index_map_t e_i_map = args[edge_index_map | e_d_map]; | |
7c673cae FG |
120 | boyer_myrvold_impl |
121 | <graph_t, | |
122 | vertex_index_map_t, | |
123 | graph::detail::store_old_handles, | |
124 | graph::detail::no_embedding | |
125 | > | |
92f5a8d4 | 126 | planarity_tester(g, v_i_map); |
7c673cae FG |
127 | |
128 | if (planarity_tester.is_planar()) | |
129 | return true; | |
130 | else | |
131 | { | |
132 | planarity_tester.extract_kuratowski_subgraph | |
92f5a8d4 | 133 | (args[kuratowski_subgraph], e_i_map); |
7c673cae FG |
134 | return false; |
135 | } | |
136 | } | |
137 | ||
138 | ||
139 | ||
140 | ||
141 | template <typename ArgumentPack> | |
142 | bool dispatched_boyer_myrvold(ArgumentPack const& args, | |
143 | mpl::false_, | |
144 | mpl::true_ | |
145 | ) | |
146 | { | |
147 | //Dispatch for planar embedding, no kuratowski subgraph isolation | |
92f5a8d4 TL |
148 | typedef typename remove_const< |
149 | typename parameter::value_type<ArgumentPack, tag::graph>::type | |
150 | >::type graph_t; | |
7c673cae | 151 | |
92f5a8d4 TL |
152 | typedef typename property_map< |
153 | graph_t, | |
154 | vertex_index_t | |
155 | >::const_type vertex_default_index_map_t; | |
156 | ||
157 | typedef typename parameter::value_type< | |
158 | ArgumentPack, | |
159 | tag::vertex_index_map, | |
160 | vertex_default_index_map_t | |
161 | >::type vertex_index_map_t; | |
162 | ||
163 | graph_t const& g = args[graph]; | |
164 | vertex_default_index_map_t v_d_map = get(vertex_index, g); | |
165 | vertex_index_map_t v_i_map = args[vertex_index_map | v_d_map]; | |
7c673cae FG |
166 | boyer_myrvold_impl |
167 | <graph_t, | |
168 | vertex_index_map_t, | |
169 | graph::detail::no_old_handles, | |
170 | #ifdef BOOST_GRAPH_PREFER_STD_LIB | |
171 | graph::detail::std_list | |
172 | #else | |
173 | graph::detail::recursive_lazy_list | |
174 | #endif | |
175 | > | |
92f5a8d4 | 176 | planarity_tester(g, v_i_map); |
7c673cae FG |
177 | |
178 | if (planarity_tester.is_planar()) | |
179 | { | |
180 | planarity_tester.make_edge_permutation(args[embedding]); | |
181 | return true; | |
182 | } | |
183 | else | |
184 | return false; | |
185 | } | |
186 | ||
187 | ||
188 | ||
189 | template <typename ArgumentPack> | |
190 | bool dispatched_boyer_myrvold(ArgumentPack const& args, | |
191 | mpl::false_, | |
192 | mpl::false_ | |
193 | ) | |
194 | { | |
195 | //Dispatch for planar embedding, kuratowski subgraph isolation | |
92f5a8d4 TL |
196 | typedef typename remove_const< |
197 | typename parameter::value_type<ArgumentPack, tag::graph>::type | |
198 | >::type graph_t; | |
199 | ||
200 | typedef typename property_map< | |
201 | graph_t, | |
202 | vertex_index_t | |
203 | >::const_type vertex_default_index_map_t; | |
204 | ||
205 | typedef typename parameter::value_type< | |
206 | ArgumentPack, | |
207 | tag::vertex_index_map, | |
208 | vertex_default_index_map_t | |
209 | >::type vertex_index_map_t; | |
210 | ||
211 | typedef typename property_map< | |
212 | graph_t, | |
213 | edge_index_t | |
214 | >::const_type edge_default_index_map_t; | |
215 | ||
216 | typedef typename parameter::value_type< | |
217 | ArgumentPack, | |
218 | tag::edge_index_map, | |
219 | edge_default_index_map_t | |
220 | >::type edge_index_map_t; | |
221 | ||
222 | graph_t const& g = args[graph]; | |
223 | vertex_default_index_map_t v_d_map = get(vertex_index, g); | |
224 | vertex_index_map_t v_i_map = args[vertex_index_map | v_d_map]; | |
225 | edge_default_index_map_t e_d_map = get(edge_index, g); | |
226 | edge_index_map_t e_i_map = args[edge_index_map | e_d_map]; | |
7c673cae FG |
227 | boyer_myrvold_impl |
228 | <graph_t, | |
229 | vertex_index_map_t, | |
230 | graph::detail::store_old_handles, | |
231 | #ifdef BOOST_BGL_PREFER_STD_LIB | |
232 | graph::detail::std_list | |
233 | #else | |
234 | graph::detail::recursive_lazy_list | |
235 | #endif | |
236 | > | |
92f5a8d4 | 237 | planarity_tester(g, v_i_map); |
7c673cae FG |
238 | |
239 | if (planarity_tester.is_planar()) | |
240 | { | |
241 | planarity_tester.make_edge_permutation(args[embedding]); | |
242 | return true; | |
243 | } | |
244 | else | |
245 | { | |
246 | planarity_tester.extract_kuratowski_subgraph | |
92f5a8d4 | 247 | (args[kuratowski_subgraph], e_i_map); |
7c673cae FG |
248 | return false; |
249 | } | |
250 | } | |
251 | ||
252 | ||
253 | ||
254 | ||
255 | template <typename ArgumentPack> | |
256 | bool boyer_myrvold_planarity_test(ArgumentPack const& args) | |
257 | { | |
258 | ||
259 | typedef typename parameter::binding | |
260 | < ArgumentPack, | |
261 | tag::kuratowski_subgraph, | |
262 | const no_kuratowski_subgraph_isolation& | |
263 | >::type | |
264 | kuratowski_arg_t; | |
265 | ||
266 | typedef typename parameter::binding | |
267 | < ArgumentPack, | |
268 | tag::embedding, | |
269 | const no_planar_embedding& | |
270 | >::type | |
271 | embedding_arg_t; | |
272 | ||
273 | return dispatched_boyer_myrvold | |
274 | (args, | |
275 | boost::is_same | |
276 | <embedding_arg_t, const no_planar_embedding&>(), | |
277 | boost::is_same | |
278 | <kuratowski_arg_t, const no_kuratowski_subgraph_isolation&>() | |
279 | ); | |
280 | } | |
281 | ||
282 | ||
283 | ||
284 | } //namespace core | |
285 | ||
286 | } //namespace boyer_myrvold_params | |
287 | ||
288 | ||
289 | template <typename A0> | |
290 | bool boyer_myrvold_planarity_test(A0 const& arg0) | |
291 | { | |
292 | return boyer_myrvold_params::core::boyer_myrvold_planarity_test | |
293 | (boyer_myrvold_params::boyer_myrvold_params_t()(arg0)); | |
294 | } | |
295 | ||
296 | template <typename A0, typename A1> | |
297 | // bool boyer_myrvold_planarity_test(A0 const& arg0, A1 const& arg1) | |
298 | bool boyer_myrvold_planarity_test(A0 const& arg0, A1 const& arg1) | |
299 | { | |
300 | return boyer_myrvold_params::core::boyer_myrvold_planarity_test | |
301 | (boyer_myrvold_params::boyer_myrvold_params_t()(arg0,arg1)); | |
302 | } | |
303 | ||
304 | template <typename A0, typename A1, typename A2> | |
305 | bool boyer_myrvold_planarity_test(A0 const& arg0, | |
306 | A1 const& arg1, | |
307 | A2 const& arg2 | |
308 | ) | |
309 | { | |
310 | return boyer_myrvold_params::core::boyer_myrvold_planarity_test | |
311 | (boyer_myrvold_params::boyer_myrvold_params_t()(arg0,arg1,arg2)); | |
312 | } | |
313 | ||
314 | template <typename A0, typename A1, typename A2, typename A3> | |
315 | bool boyer_myrvold_planarity_test(A0 const& arg0, | |
316 | A1 const& arg1, | |
317 | A2 const& arg2, | |
318 | A3 const& arg3 | |
319 | ) | |
320 | { | |
321 | return boyer_myrvold_params::core::boyer_myrvold_planarity_test | |
322 | (boyer_myrvold_params::boyer_myrvold_params_t()(arg0,arg1,arg2,arg3)); | |
323 | } | |
324 | ||
325 | template <typename A0, typename A1, typename A2, typename A3, typename A4> | |
326 | bool boyer_myrvold_planarity_test(A0 const& arg0, | |
327 | A1 const& arg1, | |
328 | A2 const& arg2, | |
329 | A3 const& arg3, | |
330 | A4 const& arg4 | |
331 | ) | |
332 | { | |
333 | return boyer_myrvold_params::core::boyer_myrvold_planarity_test | |
334 | (boyer_myrvold_params::boyer_myrvold_params_t() | |
335 | (arg0,arg1,arg2,arg3,arg4) | |
336 | ); | |
337 | } | |
338 | ||
339 | ||
340 | } | |
341 | ||
342 | #endif //__BOYER_MYRVOLD_PLANAR_TEST_HPP__ |