Implementazione delle relazioni di equivalenza in C++ (utilizzando boost :: disjoint_sets)

Question

Si supponga di avere molti elementi e di tenere traccia delle relazioni di equivalenza tra di loro. Se l'elemento A è equivalente all'elemento B, è equivalente a tutti gli altri elementi B è equivalente a.

Sto cercando una struttura dati efficiente per codificare queste informazioni. Dovrebbe essere possibile aggiungere dinamicamente nuovi elementi attraverso un'equivalenza con un elemento esistente e da tali informazioni dovrebbe essere possibile calcolare in modo efficiente tutti gli elementi a cui il nuovo elemento è equivalente.

Ad esempio, considerare i seguenti gruppi di equivalenza degli elementi [0,1,2,3,4]:

0 = 1 = 2 
3 = 4 

dove il segno uguaglianza denota equivalenza. Ora si aggiunge un nuovo elemento 5

0 = 1 = 2 
3 = 4 
5 

e far rispettare l'equivalenza 5=3, la struttura di dati diventa

0 = 1 = 2 
3 = 4 = 5 

Da questo, si dovrebbe essere in grado di scorrere in modo efficiente attraverso l'equivalenza impostare per ogni elemento. Per 5, questo set sarebbe [3,4,5].

Boost fornisce già una comoda struttura dati chiamata disjoint_sets che sembra soddisfare la maggior parte delle mie esigenze. Considerate questo semplice programma che illustates come implementare l'esempio di cui sopra:

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

Come visto sopra si possono aggiungere elementi in modo efficiente, e dinamicamente ampliare gli insiemi disgiunti. Come si può iterare in modo efficiente sugli elementi di un singolo insieme disgiunto, senza dover iterare su tutti gli elementi?

Answer 1

Molto probabilmente non è possibile farlo, disjoint_sets non supporta l'iterazione su un solo set. La struttura e gli algoritmi di dati sottostanti non sarebbero in grado di farlo in ogni caso in modo efficiente, vale a dire anche se c'era un supporto integrato a disjoint_sets per l'iterazione su un solo set, che sarebbe lento come iterare su tutti gli insiemi e filtrare in modo errato imposta.