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