1 //=======================================================================
2 // Copyright 2007 Aaron Windsor
3 //
4 // Distributed under the Boost Software License, Version 1.0. (See
5 // accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
7 //=======================================================================
8 
9 #ifndef __BOYER_MYRVOLD_PLANAR_TEST_HPP__
10 #define __BOYER_MYRVOLD_PLANAR_TEST_HPP__
11 
12 #include <boost/graph/planar_detail/boyer_myrvold_impl.hpp>
13 #include <boost/parameter.hpp>
14 #include <boost/type_traits.hpp>
15 #include <boost/mpl/bool.hpp>
16 
17 
18 namespace boost
19 {
20 
21   struct no_kuratowski_subgraph_isolation {};
22   struct no_planar_embedding {};
23 
24   namespace boyer_myrvold_params
25   {
26 
27     BOOST_PARAMETER_KEYWORD(tag, graph)
28     BOOST_PARAMETER_KEYWORD(tag, embedding)
29     BOOST_PARAMETER_KEYWORD(tag, kuratowski_subgraph)
30     BOOST_PARAMETER_KEYWORD(tag, vertex_index_map)
31     BOOST_PARAMETER_KEYWORD(tag, edge_index_map)
32 
33     typedef parameter::parameters< parameter::required<tag::graph>,
34                                    tag::embedding,
35                                    tag::kuratowski_subgraph,
36                                    tag::vertex_index_map,
37                                    tag::edge_index_map
38                                    > boyer_myrvold_params_t;
39 
40     namespace core
41     {
42 
43       template <typename ArgumentPack>
dispatched_boyer_myrvold(ArgumentPack const & args,mpl::true_,mpl::true_)44       bool dispatched_boyer_myrvold(ArgumentPack const& args,
45                                     mpl::true_,
46                                     mpl::true_
47                                     )
48       {
49         //Dispatch for no planar embedding, no kuratowski subgraph isolation
50 
51         typedef typename remove_const<
52             typename parameter::value_type<ArgumentPack, tag::graph>::type
53         >::type graph_t;
54 
55         typedef typename property_map<
56             graph_t,
57             vertex_index_t
58         >::const_type vertex_default_index_map_t;
59 
60         typedef typename parameter::value_type<
61             ArgumentPack,
62             tag::vertex_index_map,
63             vertex_default_index_map_t
64         >::type vertex_index_map_t;
65 
66         graph_t const& g = args[graph];
67         vertex_default_index_map_t v_d_map = get(vertex_index, g);
68         vertex_index_map_t v_i_map = args[vertex_index_map | v_d_map];
69         boyer_myrvold_impl
70           <graph_t,
71            vertex_index_map_t,
72            graph::detail::no_old_handles,
73            graph::detail::no_embedding
74           >
75           planarity_tester(g, v_i_map);
76 
77         return planarity_tester.is_planar() ? true : false;
78       }
79 
80 
81 
82       template <typename ArgumentPack>
dispatched_boyer_myrvold(ArgumentPack const & args,mpl::true_,mpl::false_)83       bool dispatched_boyer_myrvold(ArgumentPack const& args,
84                                     mpl::true_,
85                                     mpl::false_
86                                     )
87       {
88         //Dispatch for no planar embedding, kuratowski subgraph isolation
89         typedef typename remove_const<
90             typename parameter::value_type<ArgumentPack, tag::graph>::type
91         >::type graph_t;
92 
93         typedef typename property_map<
94             graph_t,
95             vertex_index_t
96         >::const_type vertex_default_index_map_t;
97 
98         typedef typename parameter::value_type<
99             ArgumentPack,
100             tag::vertex_index_map,
101             vertex_default_index_map_t
102         >::type vertex_index_map_t;
103 
104         typedef typename property_map<
105             graph_t,
106             edge_index_t
107         >::const_type edge_default_index_map_t;
108 
109         typedef typename parameter::value_type<
110             ArgumentPack,
111             tag::edge_index_map,
112             edge_default_index_map_t
113         >::type edge_index_map_t;
114 
115         graph_t const& g = args[graph];
116         vertex_default_index_map_t v_d_map = get(vertex_index, g);
117         vertex_index_map_t v_i_map = args[vertex_index_map | v_d_map];
118         edge_default_index_map_t e_d_map = get(edge_index, g);
119         edge_index_map_t e_i_map = args[edge_index_map | e_d_map];
120         boyer_myrvold_impl
121           <graph_t,
122            vertex_index_map_t,
123            graph::detail::store_old_handles,
124            graph::detail::no_embedding
125           >
126           planarity_tester(g, v_i_map);
127 
128         if (planarity_tester.is_planar())
129           return true;
130         else
131           {
132             planarity_tester.extract_kuratowski_subgraph
133               (args[kuratowski_subgraph], e_i_map);
134             return false;
135           }
136       }
137 
138 
139 
140 
141       template <typename ArgumentPack>
dispatched_boyer_myrvold(ArgumentPack const & args,mpl::false_,mpl::true_)142       bool dispatched_boyer_myrvold(ArgumentPack const& args,
143                                     mpl::false_,
144                                     mpl::true_
145                                     )
146       {
147         //Dispatch for planar embedding, no kuratowski subgraph isolation
148         typedef typename remove_const<
149             typename parameter::value_type<ArgumentPack, tag::graph>::type
150         >::type graph_t;
151 
152         typedef typename property_map<
153             graph_t,
154             vertex_index_t
155         >::const_type vertex_default_index_map_t;
156 
157         typedef typename parameter::value_type<
158             ArgumentPack,
159             tag::vertex_index_map,
160             vertex_default_index_map_t
161         >::type vertex_index_map_t;
162 
163         graph_t const& g = args[graph];
164         vertex_default_index_map_t v_d_map = get(vertex_index, g);
165         vertex_index_map_t v_i_map = args[vertex_index_map | v_d_map];
166         boyer_myrvold_impl
167           <graph_t,
168            vertex_index_map_t,
169            graph::detail::no_old_handles,
170 #ifdef BOOST_GRAPH_PREFER_STD_LIB
171            graph::detail::std_list
172 #else
173            graph::detail::recursive_lazy_list
174 #endif
175           >
176           planarity_tester(g, v_i_map);
177 
178         if (planarity_tester.is_planar())
179           {
180             planarity_tester.make_edge_permutation(args[embedding]);
181             return true;
182           }
183         else
184           return false;
185       }
186 
187 
188 
189       template <typename ArgumentPack>
dispatched_boyer_myrvold(ArgumentPack const & args,mpl::false_,mpl::false_)190       bool dispatched_boyer_myrvold(ArgumentPack const& args,
191                                     mpl::false_,
192                                     mpl::false_
193                                     )
194       {
195         //Dispatch for planar embedding, kuratowski subgraph isolation
196         typedef typename remove_const<
197             typename parameter::value_type<ArgumentPack, tag::graph>::type
198         >::type graph_t;
199 
200         typedef typename property_map<
201             graph_t,
202             vertex_index_t
203         >::const_type vertex_default_index_map_t;
204 
205         typedef typename parameter::value_type<
206             ArgumentPack,
207             tag::vertex_index_map,
208             vertex_default_index_map_t
209         >::type vertex_index_map_t;
210 
211         typedef typename property_map<
212             graph_t,
213             edge_index_t
214         >::const_type edge_default_index_map_t;
215 
216         typedef typename parameter::value_type<
217             ArgumentPack,
218             tag::edge_index_map,
219             edge_default_index_map_t
220         >::type edge_index_map_t;
221 
222         graph_t const& g = args[graph];
223         vertex_default_index_map_t v_d_map = get(vertex_index, g);
224         vertex_index_map_t v_i_map = args[vertex_index_map | v_d_map];
225         edge_default_index_map_t e_d_map = get(edge_index, g);
226         edge_index_map_t e_i_map = args[edge_index_map | e_d_map];
227         boyer_myrvold_impl
228           <graph_t,
229           vertex_index_map_t,
230           graph::detail::store_old_handles,
231 #ifdef BOOST_BGL_PREFER_STD_LIB
232            graph::detail::std_list
233 #else
234            graph::detail::recursive_lazy_list
235 #endif
236           >
237           planarity_tester(g, v_i_map);
238 
239         if (planarity_tester.is_planar())
240           {
241             planarity_tester.make_edge_permutation(args[embedding]);
242             return true;
243           }
244         else
245           {
246             planarity_tester.extract_kuratowski_subgraph
247               (args[kuratowski_subgraph], e_i_map);
248             return false;
249           }
250       }
251 
252 
253 
254 
255       template <typename ArgumentPack>
boyer_myrvold_planarity_test(ArgumentPack const & args)256       bool boyer_myrvold_planarity_test(ArgumentPack const& args)
257       {
258 
259         typedef typename parameter::binding
260           < ArgumentPack,
261             tag::kuratowski_subgraph,
262             const no_kuratowski_subgraph_isolation&
263           >::type
264           kuratowski_arg_t;
265 
266         typedef typename parameter::binding
267           < ArgumentPack,
268             tag::embedding,
269             const no_planar_embedding&
270           >::type
271           embedding_arg_t;
272 
273          return dispatched_boyer_myrvold
274            (args,
275             boost::is_same
276               <embedding_arg_t, const no_planar_embedding&>(),
277             boost::is_same
278               <kuratowski_arg_t, const no_kuratowski_subgraph_isolation&>()
279             );
280       }
281 
282 
283 
284     } //namespace core
285 
286   } //namespace boyer_myrvold_params
287 
288 
289   template <typename A0>
boyer_myrvold_planarity_test(A0 const & arg0)290   bool boyer_myrvold_planarity_test(A0 const& arg0)
291   {
292     return boyer_myrvold_params::core::boyer_myrvold_planarity_test
293       (boyer_myrvold_params::boyer_myrvold_params_t()(arg0));
294   }
295 
296   template <typename A0, typename A1>
297   //  bool boyer_myrvold_planarity_test(A0 const& arg0, A1 const& arg1)
boyer_myrvold_planarity_test(A0 const & arg0,A1 const & arg1)298   bool boyer_myrvold_planarity_test(A0 const& arg0, A1 const& arg1)
299   {
300     return boyer_myrvold_params::core::boyer_myrvold_planarity_test
301       (boyer_myrvold_params::boyer_myrvold_params_t()(arg0,arg1));
302   }
303 
304   template <typename A0, typename A1, typename A2>
boyer_myrvold_planarity_test(A0 const & arg0,A1 const & arg1,A2 const & arg2)305   bool boyer_myrvold_planarity_test(A0 const& arg0,
306                                     A1 const& arg1,
307                                     A2 const& arg2
308                                     )
309   {
310     return boyer_myrvold_params::core::boyer_myrvold_planarity_test
311       (boyer_myrvold_params::boyer_myrvold_params_t()(arg0,arg1,arg2));
312   }
313 
314   template <typename A0, typename A1, typename A2, typename A3>
boyer_myrvold_planarity_test(A0 const & arg0,A1 const & arg1,A2 const & arg2,A3 const & arg3)315   bool boyer_myrvold_planarity_test(A0 const& arg0,
316                                     A1 const& arg1,
317                                     A2 const& arg2,
318                                     A3 const& arg3
319                                     )
320   {
321     return boyer_myrvold_params::core::boyer_myrvold_planarity_test
322       (boyer_myrvold_params::boyer_myrvold_params_t()(arg0,arg1,arg2,arg3));
323   }
324 
325   template <typename A0, typename A1, typename A2, typename A3, typename A4>
boyer_myrvold_planarity_test(A0 const & arg0,A1 const & arg1,A2 const & arg2,A3 const & arg3,A4 const & arg4)326   bool boyer_myrvold_planarity_test(A0 const& arg0,
327                                     A1 const& arg1,
328                                     A2 const& arg2,
329                                     A3 const& arg3,
330                                     A4 const& arg4
331                                     )
332   {
333     return boyer_myrvold_params::core::boyer_myrvold_planarity_test
334       (boyer_myrvold_params::boyer_myrvold_params_t()
335        (arg0,arg1,arg2,arg3,arg4)
336        );
337   }
338 
339 
340 }
341 
342 #endif //__BOYER_MYRVOLD_PLANAR_TEST_HPP__
343