]>
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 | ||
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__ |