1 //=======================================================================
2 // Copyright 2007 Aaron Windsor
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 //=======================================================================
9 #ifndef __BOYER_MYRVOLD_PLANAR_TEST_HPP__
10 #define __BOYER_MYRVOLD_PLANAR_TEST_HPP__
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>
21 struct no_kuratowski_subgraph_isolation {};
22 struct no_planar_embedding {};
24 namespace boyer_myrvold_params
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)
33 typedef parameter::parameters< parameter::required<tag::graph>,
35 tag::kuratowski_subgraph,
36 tag::vertex_index_map,
38 > boyer_myrvold_params_t;
43 template <typename ArgumentPack>
44 bool dispatched_boyer_myrvold(ArgumentPack const& args,
49 //Dispatch for no planar embedding, no kuratowski subgraph isolation
51 typedef typename remove_const
53 typename remove_reference
54 < typename parameter::binding
55 < ArgumentPack, tag::graph>::type
59 typedef typename parameter::binding
61 tag::vertex_index_map,
63 < typename remove_reference<graph_t>::type,
64 vertex_index_t>::const_type
65 >::type vertex_index_map_t;
70 graph::detail::no_old_handles,
71 graph::detail::no_embedding
73 planarity_tester(args[graph],
74 args[vertex_index_map |
75 get(vertex_index, args[graph])
79 return planarity_tester.is_planar() ? true : false;
84 template <typename ArgumentPack>
85 bool dispatched_boyer_myrvold(ArgumentPack const& args,
90 //Dispatch for no planar embedding, kuratowski subgraph isolation
91 typedef typename remove_const
93 typename remove_reference
94 < typename parameter::binding
95 < ArgumentPack, tag::graph>::type
99 typedef typename parameter::binding
101 tag::vertex_index_map,
102 typename property_map<graph_t, vertex_index_t>::type
103 >::type vertex_index_map_t;
108 graph::detail::store_old_handles,
109 graph::detail::no_embedding
111 planarity_tester(args[graph],
112 args[vertex_index_map |
113 get(vertex_index, args[graph])
117 if (planarity_tester.is_planar())
121 planarity_tester.extract_kuratowski_subgraph
122 (args[kuratowski_subgraph],
123 args[edge_index_map|get(edge_index, args[graph])]
132 template <typename ArgumentPack>
133 bool dispatched_boyer_myrvold(ArgumentPack const& args,
138 //Dispatch for planar embedding, no kuratowski subgraph isolation
139 typedef typename remove_const
141 typename remove_reference
142 < typename parameter::binding
143 < ArgumentPack, tag::graph>::type
147 typedef typename parameter::binding
149 tag::vertex_index_map,
150 typename property_map<graph_t, vertex_index_t>::type
151 >::type vertex_index_map_t;
156 graph::detail::no_old_handles,
157 #ifdef BOOST_GRAPH_PREFER_STD_LIB
158 graph::detail::std_list
160 graph::detail::recursive_lazy_list
163 planarity_tester(args[graph],
164 args[vertex_index_map |
165 get(vertex_index, args[graph])
169 if (planarity_tester.is_planar())
171 planarity_tester.make_edge_permutation(args[embedding]);
180 template <typename ArgumentPack>
181 bool dispatched_boyer_myrvold(ArgumentPack const& args,
186 //Dispatch for planar embedding, kuratowski subgraph isolation
187 typedef typename remove_const
189 typename remove_reference
190 < typename parameter::binding
191 < ArgumentPack, tag::graph>::type
195 typedef typename parameter::binding
197 tag::vertex_index_map,
198 typename property_map<graph_t, vertex_index_t>::type
199 >::type vertex_index_map_t;
204 graph::detail::store_old_handles,
205 #ifdef BOOST_BGL_PREFER_STD_LIB
206 graph::detail::std_list
208 graph::detail::recursive_lazy_list
211 planarity_tester(args[graph],
212 args[vertex_index_map |
213 get(vertex_index, args[graph])
217 if (planarity_tester.is_planar())
219 planarity_tester.make_edge_permutation(args[embedding]);
224 planarity_tester.extract_kuratowski_subgraph
225 (args[kuratowski_subgraph],
226 args[edge_index_map | get(edge_index, args[graph])]
235 template <typename ArgumentPack>
236 bool boyer_myrvold_planarity_test(ArgumentPack const& args)
239 typedef typename parameter::binding
241 tag::kuratowski_subgraph,
242 const no_kuratowski_subgraph_isolation&
246 typedef typename parameter::binding
249 const no_planar_embedding&
253 return dispatched_boyer_myrvold
256 <embedding_arg_t, const no_planar_embedding&>(),
258 <kuratowski_arg_t, const no_kuratowski_subgraph_isolation&>()
266 } //namespace boyer_myrvold_params
269 template <typename A0>
270 bool boyer_myrvold_planarity_test(A0 const& arg0)
272 return boyer_myrvold_params::core::boyer_myrvold_planarity_test
273 (boyer_myrvold_params::boyer_myrvold_params_t()(arg0));
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)
280 return boyer_myrvold_params::core::boyer_myrvold_planarity_test
281 (boyer_myrvold_params::boyer_myrvold_params_t()(arg0,arg1));
284 template <typename A0, typename A1, typename A2>
285 bool boyer_myrvold_planarity_test(A0 const& arg0,
290 return boyer_myrvold_params::core::boyer_myrvold_planarity_test
291 (boyer_myrvold_params::boyer_myrvold_params_t()(arg0,arg1,arg2));
294 template <typename A0, typename A1, typename A2, typename A3>
295 bool boyer_myrvold_planarity_test(A0 const& arg0,
301 return boyer_myrvold_params::core::boyer_myrvold_planarity_test
302 (boyer_myrvold_params::boyer_myrvold_params_t()(arg0,arg1,arg2,arg3));
305 template <typename A0, typename A1, typename A2, typename A3, typename A4>
306 bool boyer_myrvold_planarity_test(A0 const& arg0,
313 return boyer_myrvold_params::core::boyer_myrvold_planarity_test
314 (boyer_myrvold_params::boyer_myrvold_params_t()
315 (arg0,arg1,arg2,arg3,arg4)
322 #endif //__BOYER_MYRVOLD_PLANAR_TEST_HPP__