//=======================================================================

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

