Comprendre boost :: disjoint_sets

Question

Je dois utiliser boost :: disjoint_sets, mais the documentation n'est pas clair pour moi. Quelqu'un peut-il expliquer ce que signifie chaque paramètre de modèle, et peut-être donner un petit exemple de code pour créer un disjoint_sets?

Selon la demande, j'utilise disjoint_sets pour implémenter Tarjan's off-line least common ancestors algorithm, c'est-à-dire que le type de valeur doit être vertex_descriptor.

Answer 1

Ce que je peux comprendre de la documentation:

besoin disjoints d'associer un rang et un parent (dans l'arbre de la forêt) à chaque élément. Puisque vous voudrez peut-être travailler avec n'importe quel type de données, vous pouvez, par exemple, ne pas toujours vouloir utiliser une carte pour le parent: avec un entier, un tableau est suffisant. Vous avez également besoin d'un ennemi de rang chaque élément (le rang nécessaire pour l'union-trouver).

Vous aurez besoin de deux « propriétés »:

• un à associer un entier à chaque élément (premier argument de modèle), le rang
• un pour associer un élément à un autre (deuxième modèle argument), les pères

Sur un exemple:

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

les tableaux sont utilisé &rank[0], &parent[0] pour le type dans le modèle est int*

Pour un exemple plus complexe (en utilisant des cartes) vous pouvez regarder la réponse d'Ugo.

Vous donnez simplement à l'algorithme deux structures pour stocker les données (rang/parent) dont il a besoin.

Answer 2

disjoint_sets<Rank, Parent, FindCompress> 

• Rang PropertyMap utilisé pour stocker la taille d'un ensemble (élément -> std :: size_t). Voir union by rank
• Parent PropertyMap utilisé pour stocker le parent d'un élément (élément -> élément). Voir Path compression
• FindCompress Argument facultatif définissant la méthode find. Par défaut à find_with_full_path_compression Voir here (La valeur par défaut devrait correspondre à ce dont vous avez besoin).

Exemple:

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

Notez que « La bibliothèque Boost propriété Map contient quelques adaptateurs qui convertissent couramment utilisés structures-données qui mettent en œuvre une opération de cartographie, tels que des tableaux prédéfinis (pointeurs), itérateurs, et std :: map, pour avoir l'interface de carte de propriétés "

Cette liste de ces adaptateurs (comme boost :: associative_property_map) peut être trouvée here.

Answer 3

Pour ceux d'entre vous qui ne peuvent pas se permettre les frais généraux de std::map (ou ne peut pas l'utiliser parce que vous n'avez pas constructeur par défaut dans votre classe), mais dont les données ne sont pas aussi simple que int, je l'ai écrit a guide à une solution en utilisant std::vector, ce qui est plutôt optimal lorsque vous connaissez le nombre total d'éléments à l'avance.

Le guide comprend un fully-working sample code que vous pouvez télécharger et tester par vous-même.

La solution mentionnée ici suppose que vous avez le contrôle du code de la classe afin que vous puissiez en particulier ajouter certains attributs. Si cela est toujours pas possible, vous pouvez toujours ajouter une enveloppe autour:

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

De plus, si vous connaissez le nombre d'éléments à petit, il n'y a pas besoin de size_t, auquel cas vous pouvez ajouter un peu de modèle pour le type UnsignedInt et décider à l'exécution de l'instancier avec uint8_t, uint16_t, uint32_t ou uint64_t, que vous pouvez obtenir avec <cstdint> en C++ 11 ou avec boost::cstdint sinon.

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

Voici le lien à nouveau dans le cas où vous l'avez manqué: http://janoma.cl/post/using-disjoint-sets-with-a-vector/