| //======================================================================= |
| // Copyright 2007 Aaron Windsor |
| // |
| // Distributed under the Boost Software License, Version 1.0. (See |
| // accompanying file LICENSE_1_0.txt or copy at |
| // http://www.boost.org/LICENSE_1_0.txt) |
| //======================================================================= |
| |
| #ifndef __BOYER_MYRVOLD_PLANAR_TEST_HPP__ |
| #define __BOYER_MYRVOLD_PLANAR_TEST_HPP__ |
| |
| #include <boost/graph/planar_detail/boyer_myrvold_impl.hpp> |
| #include <boost/parameter.hpp> |
| #include <boost/type_traits.hpp> |
| #include <boost/mpl/bool.hpp> |
| |
| |
| namespace boost |
| { |
| |
| struct no_kuratowski_subgraph_isolation {}; |
| struct no_planar_embedding {}; |
| |
| namespace boyer_myrvold_params |
| { |
| |
| BOOST_PARAMETER_KEYWORD(tag, graph) |
| BOOST_PARAMETER_KEYWORD(tag, embedding) |
| BOOST_PARAMETER_KEYWORD(tag, kuratowski_subgraph) |
| BOOST_PARAMETER_KEYWORD(tag, vertex_index_map) |
| BOOST_PARAMETER_KEYWORD(tag, edge_index_map) |
| |
| typedef parameter::parameters< parameter::required<tag::graph>, |
| tag::embedding, |
| tag::kuratowski_subgraph, |
| tag::vertex_index_map, |
| tag::edge_index_map |
| > boyer_myrvold_params_t; |
| |
| namespace core |
| { |
| |
| template <typename ArgumentPack> |
| bool dispatched_boyer_myrvold(ArgumentPack const& args, |
| mpl::true_, |
| mpl::true_ |
| ) |
| { |
| //Dispatch for no planar embedding, no kuratowski subgraph isolation |
| |
| typedef typename remove_const |
| < |
| typename remove_reference |
| < typename parameter::binding |
| < ArgumentPack, tag::graph>::type |
| >::type |
| >::type graph_t; |
| |
| typedef typename parameter::binding |
| < ArgumentPack, |
| tag::vertex_index_map, |
| typename property_map |
| < typename remove_reference<graph_t>::type, |
| vertex_index_t>::const_type |
| >::type vertex_index_map_t; |
| |
| boyer_myrvold_impl |
| <graph_t, |
| vertex_index_map_t, |
| graph::detail::no_old_handles, |
| graph::detail::no_embedding |
| > |
| planarity_tester(args[graph], |
| args[vertex_index_map | |
| get(vertex_index, args[graph]) |
| ] |
| ); |
| |
| return planarity_tester.is_planar() ? true : false; |
| } |
| |
| |
| |
| template <typename ArgumentPack> |
| bool dispatched_boyer_myrvold(ArgumentPack const& args, |
| mpl::true_, |
| mpl::false_ |
| ) |
| { |
| //Dispatch for no planar embedding, kuratowski subgraph isolation |
| typedef typename remove_const |
| < |
| typename remove_reference |
| < typename parameter::binding |
| < ArgumentPack, tag::graph>::type |
| >::type |
| >::type graph_t; |
| |
| typedef typename parameter::binding |
| < ArgumentPack, |
| tag::vertex_index_map, |
| typename property_map<graph_t, vertex_index_t>::type |
| >::type vertex_index_map_t; |
| |
| boyer_myrvold_impl |
| <graph_t, |
| vertex_index_map_t, |
| graph::detail::store_old_handles, |
| graph::detail::no_embedding |
| > |
| planarity_tester(args[graph], |
| args[vertex_index_map | |
| get(vertex_index, args[graph]) |
| ] |
| ); |
| |
| if (planarity_tester.is_planar()) |
| return true; |
| else |
| { |
| planarity_tester.extract_kuratowski_subgraph |
| (args[kuratowski_subgraph], |
| args[edge_index_map|get(edge_index, args[graph])] |
| ); |
| return false; |
| } |
| } |
| |
| |
| |
| |
| template <typename ArgumentPack> |
| bool dispatched_boyer_myrvold(ArgumentPack const& args, |
| mpl::false_, |
| mpl::true_ |
| ) |
| { |
| //Dispatch for planar embedding, no kuratowski subgraph isolation |
| typedef typename remove_const |
| < |
| typename remove_reference |
| < typename parameter::binding |
| < ArgumentPack, tag::graph>::type |
| >::type |
| >::type graph_t; |
| |
| typedef typename parameter::binding |
| < ArgumentPack, |
| tag::vertex_index_map, |
| typename property_map<graph_t, vertex_index_t>::type |
| >::type vertex_index_map_t; |
| |
| boyer_myrvold_impl |
| <graph_t, |
| vertex_index_map_t, |
| graph::detail::no_old_handles, |
| #ifdef BOOST_GRAPH_PREFER_STD_LIB |
| graph::detail::std_list |
| #else |
| graph::detail::recursive_lazy_list |
| #endif |
| > |
| planarity_tester(args[graph], |
| args[vertex_index_map | |
| get(vertex_index, args[graph]) |
| ] |
| ); |
| |
| if (planarity_tester.is_planar()) |
| { |
| planarity_tester.make_edge_permutation(args[embedding]); |
| return true; |
| } |
| else |
| return false; |
| } |
| |
| |
| |
| template <typename ArgumentPack> |
| bool dispatched_boyer_myrvold(ArgumentPack const& args, |
| mpl::false_, |
| mpl::false_ |
| ) |
| { |
| //Dispatch for planar embedding, kuratowski subgraph isolation |
| typedef typename remove_const |
| < |
| typename remove_reference |
| < typename parameter::binding |
| < ArgumentPack, tag::graph>::type |
| >::type |
| >::type graph_t; |
| |
| typedef typename parameter::binding |
| < ArgumentPack, |
| tag::vertex_index_map, |
| typename property_map<graph_t, vertex_index_t>::type |
| >::type vertex_index_map_t; |
| |
| boyer_myrvold_impl |
| <graph_t, |
| vertex_index_map_t, |
| graph::detail::store_old_handles, |
| #ifdef BOOST_BGL_PREFER_STD_LIB |
| graph::detail::std_list |
| #else |
| graph::detail::recursive_lazy_list |
| #endif |
| > |
| planarity_tester(args[graph], |
| args[vertex_index_map | |
| get(vertex_index, args[graph]) |
| ] |
| ); |
| |
| if (planarity_tester.is_planar()) |
| { |
| planarity_tester.make_edge_permutation(args[embedding]); |
| return true; |
| } |
| else |
| { |
| planarity_tester.extract_kuratowski_subgraph |
| (args[kuratowski_subgraph], |
| args[edge_index_map | get(edge_index, args[graph])] |
| ); |
| return false; |
| } |
| } |
| |
| |
| |
| |
| template <typename ArgumentPack> |
| bool boyer_myrvold_planarity_test(ArgumentPack const& args) |
| { |
| |
| typedef typename parameter::binding |
| < ArgumentPack, |
| tag::kuratowski_subgraph, |
| const no_kuratowski_subgraph_isolation& |
| >::type |
| kuratowski_arg_t; |
| |
| typedef typename parameter::binding |
| < ArgumentPack, |
| tag::embedding, |
| const no_planar_embedding& |
| >::type |
| embedding_arg_t; |
| |
| return dispatched_boyer_myrvold |
| (args, |
| boost::is_same |
| <embedding_arg_t, const no_planar_embedding&>(), |
| boost::is_same |
| <kuratowski_arg_t, const no_kuratowski_subgraph_isolation&>() |
| ); |
| } |
| |
| |
| |
| } //namespace core |
| |
| } //namespace boyer_myrvold_params |
| |
| |
| template <typename A0> |
| bool boyer_myrvold_planarity_test(A0 const& arg0) |
| { |
| return boyer_myrvold_params::core::boyer_myrvold_planarity_test |
| (boyer_myrvold_params::boyer_myrvold_params_t()(arg0)); |
| } |
| |
| template <typename A0, typename A1> |
| // bool boyer_myrvold_planarity_test(A0 const& arg0, A1 const& arg1) |
| bool boyer_myrvold_planarity_test(A0 const& arg0, A1 const& arg1) |
| { |
| return boyer_myrvold_params::core::boyer_myrvold_planarity_test |
| (boyer_myrvold_params::boyer_myrvold_params_t()(arg0,arg1)); |
| } |
| |
| template <typename A0, typename A1, typename A2> |
| bool boyer_myrvold_planarity_test(A0 const& arg0, |
| A1 const& arg1, |
| A2 const& arg2 |
| ) |
| { |
| return boyer_myrvold_params::core::boyer_myrvold_planarity_test |
| (boyer_myrvold_params::boyer_myrvold_params_t()(arg0,arg1,arg2)); |
| } |
| |
| template <typename A0, typename A1, typename A2, typename A3> |
| bool boyer_myrvold_planarity_test(A0 const& arg0, |
| A1 const& arg1, |
| A2 const& arg2, |
| A3 const& arg3 |
| ) |
| { |
| return boyer_myrvold_params::core::boyer_myrvold_planarity_test |
| (boyer_myrvold_params::boyer_myrvold_params_t()(arg0,arg1,arg2,arg3)); |
| } |
| |
| template <typename A0, typename A1, typename A2, typename A3, typename A4> |
| bool boyer_myrvold_planarity_test(A0 const& arg0, |
| A1 const& arg1, |
| A2 const& arg2, |
| A3 const& arg3, |
| A4 const& arg4 |
| ) |
| { |
| return boyer_myrvold_params::core::boyer_myrvold_planarity_test |
| (boyer_myrvold_params::boyer_myrvold_params_t() |
| (arg0,arg1,arg2,arg3,arg4) |
| ); |
| } |
| |
| |
| } |
| |
| #endif //__BOYER_MYRVOLD_PLANAR_TEST_HPP__ |