Chris@16: //=======================================================================
Chris@16: // Copyright (c) Aaron Windsor 2007
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //=======================================================================
Chris@16: 
Chris@16: #ifndef __FACE_HANDLES_HPP__
Chris@16: #define __FACE_HANDLES_HPP__
Chris@16: 
Chris@16: 
Chris@16: #include <list>
Chris@16: #include <boost/graph/graph_traits.hpp>
Chris@16: #include <boost/shared_ptr.hpp>
Chris@16: 
Chris@16: 
Chris@16: // A "face handle" is an optimization meant to serve two purposes in
Chris@16: // the implementation of the Boyer-Myrvold planarity test: (1) it holds
Chris@16: // the partial planar embedding of a particular vertex as it's being
Chris@16: // constructed, and (2) it allows for efficient traversal around the
Chris@16: // outer face of the partial embedding at that particular vertex. A face
Chris@16: // handle is lightweight, just a shared pointer to the actual implementation,
Chris@16: // since it is passed around/copied liberally in the algorithm. It consists
Chris@16: // of an "anchor" (the actual vertex it's associated with) as well as a
Chris@16: // sequence of edges. The functions first_vertex/second_vertex and
Chris@16: // first_edge/second_edge allow fast access to the beginning and end of the
Chris@16: // stored sequence, which allows one to traverse the outer face of the partial
Chris@16: // planar embedding as it's being created. 
Chris@16: //
Chris@16: // There are some policies below that define the contents of the face handles:
Chris@16: // in the case no embedding is needed (for example, if one just wants to use
Chris@16: // the Boyer-Myrvold algorithm as a true/false test for planarity, the
Chris@16: // no_embedding class can be passed as the StoreEmbedding policy. Otherwise,
Chris@16: // either std_list (which uses as std::list) or recursive_lazy_list can be
Chris@16: // passed as this policy. recursive_lazy_list has the best theoretical
Chris@16: // performance (O(n) for a sequence of interleaved concatenations and reversals
Chris@16: // of the underlying list), but I've noticed little difference between std_list
Chris@16: // and recursive_lazy_list in my tests, even though using std_list changes
Chris@16: // the worst-case complexity of the planarity test to O(n^2)
Chris@16: //
Chris@16: // Another policy is StoreOldHandlesPolicy, which specifies whether or not
Chris@16: // to keep a record of the previous first/second vertex/edge - this is needed
Chris@16: // if a Kuratowski subgraph needs to be isolated.
Chris@16: 
Chris@16: 
Chris@16: namespace boost { namespace graph { namespace detail {
Chris@16: 
Chris@16: 
Chris@16:   //face handle policies
Chris@16:   
Chris@16:   //EmbeddingStorage policy
Chris@16:   struct store_embedding {};
Chris@16:   struct recursive_lazy_list : public store_embedding {};
Chris@16:   struct std_list : public store_embedding {};
Chris@16:   struct no_embedding {};
Chris@16: 
Chris@16:   //StoreOldHandlesPolicy
Chris@16:   struct store_old_handles {};
Chris@16:   struct no_old_handles {};
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16:   template<typename DataType>
Chris@16:   struct lazy_list_node
Chris@16:   {
Chris@16:     typedef shared_ptr< lazy_list_node<DataType> > ptr_t;
Chris@16: 
Chris@16:     lazy_list_node(const DataType& data) :
Chris@16:       m_reversed(false),
Chris@16:       m_data(data),
Chris@16:       m_has_data(true)
Chris@16:     {}
Chris@16:     
Chris@16:     lazy_list_node(ptr_t left_child, ptr_t right_child) :
Chris@16:       m_reversed(false),
Chris@16:       m_has_data(false),
Chris@16:       m_left_child(left_child),
Chris@16:       m_right_child(right_child)
Chris@16:     {}
Chris@16: 
Chris@16:     bool m_reversed;
Chris@16:     DataType m_data;
Chris@16:     bool m_has_data;
Chris@16:     shared_ptr<lazy_list_node> m_left_child;
Chris@16:     shared_ptr<lazy_list_node> m_right_child;
Chris@16:   };
Chris@16:   
Chris@16: 
Chris@16: 
Chris@16:   template <typename StoreOldHandlesPolicy, typename Vertex, typename Edge>
Chris@16:   struct old_handles_storage;
Chris@16: 
Chris@16:   template <typename Vertex, typename Edge>
Chris@16:   struct old_handles_storage<store_old_handles, Vertex, Edge>
Chris@16:   {
Chris@16:     Vertex first_vertex;
Chris@16:     Vertex second_vertex;
Chris@16:     Edge first_edge;
Chris@16:     Edge second_edge;
Chris@16:   };
Chris@16: 
Chris@16:   template <typename Vertex, typename Edge>
Chris@16:   struct old_handles_storage<no_old_handles, Vertex, Edge>
Chris@16:   {};
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16:   template <typename StoreEmbeddingPolicy, typename Edge>
Chris@16:   struct edge_list_storage;
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16:   template <typename Edge>
Chris@16:   struct edge_list_storage<no_embedding, Edge>
Chris@16:   {
Chris@16:     typedef void type;
Chris@16: 
Chris@16:     void push_back(Edge) {}
Chris@16:     void push_front(Edge) {}
Chris@16:     void reverse() {}
Chris@16:     void concat_front(edge_list_storage<no_embedding,Edge>) {}
Chris@16:     void concat_back(edge_list_storage<no_embedding,Edge>) {}
Chris@16:     template <typename OutputIterator>
Chris@16:     void get_list(OutputIterator) {}
Chris@16:   };
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16:   template <typename Edge>
Chris@16:   struct edge_list_storage<recursive_lazy_list, Edge>
Chris@16:   {
Chris@16:     typedef lazy_list_node<Edge> node_type;
Chris@16:     typedef shared_ptr< node_type > type;
Chris@16:     type value;
Chris@16: 
Chris@16:     void push_back(Edge e)
Chris@16:     {
Chris@16:       type new_node(new node_type(e));
Chris@16:       value = type(new node_type(value, new_node));
Chris@16:     }
Chris@16: 
Chris@16:     void push_front(Edge e)
Chris@16:     {
Chris@16:       type new_node(new node_type(e));
Chris@16:       value = type(new node_type(new_node, value));
Chris@16:     }
Chris@16: 
Chris@16:     void reverse()
Chris@16:     {
Chris@16:       value->m_reversed = !value->m_reversed;
Chris@16:     }
Chris@16: 
Chris@16:     void concat_front(edge_list_storage<recursive_lazy_list, Edge> other)
Chris@16:     {
Chris@16:       value = type(new node_type(other.value, value));
Chris@16:     }
Chris@16: 
Chris@16:     void concat_back(edge_list_storage<recursive_lazy_list, Edge> other)
Chris@16:     {
Chris@16:       value = type(new node_type(value, other.value));
Chris@16:     }
Chris@16: 
Chris@16:     template <typename OutputIterator>
Chris@16:     void get_list(OutputIterator out)
Chris@16:     {
Chris@16:       get_list_helper(out, value);
Chris@16:     }
Chris@16: 
Chris@16:   private:
Chris@16: 
Chris@16:     template <typename OutputIterator>
Chris@16:     void get_list_helper(OutputIterator o_itr, 
Chris@16:                          type root,
Chris@16:                          bool flipped = false
Chris@16:                          )
Chris@16:     {
Chris@16:       if (!root)
Chris@16:         return;
Chris@16:       
Chris@16:       if (root->m_has_data)
Chris@16:         *o_itr = root->m_data;
Chris@16:       
Chris@16:       if ((flipped && !root->m_reversed) ||
Chris@16:           (!flipped && root->m_reversed)
Chris@16:           )
Chris@16:         {
Chris@16:           get_list_helper(o_itr, root->m_right_child, true);
Chris@16:           get_list_helper(o_itr, root->m_left_child, true);
Chris@16:         }
Chris@16:       else
Chris@16:         {
Chris@16:           get_list_helper(o_itr, root->m_left_child, false);
Chris@16:           get_list_helper(o_itr, root->m_right_child, false);
Chris@16:         }
Chris@16:       
Chris@16:     }
Chris@16:     
Chris@16:   };
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16:   template <typename Edge>
Chris@16:   struct edge_list_storage<std_list, Edge>
Chris@16:   {
Chris@16:     typedef std::list<Edge> type;
Chris@16:     type value;
Chris@16: 
Chris@16:     void push_back(Edge e)
Chris@16:     {
Chris@16:       value.push_back(e);
Chris@16:     }
Chris@16: 
Chris@16:     void push_front(Edge e)
Chris@16:     {
Chris@16:       value.push_front(e);
Chris@16:     }
Chris@16: 
Chris@16:     void reverse()
Chris@16:     {
Chris@16:       value.reverse();
Chris@16:     }
Chris@16: 
Chris@16:     void concat_front(edge_list_storage<std_list,Edge> other)
Chris@16:     {
Chris@16:       value.splice(value.begin(), other.value);
Chris@16:     }
Chris@16: 
Chris@16:     void concat_back(edge_list_storage<std_list, Edge> other)
Chris@16:     {
Chris@16:       value.splice(value.end(), other.value);
Chris@16:     }
Chris@16: 
Chris@16:     template <typename OutputIterator>
Chris@16:     void get_list(OutputIterator out)
Chris@16:     {
Chris@16:       std::copy(value.begin(), value.end(), out);
Chris@16:     }
Chris@16: 
Chris@16:   };
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16:   
Chris@16:   template<typename Graph, 
Chris@16:            typename StoreOldHandlesPolicy, 
Chris@16:            typename StoreEmbeddingPolicy           
Chris@16:            >
Chris@16:   struct face_handle_impl
Chris@16:   {
Chris@16:     typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
Chris@16:     typedef typename graph_traits<Graph>::edge_descriptor edge_t;
Chris@16:     typedef typename edge_list_storage<StoreEmbeddingPolicy, edge_t>::type 
Chris@16:       edge_list_storage_t;
Chris@16: 
Chris@16: 
Chris@16:     face_handle_impl() : 
Chris@16:       cached_first_vertex(graph_traits<Graph>::null_vertex()),
Chris@16:       cached_second_vertex(graph_traits<Graph>::null_vertex()),
Chris@16:       true_first_vertex(graph_traits<Graph>::null_vertex()),
Chris@16:       true_second_vertex(graph_traits<Graph>::null_vertex()),
Chris@16:       anchor(graph_traits<Graph>::null_vertex())
Chris@16:     {
Chris@16:       initialize_old_vertices_dispatch(StoreOldHandlesPolicy());
Chris@16:     }
Chris@16: 
Chris@16:     void initialize_old_vertices_dispatch(store_old_handles)
Chris@16:     {
Chris@16:       old_handles.first_vertex = graph_traits<Graph>::null_vertex();
Chris@16:       old_handles.second_vertex = graph_traits<Graph>::null_vertex();
Chris@16:     }
Chris@16: 
Chris@16:     void initialize_old_vertices_dispatch(no_old_handles) {}
Chris@16: 
Chris@16:     vertex_t cached_first_vertex;
Chris@16:     vertex_t cached_second_vertex;
Chris@16:     vertex_t true_first_vertex;
Chris@16:     vertex_t true_second_vertex;
Chris@16:     vertex_t anchor;
Chris@16:     edge_t cached_first_edge;
Chris@16:     edge_t cached_second_edge;
Chris@16: 
Chris@16:     edge_list_storage<StoreEmbeddingPolicy, edge_t> edge_list;
Chris@16:     old_handles_storage<StoreOldHandlesPolicy, vertex_t, edge_t> old_handles;
Chris@16: 
Chris@16:   };
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16:   template <typename Graph, 
Chris@16:             typename StoreOldHandlesPolicy = store_old_handles, 
Chris@16:             typename StoreEmbeddingPolicy = recursive_lazy_list
Chris@16:             >
Chris@16:   class face_handle 
Chris@16:   {
Chris@16:   public:
Chris@16:     typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
Chris@16:     typedef typename graph_traits<Graph>::edge_descriptor edge_t;
Chris@16:     typedef face_handle_impl
Chris@16:       <Graph, StoreOldHandlesPolicy, StoreEmbeddingPolicy> impl_t;
Chris@16:     typedef face_handle
Chris@16:       <Graph, StoreOldHandlesPolicy, StoreEmbeddingPolicy> self_t;
Chris@16: 
Chris@16:     face_handle(vertex_t anchor = graph_traits<Graph>::null_vertex()) :
Chris@16:       pimpl(new impl_t())
Chris@16:     {
Chris@16:       pimpl->anchor = anchor;
Chris@16:     }
Chris@16: 
Chris@16:     face_handle(vertex_t anchor, edge_t initial_edge, const Graph& g) :
Chris@16:       pimpl(new impl_t())
Chris@16:     {
Chris@16:       vertex_t s(source(initial_edge,g));
Chris@16:       vertex_t t(target(initial_edge,g));
Chris@16:       vertex_t other_vertex = s == anchor ? t : s;
Chris@16:       pimpl->anchor = anchor;
Chris@16:       pimpl->cached_first_edge = initial_edge;
Chris@16:       pimpl->cached_second_edge = initial_edge;
Chris@16:       pimpl->cached_first_vertex = other_vertex;
Chris@16:       pimpl->cached_second_vertex = other_vertex;
Chris@16:       pimpl->true_first_vertex = other_vertex;
Chris@16:       pimpl->true_second_vertex = other_vertex;
Chris@16: 
Chris@16:       pimpl->edge_list.push_back(initial_edge);
Chris@16:       store_old_face_handles_dispatch(StoreOldHandlesPolicy());
Chris@16:     }
Chris@16: 
Chris@16:     //default copy construction, assignment okay.
Chris@16:     
Chris@16:     void push_first(edge_t e, const Graph& g) 
Chris@16:     { 
Chris@16:       pimpl->edge_list.push_front(e);
Chris@16:       pimpl->cached_first_vertex = pimpl->true_first_vertex = 
Chris@16:         source(e, g) == pimpl->anchor ? target(e,g) : source(e,g);
Chris@16:       pimpl->cached_first_edge = e;
Chris@16:     }
Chris@16:   
Chris@16:     void push_second(edge_t e, const Graph& g) 
Chris@16:     { 
Chris@16:       pimpl->edge_list.push_back(e);
Chris@16:       pimpl->cached_second_vertex = pimpl->true_second_vertex = 
Chris@16:         source(e, g) == pimpl->anchor ? target(e,g) : source(e,g);
Chris@16:       pimpl->cached_second_edge = e;
Chris@16:     }
Chris@16: 
Chris@16:     inline void store_old_face_handles()
Chris@16:     {
Chris@16:       store_old_face_handles_dispatch(StoreOldHandlesPolicy());
Chris@16:     }
Chris@16: 
Chris@16:     inline vertex_t first_vertex() const
Chris@16:     { 
Chris@16:       return pimpl->cached_first_vertex;
Chris@16:     }
Chris@16:     
Chris@16:     inline vertex_t second_vertex() const 
Chris@16:     { 
Chris@16:       return pimpl->cached_second_vertex;
Chris@16:     }
Chris@16: 
Chris@16:     inline vertex_t true_first_vertex() const 
Chris@16:     { 
Chris@16:       return pimpl->true_first_vertex;
Chris@16:     }
Chris@16: 
Chris@16:     inline vertex_t true_second_vertex() const 
Chris@16:     { 
Chris@16:       return pimpl->true_second_vertex;
Chris@16:     }
Chris@16: 
Chris@16:     inline vertex_t old_first_vertex() const
Chris@16:     {
Chris@16:       return pimpl->old_handles.first_vertex;
Chris@16:     }
Chris@16: 
Chris@16:     inline vertex_t old_second_vertex() const
Chris@16:     {
Chris@16:       return pimpl->old_handles.second_vertex;
Chris@16:     }
Chris@16: 
Chris@16:     inline edge_t old_first_edge() const
Chris@16:     {
Chris@16:       return pimpl->old_handles.first_edge;
Chris@16:     }
Chris@16: 
Chris@16:     inline edge_t old_second_edge() const
Chris@16:     {
Chris@16:       return pimpl->old_handles.second_edge;
Chris@16:     }
Chris@16: 
Chris@16:     inline edge_t first_edge() const
Chris@16:     {
Chris@16:       return pimpl->cached_first_edge;
Chris@16:     }
Chris@16:   
Chris@16:     inline edge_t second_edge() const
Chris@16:     {
Chris@16:       return pimpl->cached_second_edge;
Chris@16:     }
Chris@16:     
Chris@16:     inline vertex_t get_anchor() const
Chris@16:     {
Chris@16:       return pimpl->anchor;
Chris@16:     }
Chris@16:   
Chris@16:     void glue_first_to_second
Chris@16:       (face_handle<Graph,StoreOldHandlesPolicy,StoreEmbeddingPolicy>& bottom)
Chris@16:     {
Chris@16:       pimpl->edge_list.concat_front(bottom.pimpl->edge_list);
Chris@16:       pimpl->true_first_vertex = bottom.pimpl->true_first_vertex;
Chris@16:       pimpl->cached_first_vertex = bottom.pimpl->cached_first_vertex;
Chris@16:       pimpl->cached_first_edge = bottom.pimpl->cached_first_edge;
Chris@16:     }
Chris@16:     
Chris@16:     void glue_second_to_first
Chris@16:       (face_handle<Graph,StoreOldHandlesPolicy,StoreEmbeddingPolicy>& bottom)
Chris@16:     {
Chris@16:       pimpl->edge_list.concat_back(bottom.pimpl->edge_list);
Chris@16:       pimpl->true_second_vertex = bottom.pimpl->true_second_vertex;
Chris@16:       pimpl->cached_second_vertex = bottom.pimpl->cached_second_vertex;
Chris@16:       pimpl->cached_second_edge = bottom.pimpl->cached_second_edge;
Chris@16:     }
Chris@16:   
Chris@16:     void flip()
Chris@16:     {
Chris@16:       pimpl->edge_list.reverse();
Chris@16:       std::swap(pimpl->true_first_vertex, pimpl->true_second_vertex);
Chris@16:       std::swap(pimpl->cached_first_vertex, pimpl->cached_second_vertex);
Chris@16:       std::swap(pimpl->cached_first_edge, pimpl->cached_second_edge);
Chris@16:     }
Chris@16:     
Chris@16:     template <typename OutputIterator>
Chris@16:     void get_list(OutputIterator o_itr)
Chris@16:     {
Chris@16:       pimpl->edge_list.get_list(o_itr);
Chris@16:     }
Chris@16: 
Chris@16:     void reset_vertex_cache()
Chris@16:     {
Chris@16:       pimpl->cached_first_vertex = pimpl->true_first_vertex;
Chris@16:       pimpl->cached_second_vertex = pimpl->true_second_vertex;
Chris@16:     }
Chris@16: 
Chris@16:     inline void set_first_vertex(vertex_t v)
Chris@16:     {
Chris@16:       pimpl->cached_first_vertex = v;
Chris@16:     }
Chris@16: 
Chris@16:     inline void set_second_vertex(vertex_t v)
Chris@16:     {
Chris@16:       pimpl->cached_second_vertex = v;
Chris@16:     }
Chris@16: 
Chris@16:   private:
Chris@16: 
Chris@16:     void store_old_face_handles_dispatch(store_old_handles)
Chris@16:     {
Chris@16:       pimpl->old_handles.first_vertex = pimpl->true_first_vertex;
Chris@16:       pimpl->old_handles.second_vertex = pimpl->true_second_vertex;
Chris@16:       pimpl->old_handles.first_edge = pimpl->cached_first_edge;
Chris@16:       pimpl->old_handles.second_edge = pimpl->cached_second_edge;
Chris@16:     }
Chris@16:   
Chris@16:     void store_old_face_handles_dispatch(no_old_handles) {}
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16:     boost::shared_ptr<impl_t> pimpl;
Chris@16: 
Chris@16:   };
Chris@16: 
Chris@16: 
Chris@16: } /* namespace detail */ } /* namespace graph */ } /* namespace boost */
Chris@16: 
Chris@16: 
Chris@16: #endif //__FACE_HANDLES_HPP__