1 //======================================================================= 2 // Copyright (c) Aaron Windsor 2007 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 __FACE_HANDLES_HPP__ 10 #define __FACE_HANDLES_HPP__ 11 12 #include <list> 13 #include <boost/graph/graph_traits.hpp> 14 #include <boost/shared_ptr.hpp> 15 16 // A "face handle" is an optimization meant to serve two purposes in 17 // the implementation of the Boyer-Myrvold planarity test: (1) it holds 18 // the partial planar embedding of a particular vertex as it's being 19 // constructed, and (2) it allows for efficient traversal around the 20 // outer face of the partial embedding at that particular vertex. A face 21 // handle is lightweight, just a shared pointer to the actual implementation, 22 // since it is passed around/copied liberally in the algorithm. It consists 23 // of an "anchor" (the actual vertex it's associated with) as well as a 24 // sequence of edges. The functions first_vertex/second_vertex and 25 // first_edge/second_edge allow fast access to the beginning and end of the 26 // stored sequence, which allows one to traverse the outer face of the partial 27 // planar embedding as it's being created. 28 // 29 // There are some policies below that define the contents of the face handles: 30 // in the case no embedding is needed (for example, if one just wants to use 31 // the Boyer-Myrvold algorithm as a true/false test for planarity, the 32 // no_embedding class can be passed as the StoreEmbedding policy. Otherwise, 33 // either std_list (which uses as std::list) or recursive_lazy_list can be 34 // passed as this policy. recursive_lazy_list has the best theoretical 35 // performance (O(n) for a sequence of interleaved concatenations and reversals 36 // of the underlying list), but I've noticed little difference between std_list 37 // and recursive_lazy_list in my tests, even though using std_list changes 38 // the worst-case complexity of the planarity test to O(n^2) 39 // 40 // Another policy is StoreOldHandlesPolicy, which specifies whether or not 41 // to keep a record of the previous first/second vertex/edge - this is needed 42 // if a Kuratowski subgraph needs to be isolated. 43 44 namespace boost 45 { 46 namespace graph 47 { 48 namespace detail 49 { 50 51 // face handle policies 52 53 // EmbeddingStorage policy 54 struct store_embedding 55 { 56 }; 57 struct recursive_lazy_list : public store_embedding 58 { 59 }; 60 struct std_list : public store_embedding 61 { 62 }; 63 struct no_embedding 64 { 65 }; 66 67 // StoreOldHandlesPolicy 68 struct store_old_handles 69 { 70 }; 71 struct no_old_handles 72 { 73 }; 74 75 template < typename DataType > struct lazy_list_node 76 { 77 typedef shared_ptr< lazy_list_node< DataType > > ptr_t; 78 lazy_list_nodeboost::graph::detail::lazy_list_node79 lazy_list_node(const DataType& data) 80 : m_reversed(false), m_data(data), m_has_data(true) 81 { 82 } 83 lazy_list_nodeboost::graph::detail::lazy_list_node84 lazy_list_node(ptr_t left_child, ptr_t right_child) 85 : m_reversed(false) 86 , m_has_data(false) 87 , m_left_child(left_child) 88 , m_right_child(right_child) 89 { 90 } 91 92 bool m_reversed; 93 DataType m_data; 94 bool m_has_data; 95 shared_ptr< lazy_list_node > m_left_child; 96 shared_ptr< lazy_list_node > m_right_child; 97 }; 98 99 template < typename StoreOldHandlesPolicy, typename Vertex, 100 typename Edge > 101 struct old_handles_storage; 102 103 template < typename Vertex, typename Edge > 104 struct old_handles_storage< store_old_handles, Vertex, Edge > 105 { 106 Vertex first_vertex; 107 Vertex second_vertex; 108 Edge first_edge; 109 Edge second_edge; 110 }; 111 112 template < typename Vertex, typename Edge > 113 struct old_handles_storage< no_old_handles, Vertex, Edge > 114 { 115 }; 116 117 template < typename StoreEmbeddingPolicy, typename Edge > 118 struct edge_list_storage; 119 120 template < typename Edge > 121 struct edge_list_storage< no_embedding, Edge > 122 { 123 typedef void type; 124 push_backboost::graph::detail::edge_list_storage125 void push_back(Edge) {} push_frontboost::graph::detail::edge_list_storage126 void push_front(Edge) {} reverseboost::graph::detail::edge_list_storage127 void reverse() {} concat_frontboost::graph::detail::edge_list_storage128 void concat_front(edge_list_storage< no_embedding, Edge >) {} concat_backboost::graph::detail::edge_list_storage129 void concat_back(edge_list_storage< no_embedding, Edge >) {} get_listboost::graph::detail::edge_list_storage130 template < typename OutputIterator > void get_list(OutputIterator) 131 { 132 } 133 }; 134 135 template < typename Edge > 136 struct edge_list_storage< recursive_lazy_list, Edge > 137 { 138 typedef lazy_list_node< Edge > node_type; 139 typedef shared_ptr< node_type > type; 140 type value; 141 push_backboost::graph::detail::edge_list_storage142 void push_back(Edge e) 143 { 144 type new_node(new node_type(e)); 145 value = type(new node_type(value, new_node)); 146 } 147 push_frontboost::graph::detail::edge_list_storage148 void push_front(Edge e) 149 { 150 type new_node(new node_type(e)); 151 value = type(new node_type(new_node, value)); 152 } 153 reverseboost::graph::detail::edge_list_storage154 void reverse() { value->m_reversed = !value->m_reversed; } 155 concat_frontboost::graph::detail::edge_list_storage156 void concat_front( 157 edge_list_storage< recursive_lazy_list, Edge > other) 158 { 159 value = type(new node_type(other.value, value)); 160 } 161 concat_backboost::graph::detail::edge_list_storage162 void concat_back( 163 edge_list_storage< recursive_lazy_list, Edge > other) 164 { 165 value = type(new node_type(value, other.value)); 166 } 167 168 template < typename OutputIterator > get_listboost::graph::detail::edge_list_storage169 void get_list(OutputIterator out) 170 { 171 get_list_helper(out, value); 172 } 173 174 private: 175 template < typename OutputIterator > get_list_helperboost::graph::detail::edge_list_storage176 void get_list_helper( 177 OutputIterator o_itr, type root, bool flipped = false) 178 { 179 if (!root) 180 return; 181 182 if (root->m_has_data) 183 *o_itr = root->m_data; 184 185 if ((flipped && !root->m_reversed) 186 || (!flipped && root->m_reversed)) 187 { 188 get_list_helper(o_itr, root->m_right_child, true); 189 get_list_helper(o_itr, root->m_left_child, true); 190 } 191 else 192 { 193 get_list_helper(o_itr, root->m_left_child, false); 194 get_list_helper(o_itr, root->m_right_child, false); 195 } 196 } 197 }; 198 199 template < typename Edge > struct edge_list_storage< std_list, Edge > 200 { 201 typedef std::list< Edge > type; 202 type value; 203 push_backboost::graph::detail::edge_list_storage204 void push_back(Edge e) { value.push_back(e); } 205 push_frontboost::graph::detail::edge_list_storage206 void push_front(Edge e) { value.push_front(e); } 207 reverseboost::graph::detail::edge_list_storage208 void reverse() { value.reverse(); } 209 concat_frontboost::graph::detail::edge_list_storage210 void concat_front(edge_list_storage< std_list, Edge > other) 211 { 212 value.splice(value.begin(), other.value); 213 } 214 concat_backboost::graph::detail::edge_list_storage215 void concat_back(edge_list_storage< std_list, Edge > other) 216 { 217 value.splice(value.end(), other.value); 218 } 219 220 template < typename OutputIterator > get_listboost::graph::detail::edge_list_storage221 void get_list(OutputIterator out) 222 { 223 std::copy(value.begin(), value.end(), out); 224 } 225 }; 226 227 template < typename Graph, typename StoreOldHandlesPolicy, 228 typename StoreEmbeddingPolicy > 229 struct face_handle_impl 230 { 231 typedef typename graph_traits< Graph >::vertex_descriptor vertex_t; 232 typedef typename graph_traits< Graph >::edge_descriptor edge_t; 233 typedef 234 typename edge_list_storage< StoreEmbeddingPolicy, edge_t >::type 235 edge_list_storage_t; 236 face_handle_implboost::graph::detail::face_handle_impl237 face_handle_impl() 238 : cached_first_vertex(graph_traits< Graph >::null_vertex()) 239 , cached_second_vertex(graph_traits< Graph >::null_vertex()) 240 , true_first_vertex(graph_traits< Graph >::null_vertex()) 241 , true_second_vertex(graph_traits< Graph >::null_vertex()) 242 , anchor(graph_traits< Graph >::null_vertex()) 243 { 244 initialize_old_vertices_dispatch(StoreOldHandlesPolicy()); 245 } 246 initialize_old_vertices_dispatchboost::graph::detail::face_handle_impl247 void initialize_old_vertices_dispatch(store_old_handles) 248 { 249 old_handles.first_vertex = graph_traits< Graph >::null_vertex(); 250 old_handles.second_vertex 251 = graph_traits< Graph >::null_vertex(); 252 } 253 initialize_old_vertices_dispatchboost::graph::detail::face_handle_impl254 void initialize_old_vertices_dispatch(no_old_handles) {} 255 256 vertex_t cached_first_vertex; 257 vertex_t cached_second_vertex; 258 vertex_t true_first_vertex; 259 vertex_t true_second_vertex; 260 vertex_t anchor; 261 edge_t cached_first_edge; 262 edge_t cached_second_edge; 263 264 edge_list_storage< StoreEmbeddingPolicy, edge_t > edge_list; 265 old_handles_storage< StoreOldHandlesPolicy, vertex_t, edge_t > 266 old_handles; 267 }; 268 269 template < typename Graph, 270 typename StoreOldHandlesPolicy = store_old_handles, 271 typename StoreEmbeddingPolicy = recursive_lazy_list > 272 class face_handle 273 { 274 public: 275 typedef typename graph_traits< Graph >::vertex_descriptor vertex_t; 276 typedef typename graph_traits< Graph >::edge_descriptor edge_t; 277 typedef face_handle_impl< Graph, StoreOldHandlesPolicy, 278 StoreEmbeddingPolicy > 279 impl_t; 280 typedef face_handle< Graph, StoreOldHandlesPolicy, 281 StoreEmbeddingPolicy > 282 self_t; 283 face_handle(vertex_t anchor=graph_traits<Graph>::null_vertex ())284 face_handle(vertex_t anchor = graph_traits< Graph >::null_vertex()) 285 : pimpl(new impl_t()) 286 { 287 pimpl->anchor = anchor; 288 } 289 face_handle(vertex_t anchor,edge_t initial_edge,const Graph & g)290 face_handle(vertex_t anchor, edge_t initial_edge, const Graph& g) 291 : pimpl(new impl_t()) 292 { 293 vertex_t s(source(initial_edge, g)); 294 vertex_t t(target(initial_edge, g)); 295 vertex_t other_vertex = s == anchor ? t : s; 296 pimpl->anchor = anchor; 297 pimpl->cached_first_edge = initial_edge; 298 pimpl->cached_second_edge = initial_edge; 299 pimpl->cached_first_vertex = other_vertex; 300 pimpl->cached_second_vertex = other_vertex; 301 pimpl->true_first_vertex = other_vertex; 302 pimpl->true_second_vertex = other_vertex; 303 304 pimpl->edge_list.push_back(initial_edge); 305 store_old_face_handles_dispatch(StoreOldHandlesPolicy()); 306 } 307 308 // default copy construction, assignment okay. 309 push_first(edge_t e,const Graph & g)310 void push_first(edge_t e, const Graph& g) 311 { 312 pimpl->edge_list.push_front(e); 313 pimpl->cached_first_vertex = pimpl->true_first_vertex 314 = source(e, g) == pimpl->anchor ? target(e, g) 315 : source(e, g); 316 pimpl->cached_first_edge = e; 317 } 318 push_second(edge_t e,const Graph & g)319 void push_second(edge_t e, const Graph& g) 320 { 321 pimpl->edge_list.push_back(e); 322 pimpl->cached_second_vertex = pimpl->true_second_vertex 323 = source(e, g) == pimpl->anchor ? target(e, g) 324 : source(e, g); 325 pimpl->cached_second_edge = e; 326 } 327 store_old_face_handles()328 inline void store_old_face_handles() 329 { 330 store_old_face_handles_dispatch(StoreOldHandlesPolicy()); 331 } 332 first_vertex() const333 inline vertex_t first_vertex() const 334 { 335 return pimpl->cached_first_vertex; 336 } 337 second_vertex() const338 inline vertex_t second_vertex() const 339 { 340 return pimpl->cached_second_vertex; 341 } 342 true_first_vertex() const343 inline vertex_t true_first_vertex() const 344 { 345 return pimpl->true_first_vertex; 346 } 347 true_second_vertex() const348 inline vertex_t true_second_vertex() const 349 { 350 return pimpl->true_second_vertex; 351 } 352 old_first_vertex() const353 inline vertex_t old_first_vertex() const 354 { 355 return pimpl->old_handles.first_vertex; 356 } 357 old_second_vertex() const358 inline vertex_t old_second_vertex() const 359 { 360 return pimpl->old_handles.second_vertex; 361 } 362 old_first_edge() const363 inline edge_t old_first_edge() const 364 { 365 return pimpl->old_handles.first_edge; 366 } 367 old_second_edge() const368 inline edge_t old_second_edge() const 369 { 370 return pimpl->old_handles.second_edge; 371 } 372 first_edge() const373 inline edge_t first_edge() const 374 { 375 return pimpl->cached_first_edge; 376 } 377 second_edge() const378 inline edge_t second_edge() const 379 { 380 return pimpl->cached_second_edge; 381 } 382 get_anchor() const383 inline vertex_t get_anchor() const { return pimpl->anchor; } 384 glue_first_to_second(face_handle<Graph,StoreOldHandlesPolicy,StoreEmbeddingPolicy> & bottom)385 void glue_first_to_second(face_handle< Graph, StoreOldHandlesPolicy, 386 StoreEmbeddingPolicy >& bottom) 387 { 388 pimpl->edge_list.concat_front(bottom.pimpl->edge_list); 389 pimpl->true_first_vertex = bottom.pimpl->true_first_vertex; 390 pimpl->cached_first_vertex = bottom.pimpl->cached_first_vertex; 391 pimpl->cached_first_edge = bottom.pimpl->cached_first_edge; 392 } 393 glue_second_to_first(face_handle<Graph,StoreOldHandlesPolicy,StoreEmbeddingPolicy> & bottom)394 void glue_second_to_first(face_handle< Graph, StoreOldHandlesPolicy, 395 StoreEmbeddingPolicy >& bottom) 396 { 397 pimpl->edge_list.concat_back(bottom.pimpl->edge_list); 398 pimpl->true_second_vertex = bottom.pimpl->true_second_vertex; 399 pimpl->cached_second_vertex 400 = bottom.pimpl->cached_second_vertex; 401 pimpl->cached_second_edge = bottom.pimpl->cached_second_edge; 402 } 403 flip()404 void flip() 405 { 406 pimpl->edge_list.reverse(); 407 std::swap(pimpl->true_first_vertex, pimpl->true_second_vertex); 408 std::swap( 409 pimpl->cached_first_vertex, pimpl->cached_second_vertex); 410 std::swap(pimpl->cached_first_edge, pimpl->cached_second_edge); 411 } 412 413 template < typename OutputIterator > get_list(OutputIterator o_itr)414 void get_list(OutputIterator o_itr) 415 { 416 pimpl->edge_list.get_list(o_itr); 417 } 418 reset_vertex_cache()419 void reset_vertex_cache() 420 { 421 pimpl->cached_first_vertex = pimpl->true_first_vertex; 422 pimpl->cached_second_vertex = pimpl->true_second_vertex; 423 } 424 set_first_vertex(vertex_t v)425 inline void set_first_vertex(vertex_t v) 426 { 427 pimpl->cached_first_vertex = v; 428 } 429 set_second_vertex(vertex_t v)430 inline void set_second_vertex(vertex_t v) 431 { 432 pimpl->cached_second_vertex = v; 433 } 434 435 private: store_old_face_handles_dispatch(store_old_handles)436 void store_old_face_handles_dispatch(store_old_handles) 437 { 438 pimpl->old_handles.first_vertex = pimpl->true_first_vertex; 439 pimpl->old_handles.second_vertex = pimpl->true_second_vertex; 440 pimpl->old_handles.first_edge = pimpl->cached_first_edge; 441 pimpl->old_handles.second_edge = pimpl->cached_second_edge; 442 } 443 store_old_face_handles_dispatch(no_old_handles)444 void store_old_face_handles_dispatch(no_old_handles) {} 445 446 boost::shared_ptr< impl_t > pimpl; 447 }; 448 449 } /* namespace detail */ 450 } /* namespace graph */ 451 } /* namespace boost */ 452 453 #endif //__FACE_HANDLES_HPP__ 454