//======================================================================= | |
// 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__ |