boost/graph/planar_detail/face_handles.hpp
//=======================================================================
// 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__