Implementieren von Äquivalenzrelationen in C++ (mit boost :: disjoint_sets)

Question

Angenommen, Sie haben viele Elemente, und Sie müssen die Äquivalenzbeziehungen zwischen ihnen im Auge behalten. Wenn Element A äquivalent zu Element B ist, ist es äquivalent zu allen anderen Elementen, denen B äquivalent ist.

Ich bin auf der Suche nach einer effizienten Datenstruktur, um diese Informationen zu kodieren. Es sollte möglich sein, neue Elemente durch eine Äquivalenz mit einem vorhandenen Element dynamisch hinzuzufügen, und aus diesen Informationen sollte es möglich sein, alle Elemente, denen das neue Element entspricht, effizient zu berechnen.

Betrachten wir zum Beispiel die folgenden Äquivalenzsätze der Elemente [0,1,2,3,4]:

0 = 1 = 2 
3 = 4 

wo das Gleichheitszeichen Äquivalenz bezeichnet. Nun fügen wir ein neues Element 5

0 = 1 = 2 
3 = 4 
5 

und Durchsetzung der Gleichwertigkeit 5=3, wird die Datenstruktur

0 = 1 = 2 
3 = 4 = 5 

Daraus sollte man in der Lage sein, effizient durch die Äquivalenz für jedes Element zu durchlaufen. Für 5 wäre dieser Satz [3,4,5].

Boost bietet bereits eine komfortable Datenstruktur namens disjoint_sets, die die meisten meiner Anforderungen zu erfüllen scheint. Betrachten Sie dieses einfache Programm, das illustates, wie das obige Beispiel implementieren:

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

Wie oben gesehen ein effizienten Elemente hinzufügen kann, und dynamisch die disjunkten Mengen erweitern. Wie kann man effizient über die Elemente einer einzelnen disjunkten Menge iterieren, ohne über alle Elemente hinweg iterieren zu müssen?

Answer 1

Höchstwahrscheinlich können Sie das nicht tun, disjoint_sets unterstützt Iteration nicht nur über einen Satz. Die zugrundeliegende Datenstruktur und Algorithmen wären nicht in der Lage, dies auf effiziente Weise zu tun, dh selbst wenn die Unterstützung für die Iteration über nur eine Menge in disjoint_sets integriert wäre, wäre das genauso langsam wie das Iterieren über alle Mengen und das Ausfiltern falsch Sätze.