Ich brauche boost :: disjoint_sets, aber the documentation ist mir unklar. Kann jemand bitte erklären, was jeder Template-Parameter bedeutet, und vielleicht einen kleinen Beispielcode zum Erstellen eines disjoint_sets geben?Verständnis boost :: disjoint_sets
Gemäß der Anfrage verwende ich disjoint_sets zu implementieren Tarjan's off-line least common ancestors algorithm, d. H. - der Werttyp sollte vertex_descriptor sein.
Was ich aus der Dokumentation verstehen:
disjunkte Notwendigkeit, einen Rang und einen Elternteil zu assoziieren (im Waldbaum) zu jedem Elemente. Da Sie vielleicht mit jeder Art von Daten arbeiten möchten, möchten Sie beispielsweise nicht immer eine Map für das Elternobjekt verwenden: mit Integer ist ein Array ausreichend. Du brauchst auch einen Rang-Gegner für jedes Element (den Rang, der für den Union-Fund benötigt wird).
Sie benötigen zwei „Eigenschaften“:
Auf dem Beispiel:
std::vector<int> rank (100);
std::vector<int> parent (100);
boost::disjoint_sets<int*,int*> ds(&rank[0], &parent[0]);
Arrays sind verwendet &rank[0], &parent[0] zu dem Typ in der Vorlage ist int*
Für ein komplexeres Beispiel (mit Karten) können Sie Ugo's Antwort betrachten.
Sie geben nur dem Algorithmus zwei Strukturen, um die Daten (Rang/Eltern) zu speichern, die er benötigt.
Gibt es immer noch eine einfachere Lösung als Karte, wenn Sie die maximale Anzahl der Elemente nicht kennen? –
disjoint_sets<Rank, Parent, FindCompress>
find_with_full_path_compression Siehe here (Standard sollte sein, was Sie brauchen).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);
}
Beachten Sie, dass „Die Boost Immobilien Karte Bibliothek ein paar Adapter enthält, die häufig Daten-Strukturen umwandeln, die eine Abbildungsoperation, wie gebautet Arrays (Zeiger), Iteratoren implementieren, und std :: map, um die Eigenschaft map interface "
zu haben. Diese Liste dieser Adapter (wie boost :: associative_property_map) kann here gefunden werden.
Wirklich gute Erklärung. Ich werde meine Antwort löschen. –
@Loic Eigentlich ist deine Antwort das Ausfüllen dieses. Da kann ein effizienterer Code verwendet werden, wenn Element == int (Vektoren verwenden). – log0
Ok. Ich werde dann das zweite Beispiel löschen. –
Für diejenigen von euch, die den Overhead von std::map nicht leisten können (oder kann es nicht verwenden, weil Sie nicht Standardkonstruktor in der Klasse), aber Daten, die ist nicht so einfach, wie int, schrieb ich a guide zu einer Lösung mit std::vector, die Art von optimal ist, wenn Sie die Gesamtzahl der Elemente im Voraus kennen.
Das Handbuch enthält eine fully-working sample code, die Sie herunterladen und selbst testen können.
Die dort erwähnte Lösung geht davon aus, dass Sie die Kontrolle über den Klassencode haben, so dass Sie insbesondere einige Attribute hinzufügen können. Wenn dies noch nicht möglich ist, können Sie immer einen Wrapper um es hinzuzufügen:
class Wrapper {
UntouchableClass const& mInstance;
size_t dsID;
size_t dsRank;
size_t dsParent;
}
Außerdem, wenn Sie die Anzahl der Elemente kennen, klein zu sein, gibt es keine Notwendigkeit für size_t, in welchem Fall Sie einige Vorlage hinzufügen für den UnsignedInt Typ und entscheide dich in der Laufzeit, ihn mit uint8_t, uint16_t, uint32_t oder uint64_t zu instanziieren, die du sonst mit <cstdint> in C++ 11 oder mit boost::cstdint erhalten kannst.
template <typename UnsignedInt>
class Wrapper {
UntouchableClass const& mInstance;
UnsignedInt dsID;
UnsignedInt dsRank;
UnsignedInt dsParent;
}
Hier ist der Link wieder, falls Sie es verpasst haben: http://janoma.cl/post/using-disjoint-sets-with-a-vector/
Dies könnte besser funktionieren, wenn Sie ein Beispiel zur Verfügung gestellt, was Sie erreichen wollen. –
Wow, sieht aus wie viele Leute neugierig sind und nicht viele haben eine Idee, wie man es überhaupt anfangen kann. – wheaties
gab es mindestens ein einfaches Beispiel für die Verwendung von SO: http://StackOverflow.com/Questions/3738537/implementing-Equivalence-relations-in-C-using-boostdisjoint-sets – Cubbi