Implementando relaciones de equivalencia en C++ (usando boost :: disjoint_sets)

Question

Supongamos que tiene muchos elementos, y necesita realizar un seguimiento de las relaciones de equivalencia entre ellos. Si el elemento A es equivalente al elemento B, es equivalente a todos los otros elementos B es equivalente a.

Estoy buscando una estructura de datos eficiente para codificar esta información. Debería ser posible agregar dinámicamente nuevos elementos a través de una equivalencia con un elemento existente, y a partir de esa información debería ser posible calcular eficientemente todos los elementos a los que el nuevo elemento es equivalente.

Por ejemplo, considere los siguientes conjuntos de equivalencia de los elementos [0,1,2,3,4]:

0 = 1 = 2 
3 = 4 

donde el signo de igualdad de puntos marca equivalencia. Ahora añadimos un nuevo elemento 5

0 = 1 = 2 
3 = 4 
5 

y hacer cumplir la equivalencia 5=3, la estructura de datos se convierte en

0 = 1 = 2 
3 = 4 = 5 

partir de esto, uno debe ser capaz de repetir de manera eficiente a través de la equivalencia establecida para cualquier elemento. Para 5, este conjunto sería [3,4,5].

Boost ya proporciona una estructura de datos conveniente llamada disjoint_sets que parece cumplir con la mayoría de mis requisitos. Considere este sencillo programa que illustates cómo implementar el ejemplo anterior:

#include <cstdio> 
#include <vector> 
#include <boost/pending/disjoint_sets.hpp> 
#include <boost/unordered/unordered_set.hpp> 

/* 
    Equivalence relations 
    0 = 1 = 2 
    3 = 4 
*/ 

int main(int , char* []) 
{ 
    typedef std::vector<int> VecInt; 
    typedef boost::unordered_set<int> SetInt; 

    VecInt rank (100); 
    VecInt parent (100); 
    boost::disjoint_sets<int*,int*> ds(&rank[0], &parent[0]); 
    SetInt elements; 
    for (int i=0; i<5; ++i) { 
     ds.make_set(i); 
     elements.insert(i); 
    } 

    ds.union_set(0,1); 
    ds.union_set(1,2); 
    ds.union_set(3,4); 

    printf("Number of sets:\n\t%d\n", (int)ds.count_sets(elements.begin(), elements.end())); 

    // normalize set so that parent is always the smallest number 
    ds.normalize_sets(elements.begin(), elements.end()); 
    for (SetInt::const_iterator i = elements.begin(); i != elements.end(); ++i) { 
     printf("%d %d\n", *i, ds.find_set(*i)); 
    } 

    return 0; 
} 

Como se ha visto anteriormente se puede añadir de manera eficiente los elementos, de forma dinámica y ampliar los conjuntos disjuntos. ¿Cómo se puede iterar eficientemente sobre los elementos de un único conjunto disjunto, sin tener que iterar sobre todos los elementos?

Answer 1

Lo más probable es que no pueda hacer eso, disjoint_sets no admite la iteración en un solo conjunto. La estructura de datos subyacente y los algoritmos no podrían hacerlo de manera eficiente de todos modos, es decir, incluso si hubiera compatibilidad incorporada en disjoint_sets para la iteración en un solo conjunto, eso sería tan lento como iterar sobre todos los conjuntos y filtrar el error conjuntos.