Boost C++ Libraries

boost/graph/boyer_myrvold_planar_test.hpp

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