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 parameter::value_type<ArgumentPack, tag::graph>::type 
        >::type graph_t;

        typedef typename property_map<
            graph_t,
            vertex_index_t
        >::const_type vertex_default_index_map_t;

        typedef typename parameter::value_type<
            ArgumentPack, 
            tag::vertex_index_map,
            vertex_default_index_map_t
        >::type vertex_index_map_t;

        graph_t const& g = args[graph];
        vertex_default_index_map_t v_d_map = get(vertex_index, g);
        vertex_index_map_t v_i_map = args[vertex_index_map | v_d_map];
        boyer_myrvold_impl
          <graph_t, 
           vertex_index_map_t,
           graph::detail::no_old_handles,
           graph::detail::no_embedding
          >
          planarity_tester(g, v_i_map);

        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 parameter::value_type<ArgumentPack, tag::graph>::type 
        >::type graph_t;

        typedef typename property_map<
            graph_t,
            vertex_index_t
        >::const_type vertex_default_index_map_t;

        typedef typename parameter::value_type<
            ArgumentPack, 
            tag::vertex_index_map,
            vertex_default_index_map_t
        >::type vertex_index_map_t;

        typedef typename property_map<
            graph_t,
            edge_index_t
        >::const_type edge_default_index_map_t;

        typedef typename parameter::value_type<
            ArgumentPack, 
            tag::edge_index_map,
            edge_default_index_map_t
        >::type edge_index_map_t;

        graph_t const& g = args[graph];
        vertex_default_index_map_t v_d_map = get(vertex_index, g);
        vertex_index_map_t v_i_map = args[vertex_index_map | v_d_map];
        edge_default_index_map_t e_d_map = get(edge_index, g);
        edge_index_map_t e_i_map = args[edge_index_map | e_d_map];
        boyer_myrvold_impl 
          <graph_t, 
           vertex_index_map_t,
           graph::detail::store_old_handles,
           graph::detail::no_embedding
          >
          planarity_tester(g, v_i_map);

        if (planarity_tester.is_planar())
          return true;
        else
          {
            planarity_tester.extract_kuratowski_subgraph
              (args[kuratowski_subgraph], e_i_map);          
            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 parameter::value_type<ArgumentPack, tag::graph>::type 
        >::type graph_t;

        typedef typename property_map<
            graph_t,
            vertex_index_t
        >::const_type vertex_default_index_map_t;

        typedef typename parameter::value_type<
            ArgumentPack, 
            tag::vertex_index_map,
            vertex_default_index_map_t
        >::type vertex_index_map_t;

        graph_t const& g = args[graph];
        vertex_default_index_map_t v_d_map = get(vertex_index, g);
        vertex_index_map_t v_i_map = args[vertex_index_map | v_d_map];
        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(g, v_i_map);

        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 parameter::value_type<ArgumentPack, tag::graph>::type 
        >::type graph_t;

        typedef typename property_map<
            graph_t,
            vertex_index_t
        >::const_type vertex_default_index_map_t;

        typedef typename parameter::value_type<
            ArgumentPack, 
            tag::vertex_index_map,
            vertex_default_index_map_t
        >::type vertex_index_map_t;

        typedef typename property_map<
            graph_t,
            edge_index_t
        >::const_type edge_default_index_map_t;

        typedef typename parameter::value_type<
            ArgumentPack, 
            tag::edge_index_map,
            edge_default_index_map_t
        >::type edge_index_map_t;

        graph_t const& g = args[graph];
        vertex_default_index_map_t v_d_map = get(vertex_index, g);
        vertex_index_map_t v_i_map = args[vertex_index_map | v_d_map];
        edge_default_index_map_t e_d_map = get(edge_index, g);
        edge_index_map_t e_i_map = args[edge_index_map | e_d_map];
        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(g, v_i_map);

        if (planarity_tester.is_planar())
          {
            planarity_tester.make_edge_permutation(args[embedding]);
            return true;
          }
        else
          {
            planarity_tester.extract_kuratowski_subgraph
              (args[kuratowski_subgraph], e_i_map);          
            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__