Comprendre boost :: disjoint_sets

Question

J'ai besoin d'utiliser boost::disjoint_sets, mais la documentation n'est pas claire pour moi. Quelqu'un peut-il expliquer ce que chaque paramètre du modèle moyen, et peut-être donner un petit exemple de code pour la création d'un disjoint_sets?

Selon la demande, je suis en utilisant disjoint_sets à mettre en œuvre Tarjan est hors-ligne moins ancêtres communs algorithme, j'.e - le type de la valeur doit être vertex_descriptor.

Answer 1

Ce que je peux comprendre de la documentation :

Disjoints besoin d'associer un rang et d'un parent (dans la forêt de l'arbre) pour chaque élément. Depuis que vous pourriez vouloir travailler avec n'importe quel type de données vous pouvez,par exemple, de ne pas toujours utiliser la carte pour le parent: avec entier un tableau est suffisant. Vous avez également besoin d'un rang pour chaque élément (le rang nécessaire pour l'union-find).

Vous aurez besoin de deux "propriétés" :

• l'un d'associer un entier à chaque élément (le premier argument de modèle), le rang
• l'un d'associer un élément à un autre (deuxième argument de modèle), 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és &rank[0], &parent[0] pour le type dans le modèle est - int*

Pour un exemple plus complexe (à l'aide de cartes), vous pouvez regarder Ugo de réponse.

Vous êtes juste de donner à l'algorithme de deux structures pour stocker les données (rang/parent) 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 l'union par rang
• Parent PropertyMap utilisé pour stocker le parent d'un élément (élément -> element). Voir Chemin de compression
• FindCompress argument Optionnel de la définition de la méthode find. Par défaut find_with_full_path_compression Voir ici (par Défaut devrait être ce que 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 poussée de La Carte de Propriété de la Bibliothèque contient quelques adaptateurs qui convertissent les données couramment utilisés des structures qui mettent en œuvre une opération de cartographie, comme builtin tableaux (pointeurs), itérateurs, et std::map, avoir la carte de propriété de l'interface"

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

Answer 3

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

Le guide inclut pleinement-travail exemple de code que vous pouvez télécharger et de le tester sur votre propre.

La solution qu'il suppose que vous avez le contrôle de la classe dans le code de sorte que, en particulier, vous pouvez ajouter quelques attributs. Si ce n'est toujours pas possible, vous pouvez toujours ajouter un wrapper autour d'elle:

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

Par ailleurs, si vous connaissez le nombre d'éléments à petit, il n'y a pas besoin d' size_t, dans ce cas, vous pouvez ajouter un peu de modèle pour l' UnsignedInt type et de décider en exécution de l'instancier avec uint8_t, uint16_t, uint32_tou 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 de nouveau le lien au cas où vous l'auriez manqué: http://janoma.cl/post/using-disjoint-sets-with-a-vector/