x
Yes
No
Do you want to visit DriveHQ English website?
Inicio
Características
Precios
Prueba gratuita
Software cliente
Acerca de nosotros
Servidor de archivos
|
Solución de copias de seguridad
|
Servidor FTP
|
Servidor de correo electrónico
|
Alojamiento web
|
Software cliente
Servidor de archivos
Solución de copia de seguridad
Servidor FTP
Servidor de correo electrónico
Alojamiento web
Software cliente
face_handles.hpp - Hosted on DriveHQ Cloud IT Platform
Arriba
Subir
Descargar
Compartir
Publicar
Nueva carpeta
Nuevo archivo
Copiar
Cortar
Eliminar
Pegar
Clasificación
Actualizar
Ruta de la carpeta: \\game3dprogramming\materials\GameFactory\GameFactoryDemo\references\boost_1_35_0\boost\graph\planar_detail\face_handles.hpp
Girar
Efecto
Propiedad
Historial
//======================================================================= // 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
#include
#include
// 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
struct lazy_list_node { typedef shared_ptr< lazy_list_node
> 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
m_left_child; shared_ptr
m_right_child; }; template
struct old_handles_storage; template
struct old_handles_storage
{ Vertex first_vertex; Vertex second_vertex; Edge first_edge; Edge second_edge; }; template
struct old_handles_storage
{}; template
struct edge_list_storage; template
struct edge_list_storage
{ typedef void type; void push_back(Edge) {} void push_front(Edge) {} void reverse() {} void concat_front(edge_list_storage
) {} void concat_back(edge_list_storage
) {} template
void get_list(OutputIterator) {} }; template
struct edge_list_storage
{ typedef lazy_list_node
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
other) { value = type(new node_type(other.value, value)); } void concat_back(edge_list_storage
other) { value = type(new node_type(value, other.value)); } template
void get_list(OutputIterator out) { get_list_helper(out, value); } private: template
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
struct edge_list_storage
{ typedef std::list
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
other) { value.splice(value.begin(), other.value); } void concat_back(edge_list_storage
other) { value.splice(value.end(), other.value); } template
void get_list(OutputIterator out) { std::copy(value.begin(), value.end(), out); } }; template
struct face_handle_impl { typedef typename graph_traits
::vertex_descriptor vertex_t; typedef typename graph_traits
::edge_descriptor edge_t; typedef typename edge_list_storage
::type edge_list_storage_t; face_handle_impl() : cached_first_vertex(graph_traits
::null_vertex()), cached_second_vertex(graph_traits
::null_vertex()), true_first_vertex(graph_traits
::null_vertex()), true_second_vertex(graph_traits
::null_vertex()), anchor(graph_traits
::null_vertex()) { initialize_old_vertices_dispatch(StoreOldHandlesPolicy()); } void initialize_old_vertices_dispatch(store_old_handles) { old_handles.first_vertex = graph_traits
::null_vertex(); old_handles.second_vertex = graph_traits
::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
edge_list; old_handles_storage
old_handles; }; template
class face_handle { public: typedef typename graph_traits
::vertex_descriptor vertex_t; typedef typename graph_traits
::edge_descriptor edge_t; typedef face_handle_impl
impl_t; typedef face_handle
self_t; face_handle(vertex_t anchor = graph_traits
::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
& 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
& 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
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
pimpl; }; } /* namespace detail */ } /* namespace graph */ } /* namespace boost */ #endif //__FACE_HANDLES_HPP__
face_handles.hpp
Dirección de la página
Dirección del archivo
Anterior
4/5
Siguiente
Descargar
( 13 KB )
Comments
Total ratings:
0
Average rating:
No clasificado
of 10
Would you like to comment?
Join now
, or
Logon
if you are already a member.