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
sparse_ordering.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\detail\sparse_ordering.hpp
Girar
Efecto
Propiedad
Historial
//======================================================================= // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. // Copyright 2004, 2005 Trustees of Indiana University // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, // Doug Gregor, D. Kevin McGrath // // 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 BOOST_GRAPH_DETAIL_SPARSE_ORDERING_HPP #define BOOST_GRAPH_DETAIL_SPARSE_ORDERING_HPP #include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
namespace boost { namespace sparse { // rcm_queue // // This is a custom queue type used in the // *_ordering algorithms. // In addition to the normal queue operations, the // rcm_queue provides: // // int eccentricity() const; // value_type spouse() const; // // yes, it's a bad name...but it works, so use it template < class Vertex, class DegreeMap, class Container = std::deque
> class rcm_queue : public std::queue
{ typedef std::queue
base; public: typedef typename base::value_type value_type; typedef typename base::size_type size_type; /* SGI queue has not had a contructor queue(const Container&) */ inline rcm_queue(DegreeMap deg) : _size(0), Qsize(1), eccen(-1), degree(deg) { } inline void pop() { if ( !_size ) Qsize = base::size(); base::pop(); if ( _size == Qsize-1 ) { _size = 0; ++eccen; } else ++_size; } inline value_type& front() { value_type& u = base::front(); if ( _size == 0 ) w = u; else if (get(degree,u) < get(degree,w) ) w = u; return u; } inline const value_type& front() const { const value_type& u = base::front(); if ( _size == 0 ) w = u; else if (get(degree,u) < get(degree,w) ) w = u; return u; } inline value_type& top() { return front(); } inline const value_type& top() const { return front(); } inline size_type size() const { return base::size(); } inline size_type eccentricity() const { return eccen; } inline value_type spouse() const { return w; } protected: size_type _size; size_type Qsize; int eccen; mutable value_type w; DegreeMap degree; }; template
> class sparse_ordering_queue : public boost::queue
{ public: typedef typename Sequence::iterator iterator; typedef typename Sequence::reverse_iterator reverse_iterator; typedef queue
base; typedef typename Sequence::size_type size_type; inline iterator begin() { return this->c.begin(); } inline reverse_iterator rbegin() { return this->c.rbegin(); } inline iterator end() { return this->c.end(); } inline reverse_iterator rend() { return this->c.rend(); } inline Tp &operator[](int n) { return this->c[n]; } inline size_type size() {return this->c.size(); } protected: //nothing }; } // namespace sparse // Compute Pseudo peripheral // // To compute an approximated peripheral for a given vertex. // Used in
king_ordering
algorithm. // template
Vertex pseudo_peripheral_pair(Graph& G, const Vertex& u, int& ecc, ColorMap color, DegreeMap degree) { typedef typename property_traits
::value_type ColorValue; typedef color_traits
Color; sparse::rcm_queue
Q(degree); typename boost::graph_traits
::vertex_iterator ui, ui_end; for (tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui) if (get(color, *ui) != Color::red()) put(color, *ui, Color::white()); breadth_first_visit(G, u, buffer(Q).color_map(color)); ecc = Q.eccentricity(); return Q.spouse(); } // Find a good starting node // // This is to find a good starting node for the // king_ordering algorithm. "good" is in the sense // of the ordering generated by RCM. // template
Vertex find_starting_node(Graph& G, Vertex r, Color color, Degree degree) { Vertex x, y; int eccen_r, eccen_x; x = pseudo_peripheral_pair(G, r, eccen_r, color, degree); y = pseudo_peripheral_pair(G, x, eccen_x, color, degree); while (eccen_x > eccen_r) { r = x; eccen_r = eccen_x; x = y; y = pseudo_peripheral_pair(G, x, eccen_x, color, degree); } return x; } template
class out_degree_property_map : public put_get_helper
::degree_size_type, out_degree_property_map
> { public: typedef typename graph_traits
::vertex_descriptor key_type; typedef typename graph_traits
::degree_size_type value_type; typedef value_type reference; typedef readable_property_map_tag category; out_degree_property_map(const Graph& g) : m_g(g) { } value_type operator[](const key_type& v) const { return out_degree(v, m_g); } private: const Graph& m_g; }; template
inline out_degree_property_map
make_out_degree_map(const Graph& g) { return out_degree_property_map
(g); } } // namespace boost #endif // BOOST_GRAPH_KING_HPP
sparse_ordering.hpp
Dirección de la página
Dirección del archivo
Anterior
16/16 Siguiente
Descargar
( 6 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.