| //======================================================================= | |
| // 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__ |