Verstehen von boost::disjoint_sets

Question

Ich muss boost::disjoint_sets verwenden, aber die Dokumentation ist für mich unklar. Kann mir jemand erklären, was die einzelnen Template-Parameter bedeuten, und vielleicht einen kleinen Beispielcode für die Erstellung einer disjoint_sets geben?

Wie gewünscht, verwende ich disjoint_sets zur Implementierung von Tarjans Offline-Algorithmus für die kleinsten gemeinsamen Vorfahren d.h. der Wertetyp sollte vertex_descriptor sein.

Answer 1

Was ich aus der Dokumentation entnehmen kann:

Disjoint müssen jedem Element einen Rang und ein Elternteil (im Waldbaum) zuordnen. Da Sie mit jeder Art von Daten arbeiten möchten, müssen Sie beispielsweise nicht immer eine Karte für das übergeordnete Element verwenden: Bei Ganzzahlen reicht ein Array aus. Sie brauchen auch einen Rang für jedes Element (den Rang, der für die Union-Findung benötigt wird).

Sie benötigen zwei "Eigenschaften":

• eine, um jedem Element eine ganze Zahl zuzuordnen (erstes Template-Argument), der Rang
• eines, um ein Element mit einem anderen zu verbinden (zweites Argument der Vorlage), die Väter

Ein Beispiel:

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

Arrays werden verwendet &rank[0], &parent[0] zum Typ in der Vorlage ist int*

Für ein komplexeres Beispiel (mit Karten) können Sie sich Ugos Antwort ansehen.

Sie geben dem Algorithmus lediglich zwei Strukturen zur Speicherung der benötigten Daten (Rang/Eltern).

Answer 2

disjoint_sets<Rank, Parent, FindCompress>

• Rang PropertyMap zum Speichern der Größe einer Menge (Element -> std::size_t). Siehe Vereinigung nach Rang
• Elternteil PropertyMap zum Speichern des übergeordneten Elements (Element -> Element). Siehe Pfadkomprimierung
• FindCompress Optionales Argument zur Definition der Suchmethode. Standardmäßig auf find_with_full_path_compression Siehe aquí (Die Standardeinstellung sollte Ihren Bedürfnissen entsprechen).

Beispiel:

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

Die Boost Property Map Library enthält einige Adapter, die häufig verwendete Datenstrukturen, die eine Mapping-Operation implementieren, wie z. B. eingebaute Arrays (Zeiger), Iteratoren und std::map, in die Property Map-Schnittstelle konvertieren.

Die Liste dieser Adaptoren (wie boost::associative_property_map) finden Sie hier aquí .

Answer 3

Für diejenigen unter Ihnen, die sich die Kosten für std::map (oder ihn nicht verwenden können, weil Sie keinen Standardkonstruktor in Ihrer Klasse haben), deren Daten aber nicht so einfach sind wie int schrieb ich ein Leitfaden zu einer Lösung mit std::vector was ziemlich optimal ist, wenn man die Gesamtzahl der Elemente vorher kennt.

Der Leitfaden enthält eine voll funktionsfähiger Beispielcode die Sie herunterladen und selbst testen können.

Die dort genannte Lösung setzt voraus, dass Sie die Kontrolle über den Code der Klasse haben, so dass Sie insbesondere einige Attribute hinzufügen können. Wenn dies immer noch nicht möglich ist, können Sie immer noch einen Wrapper um die Klasse hinzufügen:

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

Wenn Sie wissen, dass die Anzahl der Elemente gering ist, brauchen Sie außerdem keine size_t in diesem Fall können Sie eine Vorlage für die UnsignedInt Typs und entscheiden zur Laufzeit, ihn mit uint8_t , uint16_t , uint32_t o uint64_t , die Sie mit <cstdint> in C++11 oder mit boost::cstdint sonst.

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

Hier ist der Link noch einmal, falls Sie ihn verpasst haben: http://janoma.cl/post/using-disjoint-sets-with-a-vector/

Answer 4

Loic's Antwort sieht gut zu mir, aber ich brauchte, um die Eltern zu initialisieren, so dass jedes Element hatte sich als Elternteil, so dass ich die iota Funktion, um eine aufsteigende Folge zu erzeugen, die bei 0 beginnt.

Mit Boost, und ich importierte bits/stdc++.h und verwendet using namespace std der Einfachheit halber.

#include <bits/stdc++.h>

#include <boost/pending/disjoint_sets.hpp>
#include <boost/unordered/unordered_set.hpp>
using namespace std;

int main() {
  array<int, 100> rank;
  array<int, 100> parent;

  iota(parent.begin(), parent.end(), 0);
  boost::disjoint_sets<int*, int*> ds(rank.begin(), parent.begin());

  ds.union_set(1, 2);
  ds.union_set(1, 3);
  ds.union_set(1, 4);

  cout << ds.find_set(1) << endl;  // 1 or 2 or 3 or 4
  cout << ds.find_set(2) << endl;  // 1 or 2 or 3 or 4
  cout << ds.find_set(3) << endl;  // 1 or 2 or 3 or 4
  cout << ds.find_set(4) << endl;  // 1 or 2 or 3 or 4
  cout << ds.find_set(5) << endl;  // 5
  cout << ds.find_set(6) << endl;  // 6
}

Ich änderte std::vector a std::array weil das Hinzufügen von Elementen zu einem Vektor dazu führt, dass dieser seine Daten neu zuweist, wodurch die Verweise, die das Objekt disjunkte Mengen enthält, ungültig werden.

Soweit ich weiß, ist es nicht garantiert, dass das Elternteil eine bestimmte Zahl ist, deshalb habe ich geschrieben 1 or 2 or 3 or 4 (es kann jeder dieser Punkte sein). Vielleicht wird in der Dokumentation genauer erklärt, welche Nummer als Anführer der Gruppe gewählt wird (ich habe sie nicht studiert).

In meinem Fall lautet die Ausgabe:

2
2
2
2
5
6

Scheint einfach zu sein, kann aber wahrscheinlich verbessert werden, um es (irgendwie) robuster zu machen.

Anmerkung: std::iota Füllt den Bereich [first, last) mit sequentiell ansteigenden Werten, beginnend mit value und wiederholter Auswertung von ++value. Mehr: https://en.cppreference.com/w/cpp/algorithm/iota

Answer 5

Ich habe vor einer Weile eine einfache Implementierung geschrieben. Schauen Sie mal rein.

struct DisjointSet {
    vector<int> parent;
    vector<int> size;

    DisjointSet(int maxSize) {
        parent.resize(maxSize);
        size.resize(maxSize);
        for (int i = 0; i < maxSize; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    int find_set(int v) {
        if (v == parent[v])
            return v;
        return parent[v] = find_set(parent[v]);
    }

    void union_set(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if (a != b) {
            if (size[a] < size[b])
                swap(a, b);
            parent[b] = a;
            size[a] += size[b];
        }
    }
};

Und die Verwendung geht folgendermaßen. Das ist ganz einfach. Nicht wahr?

void solve() {
    int n;
    cin >> n;
    DisjointSet S(n);  // Initializing with maximum Size
    S.union_set(1, 2);
    S.union_set(3, 7);
    int parent = S.find_set(1);  // root of 1
}