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