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> dispatched_boyer_myrvold(ArgumentPack const & args,mpl::true_,mpl::true_)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 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, 62 tag::vertex_index_map, 63 vertex_default_index_map_t 64 >::type vertex_index_map_t; 65 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]; 69 boyer_myrvold_impl 70 <graph_t, 71 vertex_index_map_t, 72 graph::detail::no_old_handles, 73 graph::detail::no_embedding 74 > 75 planarity_tester(g, v_i_map); 76 77 return planarity_tester.is_planar() ? true : false; 78 } 79 80 81 82 template <typename ArgumentPack> dispatched_boyer_myrvold(ArgumentPack const & args,mpl::true_,mpl::false_)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 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, 100 tag::vertex_index_map, 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]; 120 boyer_myrvold_impl 121 <graph_t, 122 vertex_index_map_t, 123 graph::detail::store_old_handles, 124 graph::detail::no_embedding 125 > 126 planarity_tester(g, v_i_map); 127 128 if (planarity_tester.is_planar()) 129 return true; 130 else 131 { 132 planarity_tester.extract_kuratowski_subgraph 133 (args[kuratowski_subgraph], e_i_map); 134 return false; 135 } 136 } 137 138 139 140 141 template <typename ArgumentPack> dispatched_boyer_myrvold(ArgumentPack const & args,mpl::false_,mpl::true_)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 148 typedef typename remove_const< 149 typename parameter::value_type<ArgumentPack, tag::graph>::type 150 >::type graph_t; 151 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]; 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 > 176 planarity_tester(g, v_i_map); 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> dispatched_boyer_myrvold(ArgumentPack const & args,mpl::false_,mpl::false_)190 bool dispatched_boyer_myrvold(ArgumentPack const& args, 191 mpl::false_, 192 mpl::false_ 193 ) 194 { 195 //Dispatch for planar embedding, kuratowski subgraph isolation 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]; 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 > 237 planarity_tester(g, v_i_map); 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 247 (args[kuratowski_subgraph], e_i_map); 248 return false; 249 } 250 } 251 252 253 254 255 template <typename ArgumentPack> boyer_myrvold_planarity_test(ArgumentPack const & args)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> boyer_myrvold_planarity_test(A0 const & arg0)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) 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> boyer_myrvold_planarity_test(A0 const & arg0,A1 const & arg1,A2 const & arg2)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> boyer_myrvold_planarity_test(A0 const & arg0,A1 const & arg1,A2 const & arg2,A3 const & arg3)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> boyer_myrvold_planarity_test(A0 const & arg0,A1 const & arg1,A2 const & arg2,A3 const & arg3,A4 const & arg4)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__ 343