Comprender boost :: disjoint_sets

Question

Necesito usar boost :: disjoint_sets, pero the documentation no está claro para mí. ¿Puede alguien explicar por qué significa cada parámetro de plantilla, y quizás dar un pequeño código de ejemplo para crear un disjoint_sets?

Según la solicitud, estoy usando disjoint_sets para implementar Tarjan's off-line least common ancestors algorithm, es decir, el tipo de valor debe ser vertex_descriptor.

Answer 1

Lo que puedo entender a partir de la documentación:

necesidad desunido en asociar un rango y un padre (en el árbol de los bosques) para cada elemento. Dado que es posible que desee trabajar con cualquier tipo de datos, puede que, por ejemplo, no siempre quiera utilizar un mapa para el padre: con enteros, una matriz es suficiente. También necesita un rango enemigo para cada elemento (el rango necesario para el descubrimiento de unión).

Tendrá dos "propiedades":

• uno para asociar un número entero a cada elemento (primer argumento de plantilla), el rango
• uno de asociar un elemento a otro una (segunda plantilla argumento), los padres

En un ejemplo:

std::vector<int> rank (100); 
std::vector<int> parent (100); 
boost::disjoint_sets<int*,int*> ds(&rank[0], &parent[0]); 

las matrices son usado &rank[0], &parent[0] para el tipo en la plantilla es int*

Para un ejemplo más complejo (usando mapas) puede mirar la respuesta de Ugo.

Usted le está dando al algoritmo dos estructuras para almacenar los datos (rango/principal) que necesita.

Answer 2

disjoint_sets<Rank, Parent, FindCompress> 

• Rango PropertyMap utiliza para almacenar el tamaño de un conjunto (elemento -> std :: size_t). Ver union by rank
• Parent PropertyMap utilizado para almacenar el elemento principal de un elemento (elemento -> elemento). Ver Path compression
• FindCompress Argumento opcional que define el método de búsqueda. Predeterminado a find_with_full_path_compression Ver here (el valor predeterminado debería ser el que necesita).

Ejemplo:

template <typename Rank, typename Parent> 
void algo(Rank& r, Parent& p, std::vector<Element>& elements) 
{ 
boost::disjoint_sets<Rank,Parent> dsets(r, p); 
for (std::vector<Element>::iterator e = elements.begin(); 
     e != elements.end(); e++) 
    dsets.make_set(*e); 
    ... 
} 

int main() 
{ 
    std::vector<Element> elements; 
    elements.push_back(Element(...)); 
    ... 

    typedef std::map<Element,std::size_t> rank_t; // => order on Element 
    typedef std::map<Element,Element> parent_t; 
    rank_t rank_map; 
    parent_t parent_map; 

    boost::associative_property_map<rank_t> rank_pmap(rank_map); 
    boost::associative_property_map<parent_t> parent_pmap(parent_map); 

    algo(rank_pmap, parent_pmap, elements); 
} 

Tenga en cuenta que "El Boost Propiedad Cartoteca contiene unos adaptadores que convierten comúnmente utilizados estructuras de datos que implementan una operación de asignación, tales como matrices incorporadas (punteros), iteradores, y std :: map, para tener la interfaz del mapa de propiedades "

Esta lista de estos adaptadores (como boost :: asociative_property_map) se puede encontrar en here.

Answer 3

Para aquellos de ustedes que no pueden pagar los gastos indirectos de std::map (o no se puede utilizar porque no tiene constructor por defecto en su clase), pero cuyos datos no es tan simple como int, escribí a guide a una solución usando std::vector, que es algo óptimo cuando se conoce el número total de elementos de antemano.

La guía incluye un fully-working sample code que puede descargar y probar por su cuenta.

La solución mencionada allí supone que usted tiene el control del código de la clase para que, en particular, pueda agregar algunos atributos. Si esto aún no es posible, siempre se puede añadir una envoltura alrededor de él:

class Wrapper { 
    UntouchableClass const& mInstance; 
    size_t dsID; 
    size_t dsRank; 
    size_t dsParent; 
} 

Por otra parte, si se conoce el número de elementos a ser pequeña, no hay necesidad de size_t, en cuyo caso se puede añadir un poco de plantilla para el tipo UnsignedInt y decide en tiempo de ejecución crear una instancia con uint8_t, uint16_t, uint32_t o uint64_t, que puedes obtener con <cstdint> en C++ 11 o con boost::cstdint en caso contrario.

template <typename UnsignedInt> 
class Wrapper { 
    UntouchableClass const& mInstance; 
    UnsignedInt dsID; 
    UnsignedInt dsRank; 
    UnsignedInt dsParent; 
} 

Aquí está el enlace de nuevo en caso de que no: http://janoma.cl/post/using-disjoint-sets-with-a-vector/