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 namespace boost
18 {
19
20 struct no_kuratowski_subgraph_isolation
21 {
22 };
23 struct no_planar_embedding
24 {
25 };
26
27 namespace boyer_myrvold_params
28 {
29
30 BOOST_PARAMETER_KEYWORD(tag, graph)
31 BOOST_PARAMETER_KEYWORD(tag, embedding)
32 BOOST_PARAMETER_KEYWORD(tag, kuratowski_subgraph)
33 BOOST_PARAMETER_KEYWORD(tag, vertex_index_map)
34 BOOST_PARAMETER_KEYWORD(tag, edge_index_map)
35
36 typedef parameter::parameters< parameter::required< tag::graph >,
37 tag::embedding, tag::kuratowski_subgraph, tag::vertex_index_map,
38 tag::edge_index_map >
39 boyer_myrvold_params_t;
40
41 namespace core
42 {
43
44 template < typename ArgumentPack >
dispatched_boyer_myrvold(ArgumentPack const & args,mpl::true_,mpl::true_)45 bool dispatched_boyer_myrvold(
46 ArgumentPack const& args, mpl::true_, mpl::true_)
47 {
48 // Dispatch for no planar embedding, no kuratowski subgraph
49 // isolation
50
51 typedef typename remove_const< typename parameter::value_type<
52 ArgumentPack, tag::graph >::type >::type graph_t;
53
54 typedef typename property_map< graph_t, vertex_index_t >::const_type
55 vertex_default_index_map_t;
56
57 typedef typename parameter::value_type< ArgumentPack,
58 tag::vertex_index_map, vertex_default_index_map_t >::type
59 vertex_index_map_t;
60
61 graph_t const& g = args[graph];
62 vertex_default_index_map_t v_d_map = get(vertex_index, g);
63 vertex_index_map_t v_i_map = args[vertex_index_map | v_d_map];
64 boyer_myrvold_impl< graph_t, vertex_index_map_t,
65 graph::detail::no_old_handles, graph::detail::no_embedding >
66 planarity_tester(g, v_i_map);
67
68 return planarity_tester.is_planar() ? true : false;
69 }
70
71 template < typename ArgumentPack >
dispatched_boyer_myrvold(ArgumentPack const & args,mpl::true_,mpl::false_)72 bool dispatched_boyer_myrvold(
73 ArgumentPack const& args, mpl::true_, mpl::false_)
74 {
75 // Dispatch for no planar embedding, kuratowski subgraph isolation
76 typedef typename remove_const< typename parameter::value_type<
77 ArgumentPack, tag::graph >::type >::type graph_t;
78
79 typedef typename property_map< graph_t, vertex_index_t >::const_type
80 vertex_default_index_map_t;
81
82 typedef typename parameter::value_type< ArgumentPack,
83 tag::vertex_index_map, vertex_default_index_map_t >::type
84 vertex_index_map_t;
85
86 typedef typename property_map< graph_t, edge_index_t >::const_type
87 edge_default_index_map_t;
88
89 typedef typename parameter::value_type< ArgumentPack,
90 tag::edge_index_map, edge_default_index_map_t >::type
91 edge_index_map_t;
92
93 graph_t const& g = args[graph];
94 vertex_default_index_map_t v_d_map = get(vertex_index, g);
95 vertex_index_map_t v_i_map = args[vertex_index_map | v_d_map];
96 edge_default_index_map_t e_d_map = get(edge_index, g);
97 edge_index_map_t e_i_map = args[edge_index_map | e_d_map];
98 boyer_myrvold_impl< graph_t, vertex_index_map_t,
99 graph::detail::store_old_handles, graph::detail::no_embedding >
100 planarity_tester(g, v_i_map);
101
102 if (planarity_tester.is_planar())
103 return true;
104 else
105 {
106 planarity_tester.extract_kuratowski_subgraph(
107 args[kuratowski_subgraph], e_i_map);
108 return false;
109 }
110 }
111
112 template < typename ArgumentPack >
dispatched_boyer_myrvold(ArgumentPack const & args,mpl::false_,mpl::true_)113 bool dispatched_boyer_myrvold(
114 ArgumentPack const& args, mpl::false_, mpl::true_)
115 {
116 // Dispatch for planar embedding, no kuratowski subgraph isolation
117 typedef typename remove_const< typename parameter::value_type<
118 ArgumentPack, tag::graph >::type >::type graph_t;
119
120 typedef typename property_map< graph_t, vertex_index_t >::const_type
121 vertex_default_index_map_t;
122
123 typedef typename parameter::value_type< ArgumentPack,
124 tag::vertex_index_map, vertex_default_index_map_t >::type
125 vertex_index_map_t;
126
127 graph_t const& g = args[graph];
128 vertex_default_index_map_t v_d_map = get(vertex_index, g);
129 vertex_index_map_t v_i_map = args[vertex_index_map | v_d_map];
130 boyer_myrvold_impl< graph_t, vertex_index_map_t,
131 graph::detail::no_old_handles,
132 #ifdef BOOST_GRAPH_PREFER_STD_LIB
133 graph::detail::std_list
134 #else
135 graph::detail::recursive_lazy_list
136 #endif
137 >
138 planarity_tester(g, v_i_map);
139
140 if (planarity_tester.is_planar())
141 {
142 planarity_tester.make_edge_permutation(args[embedding]);
143 return true;
144 }
145 else
146 return false;
147 }
148
149 template < typename ArgumentPack >
dispatched_boyer_myrvold(ArgumentPack const & args,mpl::false_,mpl::false_)150 bool dispatched_boyer_myrvold(
151 ArgumentPack const& args, mpl::false_, mpl::false_)
152 {
153 // Dispatch for planar embedding, kuratowski subgraph isolation
154 typedef typename remove_const< typename parameter::value_type<
155 ArgumentPack, tag::graph >::type >::type graph_t;
156
157 typedef typename property_map< graph_t, vertex_index_t >::const_type
158 vertex_default_index_map_t;
159
160 typedef typename parameter::value_type< ArgumentPack,
161 tag::vertex_index_map, vertex_default_index_map_t >::type
162 vertex_index_map_t;
163
164 typedef typename property_map< graph_t, edge_index_t >::const_type
165 edge_default_index_map_t;
166
167 typedef typename parameter::value_type< ArgumentPack,
168 tag::edge_index_map, edge_default_index_map_t >::type
169 edge_index_map_t;
170
171 graph_t const& g = args[graph];
172 vertex_default_index_map_t v_d_map = get(vertex_index, g);
173 vertex_index_map_t v_i_map = args[vertex_index_map | v_d_map];
174 edge_default_index_map_t e_d_map = get(edge_index, g);
175 edge_index_map_t e_i_map = args[edge_index_map | e_d_map];
176 boyer_myrvold_impl< graph_t, vertex_index_map_t,
177 graph::detail::store_old_handles,
178 #ifdef BOOST_BGL_PREFER_STD_LIB
179 graph::detail::std_list
180 #else
181 graph::detail::recursive_lazy_list
182 #endif
183 >
184 planarity_tester(g, v_i_map);
185
186 if (planarity_tester.is_planar())
187 {
188 planarity_tester.make_edge_permutation(args[embedding]);
189 return true;
190 }
191 else
192 {
193 planarity_tester.extract_kuratowski_subgraph(
194 args[kuratowski_subgraph], e_i_map);
195 return false;
196 }
197 }
198
199 template < typename ArgumentPack >
boyer_myrvold_planarity_test(ArgumentPack const & args)200 bool boyer_myrvold_planarity_test(ArgumentPack const& args)
201 {
202
203 typedef typename parameter::binding< ArgumentPack,
204 tag::kuratowski_subgraph,
205 const no_kuratowski_subgraph_isolation& >::type
206 kuratowski_arg_t;
207
208 typedef typename parameter::binding< ArgumentPack, tag::embedding,
209 const no_planar_embedding& >::type embedding_arg_t;
210
211 return dispatched_boyer_myrvold(args,
212 boost::is_same< embedding_arg_t, const no_planar_embedding& >(),
213 boost::is_same< kuratowski_arg_t,
214 const no_kuratowski_subgraph_isolation& >());
215 }
216
217 } // namespace core
218
219 } // namespace boyer_myrvold_params
220
boyer_myrvold_planarity_test(A0 const & arg0)221 template < typename A0 > bool boyer_myrvold_planarity_test(A0 const& arg0)
222 {
223 return boyer_myrvold_params::core::boyer_myrvold_planarity_test(
224 boyer_myrvold_params::boyer_myrvold_params_t()(arg0));
225 }
226
227 template < typename A0, typename A1 >
228 // bool boyer_myrvold_planarity_test(A0 const& arg0, A1 const& arg1)
boyer_myrvold_planarity_test(A0 const & arg0,A1 const & arg1)229 bool boyer_myrvold_planarity_test(A0 const& arg0, A1 const& arg1)
230 {
231 return boyer_myrvold_params::core::boyer_myrvold_planarity_test(
232 boyer_myrvold_params::boyer_myrvold_params_t()(arg0, arg1));
233 }
234
235 template < typename A0, typename A1, typename A2 >
boyer_myrvold_planarity_test(A0 const & arg0,A1 const & arg1,A2 const & arg2)236 bool boyer_myrvold_planarity_test(
237 A0 const& arg0, A1 const& arg1, A2 const& arg2)
238 {
239 return boyer_myrvold_params::core::boyer_myrvold_planarity_test(
240 boyer_myrvold_params::boyer_myrvold_params_t()(arg0, arg1, arg2));
241 }
242
243 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)244 bool boyer_myrvold_planarity_test(
245 A0 const& arg0, A1 const& arg1, A2 const& arg2, A3 const& arg3)
246 {
247 return boyer_myrvold_params::core::boyer_myrvold_planarity_test(
248 boyer_myrvold_params::boyer_myrvold_params_t()(arg0, arg1, arg2, arg3));
249 }
250
251 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)252 bool boyer_myrvold_planarity_test(A0 const& arg0, A1 const& arg1,
253 A2 const& arg2, A3 const& arg3, A4 const& arg4)
254 {
255 return boyer_myrvold_params::core::boyer_myrvold_planarity_test(
256 boyer_myrvold_params::boyer_myrvold_params_t()(
257 arg0, arg1, arg2, arg3, arg4));
258 }
259
260 }
261
262 #endif //__BOYER_MYRVOLD_PLANAR_TEST_HPP__
263