boost/graph/boyer_myrvold_planar_test.hpp

0001 //=======================================================================
0002 // Copyright 2007 Aaron Windsor
0003 //
0004 // Distributed under the Boost Software License, Version 1.0. (See
0005 // accompanying file LICENSE_1_0.txt or copy at
0006 // http://www.boost.org/LICENSE_1_0.txt)
0007 //=======================================================================
0008
0009 #ifndef __BOYER_MYRVOLD_PLANAR_TEST_HPP__
0010 #define __BOYER_MYRVOLD_PLANAR_TEST_HPP__
0011
0012 #include <boost/graph/planar_detail/boyer_myrvold_impl.hpp>
0013 #include <boost/parameter.hpp>
0014 #include <boost/type_traits.hpp>
0015 #include <boost/mpl/bool.hpp>
0016
0017 namespace boost
0018 {
0019
0020 struct no_kuratowski_subgraph_isolation
0021 {
0022 };
0023 struct no_planar_embedding
0024 {
0025 };
0026
0027 namespace boyer_myrvold_params
0028 {
0029
0030     BOOST_PARAMETER_KEYWORD(tag, graph)
0031     BOOST_PARAMETER_KEYWORD(tag, embedding)
0032     BOOST_PARAMETER_KEYWORD(tag, kuratowski_subgraph)
0033     BOOST_PARAMETER_KEYWORD(tag, vertex_index_map)
0034     BOOST_PARAMETER_KEYWORD(tag, edge_index_map)
0035
0036     typedef parameter::parameters< parameter::required< tag::graph >,
0037         tag::embedding, tag::kuratowski_subgraph, tag::vertex_index_map,
0038         tag::edge_index_map >
0039         boyer_myrvold_params_t;
0040
0041     namespace core
0042     {
0043
0044         template < typename ArgumentPack >
0045         bool dispatched_boyer_myrvold(
0046             ArgumentPack const& args, mpl::true_, mpl::true_)
0047         {
0048             // Dispatch for no planar embedding, no kuratowski subgraph
0049             // isolation
0050
0051             typedef typename remove_const< typename parameter::value_type<
0052                 ArgumentPack, tag::graph >::type >::type graph_t;
0053
0054             typedef typename property_map< graph_t, vertex_index_t >::const_type
0055                 vertex_default_index_map_t;
0056
0057             typedef typename parameter::value_type< ArgumentPack,
0058                 tag::vertex_index_map, vertex_default_index_map_t >::type
0059                 vertex_index_map_t;
0060
0061             graph_t const& g = args[graph];
0062             vertex_default_index_map_t v_d_map = get(vertex_index, g);
0063             vertex_index_map_t v_i_map = args[vertex_index_map | v_d_map];
0064             boyer_myrvold_impl< graph_t, vertex_index_map_t,
0065                 graph::detail::no_old_handles, graph::detail::no_embedding >
0066                 planarity_tester(g, v_i_map);
0067
0068             return planarity_tester.is_planar() ? true : false;
0069         }
0070
0071         template < typename ArgumentPack >
0072         bool dispatched_boyer_myrvold(
0073             ArgumentPack const& args, mpl::true_, mpl::false_)
0074         {
0075             // Dispatch for no planar embedding, kuratowski subgraph isolation
0076             typedef typename remove_const< typename parameter::value_type<
0077                 ArgumentPack, tag::graph >::type >::type graph_t;
0078
0079             typedef typename property_map< graph_t, vertex_index_t >::const_type
0080                 vertex_default_index_map_t;
0081
0082             typedef typename parameter::value_type< ArgumentPack,
0083                 tag::vertex_index_map, vertex_default_index_map_t >::type
0084                 vertex_index_map_t;
0085
0086             typedef typename property_map< graph_t, edge_index_t >::const_type
0087                 edge_default_index_map_t;
0088
0089             typedef typename parameter::value_type< ArgumentPack,
0090                 tag::edge_index_map, edge_default_index_map_t >::type
0091                 edge_index_map_t;
0092
0093             graph_t const& g = args[graph];
0094             vertex_default_index_map_t v_d_map = get(vertex_index, g);
0095             vertex_index_map_t v_i_map = args[vertex_index_map | v_d_map];
0096             edge_default_index_map_t e_d_map = get(edge_index, g);
0097             edge_index_map_t e_i_map = args[edge_index_map | e_d_map];
0098             boyer_myrvold_impl< graph_t, vertex_index_map_t,
0099                 graph::detail::store_old_handles, graph::detail::no_embedding >
0100                 planarity_tester(g, v_i_map);
0101
0102             if (planarity_tester.is_planar())
0103                 return true;
0104             else
0105             {
0106                 planarity_tester.extract_kuratowski_subgraph(
0107                     args[kuratowski_subgraph], e_i_map);
0108                 return false;
0109             }
0110         }
0111
0112         template < typename ArgumentPack >
0113         bool dispatched_boyer_myrvold(
0114             ArgumentPack const& args, mpl::false_, mpl::true_)
0115         {
0116             // Dispatch for planar embedding, no kuratowski subgraph isolation
0117             typedef typename remove_const< typename parameter::value_type<
0118                 ArgumentPack, tag::graph >::type >::type graph_t;
0119
0120             typedef typename property_map< graph_t, vertex_index_t >::const_type
0121                 vertex_default_index_map_t;
0122
0123             typedef typename parameter::value_type< ArgumentPack,
0124                 tag::vertex_index_map, vertex_default_index_map_t >::type
0125                 vertex_index_map_t;
0126
0127             graph_t const& g = args[graph];
0128             vertex_default_index_map_t v_d_map = get(vertex_index, g);
0129             vertex_index_map_t v_i_map = args[vertex_index_map | v_d_map];
0130             boyer_myrvold_impl< graph_t, vertex_index_map_t,
0131                 graph::detail::no_old_handles,
0132 #ifdef BOOST_GRAPH_PREFER_STD_LIB
0133                 graph::detail::std_list
0134 #else
0135                 graph::detail::recursive_lazy_list
0136 #endif
0137                 >
0138                 planarity_tester(g, v_i_map);
0139
0140             if (planarity_tester.is_planar())
0141             {
0142                 planarity_tester.make_edge_permutation(args[embedding]);
0143                 return true;
0144             }
0145             else
0146                 return false;
0147         }
0148
0149         template < typename ArgumentPack >
0150         bool dispatched_boyer_myrvold(
0151             ArgumentPack const& args, mpl::false_, mpl::false_)
0152         {
0153             // Dispatch for planar embedding, kuratowski subgraph isolation
0154             typedef typename remove_const< typename parameter::value_type<
0155                 ArgumentPack, tag::graph >::type >::type graph_t;
0156
0157             typedef typename property_map< graph_t, vertex_index_t >::const_type
0158                 vertex_default_index_map_t;
0159
0160             typedef typename parameter::value_type< ArgumentPack,
0161                 tag::vertex_index_map, vertex_default_index_map_t >::type
0162                 vertex_index_map_t;
0163
0164             typedef typename property_map< graph_t, edge_index_t >::const_type
0165                 edge_default_index_map_t;
0166
0167             typedef typename parameter::value_type< ArgumentPack,
0168                 tag::edge_index_map, edge_default_index_map_t >::type
0169                 edge_index_map_t;
0170
0171             graph_t const& g = args[graph];
0172             vertex_default_index_map_t v_d_map = get(vertex_index, g);
0173             vertex_index_map_t v_i_map = args[vertex_index_map | v_d_map];
0174             edge_default_index_map_t e_d_map = get(edge_index, g);
0175             edge_index_map_t e_i_map = args[edge_index_map | e_d_map];
0176             boyer_myrvold_impl< graph_t, vertex_index_map_t,
0177                 graph::detail::store_old_handles,
0178 #ifdef BOOST_BGL_PREFER_STD_LIB
0179                 graph::detail::std_list
0180 #else
0181                 graph::detail::recursive_lazy_list
0182 #endif
0183                 >
0184                 planarity_tester(g, v_i_map);
0185
0186             if (planarity_tester.is_planar())
0187             {
0188                 planarity_tester.make_edge_permutation(args[embedding]);
0189                 return true;
0190             }
0191             else
0192             {
0193                 planarity_tester.extract_kuratowski_subgraph(
0194                     args[kuratowski_subgraph], e_i_map);
0195                 return false;
0196             }
0197         }
0198
0199         template < typename ArgumentPack >
0200         bool boyer_myrvold_planarity_test(ArgumentPack const& args)
0201         {
0202
0203             typedef typename parameter::binding< ArgumentPack,
0204                 tag::kuratowski_subgraph,
0205                 const no_kuratowski_subgraph_isolation& >::type
0206                 kuratowski_arg_t;
0207
0208             typedef typename parameter::binding< ArgumentPack, tag::embedding,
0209                 const no_planar_embedding& >::type embedding_arg_t;
0210
0211             return dispatched_boyer_myrvold(args,
0212                 boost::is_same< embedding_arg_t, const no_planar_embedding& >(),
0213                 boost::is_same< kuratowski_arg_t,
0214                     const no_kuratowski_subgraph_isolation& >());
0215         }
0216
0217     } // namespace core
0218
0219 } // namespace boyer_myrvold_params
0220
0221 template < typename A0 > bool boyer_myrvold_planarity_test(A0 const& arg0)
0222 {
0223     return boyer_myrvold_params::core::boyer_myrvold_planarity_test(
0224         boyer_myrvold_params::boyer_myrvold_params_t()(arg0));
0225 }
0226
0227 template < typename A0, typename A1 >
0228 //  bool boyer_myrvold_planarity_test(A0 const& arg0, A1 const& arg1)
0229 bool boyer_myrvold_planarity_test(A0 const& arg0, A1 const& arg1)
0230 {
0231     return boyer_myrvold_params::core::boyer_myrvold_planarity_test(
0232         boyer_myrvold_params::boyer_myrvold_params_t()(arg0, arg1));
0233 }
0234
0235 template < typename A0, typename A1, typename A2 >
0236 bool boyer_myrvold_planarity_test(
0237     A0 const& arg0, A1 const& arg1, A2 const& arg2)
0238 {
0239     return boyer_myrvold_params::core::boyer_myrvold_planarity_test(
0240         boyer_myrvold_params::boyer_myrvold_params_t()(arg0, arg1, arg2));
0241 }
0242
0243 template < typename A0, typename A1, typename A2, typename A3 >
0244 bool boyer_myrvold_planarity_test(
0245     A0 const& arg0, A1 const& arg1, A2 const& arg2, A3 const& arg3)
0246 {
0247     return boyer_myrvold_params::core::boyer_myrvold_planarity_test(
0248         boyer_myrvold_params::boyer_myrvold_params_t()(arg0, arg1, arg2, arg3));
0249 }
0250
0251 template < typename A0, typename A1, typename A2, typename A3, typename A4 >
0252 bool boyer_myrvold_planarity_test(A0 const& arg0, A1 const& arg1,
0253     A2 const& arg2, A3 const& arg3, A4 const& arg4)
0254 {
0255     return boyer_myrvold_params::core::boyer_myrvold_planarity_test(
0256         boyer_myrvold_params::boyer_myrvold_params_t()(
0257             arg0, arg1, arg2, arg3, arg4));
0258 }
0259
0260 }
0261
0262 #endif //__BOYER_MYRVOLD_PLANAR_TEST_HPP__