Implémentation des relations d'équivalence en C++ (using boost :: disjoint_sets)

Question

Supposons que vous ayez beaucoup d'éléments et que vous ayez besoin de garder une trace des relations d'équivalence entre eux. Si l'élément A est équivalent à l'élément B, il est équivalent à tous les autres éléments auxquels B est équivalent.

Je cherche une structure de données efficace pour encoder cette information. Il devrait être possible d'ajouter dynamiquement de nouveaux éléments grâce à une équivalence avec un élément existant, et à partir de cette information, il devrait être possible de calculer efficacement tous les éléments auxquels le nouvel élément est équivalent.

Par exemple, considérons les ensembles d'équivalence suivants des éléments [0,1,2,3,4]:

0 = 1 = 2 
3 = 4 

où le signe d'égalité équivalence désigne. Maintenant, nous ajoutons un nouvel élément 5

0 = 1 = 2 
3 = 4 
5 

et de faire respecter l'équivalence 5=3, la structure de données devient

0 = 1 = 2 
3 = 4 = 5 

De là, on devrait pouvoir itérer efficacement grâce à l'équivalence établie pour tout élément. Pour 5, cet ensemble serait [3,4,5].

Boost fournit déjà une structure de données pratique appelée disjoint_sets qui semble répondre à la plupart de mes besoins. Considérez ce programme simple qui illustates comment mettre en œuvre l'exemple ci-dessus:

#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; 
} 

Comme on le voit ci-dessus, on peut efficacement ajouter des éléments, et développer dynamiquement les ensembles disjoints. Comment peut-on efficacement itérer sur les éléments d'un même ensemble disjoint, sans avoir à parcourir tous les éléments?

Answer 1

Vous ne pouvez probablement pas faire cela, disjoint_sets ne prend pas en charge l'itération sur un seul ensemble. La structure de données sous-jacente et les algorithmes ne seraient pas en mesure de le faire de manière efficace, même s'il y avait un support intégré à disjoint_sets pour l'itération sur un seul ensemble, ce qui serait aussi lent que d'itérer sur tous les ensembles, et de filtrer mal ensembles.