graph/planar_detail/face_handles.hpp

0001 //=======================================================================
0002 // Copyright (c) Aaron Windsor 2007
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 __FACE_HANDLES_HPP__
0010 #define __FACE_HANDLES_HPP__
0011
0012 #include <list>
0013 #include <boost/graph/graph_traits.hpp>
0014 #include <boost/shared_ptr.hpp>
0015
0016 // A "face handle" is an optimization meant to serve two purposes in
0017 // the implementation of the Boyer-Myrvold planarity test: (1) it holds
0018 // the partial planar embedding of a particular vertex as it's being
0019 // constructed, and (2) it allows for efficient traversal around the
0020 // outer face of the partial embedding at that particular vertex. A face
0021 // handle is lightweight, just a shared pointer to the actual implementation,
0022 // since it is passed around/copied liberally in the algorithm. It consists
0023 // of an "anchor" (the actual vertex it's associated with) as well as a
0024 // sequence of edges. The functions first_vertex/second_vertex and
0025 // first_edge/second_edge allow fast access to the beginning and end of the
0026 // stored sequence, which allows one to traverse the outer face of the partial
0027 // planar embedding as it's being created.
0028 //
0029 // There are some policies below that define the contents of the face handles:
0030 // in the case no embedding is needed (for example, if one just wants to use
0031 // the Boyer-Myrvold algorithm as a true/false test for planarity, the
0032 // no_embedding class can be passed as the StoreEmbedding policy. Otherwise,
0033 // either std_list (which uses as std::list) or recursive_lazy_list can be
0034 // passed as this policy. recursive_lazy_list has the best theoretical
0035 // performance (O(n) for a sequence of interleaved concatenations and reversals
0036 // of the underlying list), but I've noticed little difference between std_list
0037 // and recursive_lazy_list in my tests, even though using std_list changes
0038 // the worst-case complexity of the planarity test to O(n^2)
0039 //
0040 // Another policy is StoreOldHandlesPolicy, which specifies whether or not
0041 // to keep a record of the previous first/second vertex/edge - this is needed
0042 // if a Kuratowski subgraph needs to be isolated.
0043
0044 namespace boost
0045 {
0046 namespace graph
0047 {
0048     namespace detail
0049     {
0050
0051         // face handle policies
0052
0053         // EmbeddingStorage policy
0054         struct store_embedding
0055         {
0056         };
0057         struct recursive_lazy_list : public store_embedding
0058         {
0059         };
0060         struct std_list : public store_embedding
0061         {
0062         };
0063         struct no_embedding
0064         {
0065         };
0066
0067         // StoreOldHandlesPolicy
0068         struct store_old_handles
0069         {
0070         };
0071         struct no_old_handles
0072         {
0073         };
0074
0075         template < typename DataType > struct lazy_list_node
0076         {
0077             typedef shared_ptr< lazy_list_node< DataType > > ptr_t;
0078
0079             lazy_list_node(const DataType& data)
0080             : m_reversed(false), m_data(data), m_has_data(true)
0081             {
0082             }
0083
0084             lazy_list_node(ptr_t left_child, ptr_t right_child)
0085             : m_reversed(false)
0086             , m_has_data(false)
0087             , m_left_child(left_child)
0088             , m_right_child(right_child)
0089             {
0090             }
0091
0092             bool m_reversed;
0093             DataType m_data;
0094             bool m_has_data;
0095             shared_ptr< lazy_list_node > m_left_child;
0096             shared_ptr< lazy_list_node > m_right_child;
0097         };
0098
0099         template < typename StoreOldHandlesPolicy, typename Vertex,
0100             typename Edge >
0101         struct old_handles_storage;
0102
0103         template < typename Vertex, typename Edge >
0104         struct old_handles_storage< store_old_handles, Vertex, Edge >
0105         {
0106             Vertex first_vertex;
0107             Vertex second_vertex;
0108             Edge first_edge;
0109             Edge second_edge;
0110         };
0111
0112         template < typename Vertex, typename Edge >
0113         struct old_handles_storage< no_old_handles, Vertex, Edge >
0114         {
0115         };
0116
0117         template < typename StoreEmbeddingPolicy, typename Edge >
0118         struct edge_list_storage;
0119
0120         template < typename Edge >
0121         struct edge_list_storage< no_embedding, Edge >
0122         {
0123             typedef void type;
0124
0125             void push_back(Edge) {}
0126             void push_front(Edge) {}
0127             void reverse() {}
0128             void concat_front(edge_list_storage< no_embedding, Edge >) {}
0129             void concat_back(edge_list_storage< no_embedding, Edge >) {}
0130             template < typename OutputIterator > void get_list(OutputIterator)
0131             {
0132             }
0133         };
0134
0135         template < typename Edge >
0136         struct edge_list_storage< recursive_lazy_list, Edge >
0137         {
0138             typedef lazy_list_node< Edge > node_type;
0139             typedef shared_ptr< node_type > type;
0140             type value;
0141
0142             void push_back(Edge e)
0143             {
0144                 type new_node(new node_type(e));
0145                 value = type(new node_type(value, new_node));
0146             }
0147
0148             void push_front(Edge e)
0149             {
0150                 type new_node(new node_type(e));
0151                 value = type(new node_type(new_node, value));
0152             }
0153
0154             void reverse() { value->m_reversed = !value->m_reversed; }
0155
0156             void concat_front(
0157                 edge_list_storage< recursive_lazy_list, Edge > other)
0158             {
0159                 value = type(new node_type(other.value, value));
0160             }
0161
0162             void concat_back(
0163                 edge_list_storage< recursive_lazy_list, Edge > other)
0164             {
0165                 value = type(new node_type(value, other.value));
0166             }
0167
0168             template < typename OutputIterator >
0169             void get_list(OutputIterator out)
0170             {
0171                 get_list_helper(out, value);
0172             }
0173
0174         private:
0175             template < typename OutputIterator >
0176             void get_list_helper(
0177                 OutputIterator o_itr, type root, bool flipped = false)
0178             {
0179                 if (!root)
0180                     return;
0181
0182                 if (root->m_has_data)
0183                     *o_itr = root->m_data;
0184
0185                 if ((flipped && !root->m_reversed)
0186                     || (!flipped && root->m_reversed))
0187                 {
0188                     get_list_helper(o_itr, root->m_right_child, true);
0189                     get_list_helper(o_itr, root->m_left_child, true);
0190                 }
0191                 else
0192                 {
0193                     get_list_helper(o_itr, root->m_left_child, false);
0194                     get_list_helper(o_itr, root->m_right_child, false);
0195                 }
0196             }
0197         };
0198
0199         template < typename Edge > struct edge_list_storage< std_list, Edge >
0200         {
0201             typedef std::list< Edge > type;
0202             type value;
0203
0204             void push_back(Edge e) { value.push_back(e); }
0205
0206             void push_front(Edge e) { value.push_front(e); }
0207
0208             void reverse() { value.reverse(); }
0209
0210             void concat_front(edge_list_storage< std_list, Edge > other)
0211             {
0212                 value.splice(value.begin(), other.value);
0213             }
0214
0215             void concat_back(edge_list_storage< std_list, Edge > other)
0216             {
0217                 value.splice(value.end(), other.value);
0218             }
0219
0220             template < typename OutputIterator >
0221             void get_list(OutputIterator out)
0222             {
0223                 std::copy(value.begin(), value.end(), out);
0224             }
0225         };
0226
0227         template < typename Graph, typename StoreOldHandlesPolicy,
0228             typename StoreEmbeddingPolicy >
0229         struct face_handle_impl
0230         {
0231             typedef typename graph_traits< Graph >::vertex_descriptor vertex_t;
0232             typedef typename graph_traits< Graph >::edge_descriptor edge_t;
0233             typedef
0234                 typename edge_list_storage< StoreEmbeddingPolicy, edge_t >::type
0235                     edge_list_storage_t;
0236
0237             face_handle_impl()
0238             : cached_first_vertex(graph_traits< Graph >::null_vertex())
0239             , cached_second_vertex(graph_traits< Graph >::null_vertex())
0240             , true_first_vertex(graph_traits< Graph >::null_vertex())
0241             , true_second_vertex(graph_traits< Graph >::null_vertex())
0242             , anchor(graph_traits< Graph >::null_vertex())
0243             {
0244                 initialize_old_vertices_dispatch(StoreOldHandlesPolicy());
0245             }
0246
0247             void initialize_old_vertices_dispatch(store_old_handles)
0248             {
0249                 old_handles.first_vertex = graph_traits< Graph >::null_vertex();
0250                 old_handles.second_vertex
0251                     = graph_traits< Graph >::null_vertex();
0252             }
0253
0254             void initialize_old_vertices_dispatch(no_old_handles) {}
0255
0256             vertex_t cached_first_vertex;
0257             vertex_t cached_second_vertex;
0258             vertex_t true_first_vertex;
0259             vertex_t true_second_vertex;
0260             vertex_t anchor;
0261             edge_t cached_first_edge;
0262             edge_t cached_second_edge;
0263
0264             edge_list_storage< StoreEmbeddingPolicy, edge_t > edge_list;
0265             old_handles_storage< StoreOldHandlesPolicy, vertex_t, edge_t >
0266                 old_handles;
0267         };
0268
0269         template < typename Graph,
0270             typename StoreOldHandlesPolicy = store_old_handles,
0271             typename StoreEmbeddingPolicy = recursive_lazy_list >
0272         class face_handle
0273         {
0274         public:
0275             typedef typename graph_traits< Graph >::vertex_descriptor vertex_t;
0276             typedef typename graph_traits< Graph >::edge_descriptor edge_t;
0277             typedef face_handle_impl< Graph, StoreOldHandlesPolicy,
0278                 StoreEmbeddingPolicy >
0279                 impl_t;
0280             typedef face_handle< Graph, StoreOldHandlesPolicy,
0281                 StoreEmbeddingPolicy >
0282                 self_t;
0283
0284             face_handle(vertex_t anchor = graph_traits< Graph >::null_vertex())
0285             : pimpl(new impl_t())
0286             {
0287                 pimpl->anchor = anchor;
0288             }
0289
0290             face_handle(vertex_t anchor, edge_t initial_edge, const Graph& g)
0291             : pimpl(new impl_t())
0292             {
0293                 vertex_t s(source(initial_edge, g));
0294                 vertex_t t(target(initial_edge, g));
0295                 vertex_t other_vertex = s == anchor ? t : s;
0296                 pimpl->anchor = anchor;
0297                 pimpl->cached_first_edge = initial_edge;
0298                 pimpl->cached_second_edge = initial_edge;
0299                 pimpl->cached_first_vertex = other_vertex;
0300                 pimpl->cached_second_vertex = other_vertex;
0301                 pimpl->true_first_vertex = other_vertex;
0302                 pimpl->true_second_vertex = other_vertex;
0303
0304                 pimpl->edge_list.push_back(initial_edge);
0305                 store_old_face_handles_dispatch(StoreOldHandlesPolicy());
0306             }
0307
0308             // default copy construction, assignment okay.
0309
0310             void push_first(edge_t e, const Graph& g)
0311             {
0312                 pimpl->edge_list.push_front(e);
0313                 pimpl->cached_first_vertex = pimpl->true_first_vertex
0314                     = source(e, g) == pimpl->anchor ? target(e, g)
0315                                                     : source(e, g);
0316                 pimpl->cached_first_edge = e;
0317             }
0318
0319             void push_second(edge_t e, const Graph& g)
0320             {
0321                 pimpl->edge_list.push_back(e);
0322                 pimpl->cached_second_vertex = pimpl->true_second_vertex
0323                     = source(e, g) == pimpl->anchor ? target(e, g)
0324                                                     : source(e, g);
0325                 pimpl->cached_second_edge = e;
0326             }
0327
0328             inline void store_old_face_handles()
0329             {
0330                 store_old_face_handles_dispatch(StoreOldHandlesPolicy());
0331             }
0332
0333             inline vertex_t first_vertex() const
0334             {
0335                 return pimpl->cached_first_vertex;
0336             }
0337
0338             inline vertex_t second_vertex() const
0339             {
0340                 return pimpl->cached_second_vertex;
0341             }
0342
0343             inline vertex_t true_first_vertex() const
0344             {
0345                 return pimpl->true_first_vertex;
0346             }
0347
0348             inline vertex_t true_second_vertex() const
0349             {
0350                 return pimpl->true_second_vertex;
0351             }
0352
0353             inline vertex_t old_first_vertex() const
0354             {
0355                 return pimpl->old_handles.first_vertex;
0356             }
0357
0358             inline vertex_t old_second_vertex() const
0359             {
0360                 return pimpl->old_handles.second_vertex;
0361             }
0362
0363             inline edge_t old_first_edge() const
0364             {
0365                 return pimpl->old_handles.first_edge;
0366             }
0367
0368             inline edge_t old_second_edge() const
0369             {
0370                 return pimpl->old_handles.second_edge;
0371             }
0372
0373             inline edge_t first_edge() const
0374             {
0375                 return pimpl->cached_first_edge;
0376             }
0377
0378             inline edge_t second_edge() const
0379             {
0380                 return pimpl->cached_second_edge;
0381             }
0382
0383             inline vertex_t get_anchor() const { return pimpl->anchor; }
0384
0385             void glue_first_to_second(face_handle< Graph, StoreOldHandlesPolicy,
0386                 StoreEmbeddingPolicy >& bottom)
0387             {
0388                 pimpl->edge_list.concat_front(bottom.pimpl->edge_list);
0389                 pimpl->true_first_vertex = bottom.pimpl->true_first_vertex;
0390                 pimpl->cached_first_vertex = bottom.pimpl->cached_first_vertex;
0391                 pimpl->cached_first_edge = bottom.pimpl->cached_first_edge;
0392             }
0393
0394             void glue_second_to_first(face_handle< Graph, StoreOldHandlesPolicy,
0395                 StoreEmbeddingPolicy >& bottom)
0396             {
0397                 pimpl->edge_list.concat_back(bottom.pimpl->edge_list);
0398                 pimpl->true_second_vertex = bottom.pimpl->true_second_vertex;
0399                 pimpl->cached_second_vertex
0400                     = bottom.pimpl->cached_second_vertex;
0401                 pimpl->cached_second_edge = bottom.pimpl->cached_second_edge;
0402             }
0403
0404             void flip()
0405             {
0406                 pimpl->edge_list.reverse();
0407                 std::swap(pimpl->true_first_vertex, pimpl->true_second_vertex);
0408                 std::swap(
0409                     pimpl->cached_first_vertex, pimpl->cached_second_vertex);
0410                 std::swap(pimpl->cached_first_edge, pimpl->cached_second_edge);
0411             }
0412
0413             template < typename OutputIterator >
0414             void get_list(OutputIterator o_itr)
0415             {
0416                 pimpl->edge_list.get_list(o_itr);
0417             }
0418
0419             void reset_vertex_cache()
0420             {
0421                 pimpl->cached_first_vertex = pimpl->true_first_vertex;
0422                 pimpl->cached_second_vertex = pimpl->true_second_vertex;
0423             }
0424
0425             inline void set_first_vertex(vertex_t v)
0426             {
0427                 pimpl->cached_first_vertex = v;
0428             }
0429
0430             inline void set_second_vertex(vertex_t v)
0431             {
0432                 pimpl->cached_second_vertex = v;
0433             }
0434
0435         private:
0436             void store_old_face_handles_dispatch(store_old_handles)
0437             {
0438                 pimpl->old_handles.first_vertex = pimpl->true_first_vertex;
0439                 pimpl->old_handles.second_vertex = pimpl->true_second_vertex;
0440                 pimpl->old_handles.first_edge = pimpl->cached_first_edge;
0441                 pimpl->old_handles.second_edge = pimpl->cached_second_edge;
0442             }
0443
0444             void store_old_face_handles_dispatch(no_old_handles) {}
0445
0446             boost::shared_ptr< impl_t > pimpl;
0447         };
0448
0449     } /* namespace detail */
0450 } /* namespace graph */
0451 } /* namespace boost */
0452
0453 #endif //__FACE_HANDLES_HPP__