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
18namespace 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

source code of boost/boost/graph/boyer_myrvold_planar_test.hpp