ceph/src/boost/libs/graph/include/boost/graph/planar_detail/face_handles.hpp

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