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<
52 typename parameter::value_type<ArgumentPack, tag::graph>::type
55 typedef typename property_map<
58 >::const_type vertex_default_index_map_t;
60 typedef typename parameter::value_type<
62 tag::vertex_index_map,
63 vertex_default_index_map_t
64 >::type vertex_index_map_t;
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];
72 graph::detail::no_old_handles,
73 graph::detail::no_embedding
75 planarity_tester(g, v_i_map);
77 return planarity_tester.is_planar() ? true : false;
82 template <typename ArgumentPack>
83 bool dispatched_boyer_myrvold(ArgumentPack const& args,
88 //Dispatch for no planar embedding, kuratowski subgraph isolation
89 typedef typename remove_const<
90 typename parameter::value_type<ArgumentPack, tag::graph>::type
93 typedef typename property_map<
96 >::const_type vertex_default_index_map_t;
98 typedef typename parameter::value_type<
100 tag::vertex_index_map,
101 vertex_default_index_map_t
102 >::type vertex_index_map_t;
104 typedef typename property_map<
107 >::const_type edge_default_index_map_t;
109 typedef typename parameter::value_type<
112 edge_default_index_map_t
113 >::type edge_index_map_t;
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];
123 graph::detail::store_old_handles,
124 graph::detail::no_embedding
126 planarity_tester(g, v_i_map);
128 if (planarity_tester.is_planar())
132 planarity_tester.extract_kuratowski_subgraph
133 (args[kuratowski_subgraph], e_i_map);
141 template <typename ArgumentPack>
142 bool dispatched_boyer_myrvold(ArgumentPack const& args,
147 //Dispatch for planar embedding, no kuratowski subgraph isolation
148 typedef typename remove_const<
149 typename parameter::value_type<ArgumentPack, tag::graph>::type
152 typedef typename property_map<
155 >::const_type vertex_default_index_map_t;
157 typedef typename parameter::value_type<
159 tag::vertex_index_map,
160 vertex_default_index_map_t
161 >::type vertex_index_map_t;
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];
169 graph::detail::no_old_handles,
170 #ifdef BOOST_GRAPH_PREFER_STD_LIB
171 graph::detail::std_list
173 graph::detail::recursive_lazy_list
176 planarity_tester(g, v_i_map);
178 if (planarity_tester.is_planar())
180 planarity_tester.make_edge_permutation(args[embedding]);
189 template <typename ArgumentPack>
190 bool dispatched_boyer_myrvold(ArgumentPack const& args,
195 //Dispatch for planar embedding, kuratowski subgraph isolation
196 typedef typename remove_const<
197 typename parameter::value_type<ArgumentPack, tag::graph>::type
200 typedef typename property_map<
203 >::const_type vertex_default_index_map_t;
205 typedef typename parameter::value_type<
207 tag::vertex_index_map,
208 vertex_default_index_map_t
209 >::type vertex_index_map_t;
211 typedef typename property_map<
214 >::const_type edge_default_index_map_t;
216 typedef typename parameter::value_type<
219 edge_default_index_map_t
220 >::type edge_index_map_t;
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];
230 graph::detail::store_old_handles,
231 #ifdef BOOST_BGL_PREFER_STD_LIB
232 graph::detail::std_list
234 graph::detail::recursive_lazy_list
237 planarity_tester(g, v_i_map);
239 if (planarity_tester.is_planar())
241 planarity_tester.make_edge_permutation(args[embedding]);
246 planarity_tester.extract_kuratowski_subgraph
247 (args[kuratowski_subgraph], e_i_map);
255 template <typename ArgumentPack>
256 bool boyer_myrvold_planarity_test(ArgumentPack const& args)
259 typedef typename parameter::binding
261 tag::kuratowski_subgraph,
262 const no_kuratowski_subgraph_isolation&
266 typedef typename parameter::binding
269 const no_planar_embedding&
273 return dispatched_boyer_myrvold
276 <embedding_arg_t, const no_planar_embedding&>(),
278 <kuratowski_arg_t, const no_kuratowski_subgraph_isolation&>()
286 } //namespace boyer_myrvold_params
289 template <typename A0>
290 bool boyer_myrvold_planarity_test(A0 const& arg0)
292 return boyer_myrvold_params::core::boyer_myrvold_planarity_test
293 (boyer_myrvold_params::boyer_myrvold_params_t()(arg0));
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)
300 return boyer_myrvold_params::core::boyer_myrvold_planarity_test
301 (boyer_myrvold_params::boyer_myrvold_params_t()(arg0,arg1));
304 template <typename A0, typename A1, typename A2>
305 bool boyer_myrvold_planarity_test(A0 const& arg0,
310 return boyer_myrvold_params::core::boyer_myrvold_planarity_test
311 (boyer_myrvold_params::boyer_myrvold_params_t()(arg0,arg1,arg2));
314 template <typename A0, typename A1, typename A2, typename A3>
315 bool boyer_myrvold_planarity_test(A0 const& arg0,
321 return boyer_myrvold_params::core::boyer_myrvold_planarity_test
322 (boyer_myrvold_params::boyer_myrvold_params_t()(arg0,arg1,arg2,arg3));
325 template <typename A0, typename A1, typename A2, typename A3, typename A4>
326 bool boyer_myrvold_planarity_test(A0 const& arg0,
333 return boyer_myrvold_params::core::boyer_myrvold_planarity_test
334 (boyer_myrvold_params::boyer_myrvold_params_t()
335 (arg0,arg1,arg2,arg3,arg4)
342 #endif //__BOYER_MYRVOLD_PLANAR_TEST_HPP__