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