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
disjoint_sets.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\pending\disjoint_sets.hpp
Girar
Efecto
Propiedad
Historial
// //======================================================================= // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek // // 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_DISJOINT_SETS_HPP #define BOOST_DISJOINT_SETS_HPP #include
#include
#include
namespace boost { struct find_with_path_halving { template
Vertex operator()(ParentPA p, Vertex v) { return detail::find_representative_with_path_halving(p, v); } }; struct find_with_full_path_compression { template
Vertex operator()(ParentPA p, Vertex v){ return detail::find_representative_with_full_compression(p, v); } }; // This is a generalized functor to provide disjoint sets operations // with "union by rank" and "path compression". A disjoint-set data // structure maintains a collection S={S1, S2, ..., Sk} of disjoint // sets. Each set is identified by a representative, which is some // member of of the set. Sets are represented by rooted trees. Two // heuristics: "union by rank" and "path compression" are used to // speed up the operations. // Disjoint Set requires two vertex properties for internal use. A // RankPA and a ParentPA. The RankPA must map Vertex to some Integral type // (preferably the size_type associated with Vertex). The ParentPA // must map Vertex to Vertex. template
class disjoint_sets { typedef disjoint_sets self; inline disjoint_sets() {} public: inline disjoint_sets(RankPA r, ParentPA p) : rank(r), parent(p) {} inline disjoint_sets(const self& c) : rank(c.rank), parent(c.parent) {} // Make Set -- Create a singleton set containing vertex x template
inline void make_set(Element x) { put(parent, x, x); typedef typename property_traits
::value_type R; put(rank, x, R()); } // Link - union the two sets represented by vertex x and y template
inline void link(Element x, Element y) { detail::link_sets(parent, rank, x, y, rep); } // Union-Set - union the two sets containing vertex x and y template
inline void union_set(Element x, Element y) { link(find_set(x), find_set(y)); } // Find-Set - returns the Element representative of the set // containing Element x and applies path compression. template
inline Element find_set(Element x) { return rep(parent, x); } template
inline std::size_t count_sets(ElementIterator first, ElementIterator last) { std::size_t count = 0; for ( ; first != last; ++first) if (get(parent, *first) == *first) ++count; return count; } template
inline void normalize_sets(ElementIterator first, ElementIterator last) { for (; first != last; ++first) detail::normalize_node(parent, *first); } template
inline void compress_sets(ElementIterator first, ElementIterator last) { for (; first != last; ++first) detail::find_representative_with_full_compression(parent, *first); } protected: RankPA rank; ParentPA parent; FindCompress rep; }; template
class disjoint_sets_with_storage { typedef typename property_traits
::value_type Index; typedef std::vector
ParentContainer; typedef std::vector
RankContainer; public: typedef typename ParentContainer::size_type size_type; disjoint_sets_with_storage(size_type n = 0, ID id_ = ID(), InverseID inv = InverseID()) : id(id_), id_to_vertex(inv), rank(n, 0), parent(n) { for (Index i = 0; i < n; ++i) parent[i] = i; } // note this is not normally needed template
inline void make_set(Element x) { parent[x] = x; rank[x] = 0; } template
inline void link(Element x, Element y) { extend_sets(x,y); detail::link_sets(&parent[0], &rank[0], get(id,x), get(id,y), rep); } template
inline void union_set(Element x, Element y) { Element rx = find_set(x); Element ry = find_set(y); link(rx, ry); } template
inline Element find_set(Element x) { return id_to_vertex[rep(&parent[0], get(id,x))]; } template
inline std::size_t count_sets(ElementIterator first, ElementIterator last) { std::size_t count = 0; for ( ; first != last; ++first) if (parent[*first] == *first) ++count; return count; } template
inline void normalize_sets(ElementIterator first, ElementIterator last) { for (; first != last; ++first) detail::normalize_node(&parent[0], *first); } template
inline void compress_sets(ElementIterator first, ElementIterator last) { for (; first != last; ++first) detail::find_representative_with_full_compression(&parent[0], *first); } const ParentContainer& parents() { return parent; } protected: template
inline void extend_sets(Element x, Element y) { Index needed = get(id,x) > get(id,y) ? get(id,x) + 1 : get(id,y) + 1; if (needed > parent.size()) { rank.insert(rank.end(), needed - rank.size(), 0); for (Index k = parent.size(); k < needed; ++k) parent.push_back(k); } } ID id; InverseID id_to_vertex; RankContainer rank; ParentContainer parent; FindCompress rep; }; } // namespace boost #endif // BOOST_DISJOINT_SETS_HPP
disjoint_sets.hpp
Dirección de la página
Dirección del archivo
Anterior
5/21
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.