1/** \file
2 * \brief Tests for ogdf::DisjointSets<>.
3 *
4 * \author Mirko Wagner
5 *
6 * \par License:
7 * This file is part of the Open Graph Drawing Framework (OGDF).
8 *
9 * \par
10 * Copyright (C)<br>
11 * See README.md in the OGDF root directory for details.
12 *
13 * \par
14 * This program is free software; you can redistribute it and/or
15 * modify it under the terms of the GNU General Public License
16 * Version 2 or 3 as published by the Free Software Foundation;
17 * see the file LICENSE.txt included in the packaging of this file
18 * for details.
19 *
20 * \par
21 * This program is distributed in the hope that it will be useful,
22 * but WITHOUT ANY WARRANTY; without even the implied warranty of
23 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24 * GNU General Public License for more details.
25 *
26 * \par
27 * You should have received a copy of the GNU General Public
28 * License along with this program; if not, see
29 * http://www.gnu.org/copyleft/gpl.html
30 */
31
32#include <ogdf/basic/DisjointSets.h>
33#include <testing.h>
34
35template<typename DisjointSetsClass>
36static void registerTestSuite(const string typeName)
37{
38 describe(typeName,[&](){
39 std::unique_ptr<DisjointSetsClass> disjointSets;
40 int sets[42];
41
42 before_each([&](){
43 disjointSets.reset(new DisjointSetsClass());
44 for (auto &set : sets) {
45 set = disjointSets->makeSet();
46 }
47 });
48
49 it("assigns valid set id's", [&](){
50 for (int i : sets) {
51 AssertThat(i, IsGreaterThan(-1));
52 }
53 });
54
55 it("is initialized", [&](){
56 DisjointSetsClass emptydisjointSets;
57 AssertThat(emptydisjointSets.getNumberOfElements(), Equals(0));
58 AssertThat(emptydisjointSets.getNumberOfSets(), Equals(0));
59 });
60
61 it("can be filled", [&](){
62 AssertThat(disjointSets->getNumberOfElements(), Equals(42));
63 AssertThat(disjointSets->getNumberOfSets(), Equals(42));
64 });
65
66 it("unifies two disjoint sets and doesn't unify two joined sets", [&](){
67 AssertThat(disjointSets->quickUnion(sets[2], sets[1]), IsTrue());
68 AssertThat(disjointSets->quickUnion(sets[0], sets[2]), IsTrue());
69 AssertThat(disjointSets->quickUnion(sets[0], sets[1]), IsFalse());
70 });
71
72 it("returns the same id for every item of a unified superset", [&](){
73 AssertThat(disjointSets->getRepresentative(sets[13]), Equals(sets[13]));
74 AssertThat(disjointSets->getRepresentative(sets[13]), Equals(disjointSets->find(sets[13])));
75 disjointSets->quickUnion(sets[1], sets[2]);
76 disjointSets->quickUnion(sets[2], sets[3]);
77 disjointSets->quickUnion(sets[1], sets[4]);
78 AssertThat(disjointSets->getRepresentative(sets[1]), Equals(disjointSets->getRepresentative(sets[2])));
79 AssertThat(disjointSets->getRepresentative(sets[1]), Equals(disjointSets->getRepresentative(sets[3])));
80 AssertThat(disjointSets->getRepresentative(sets[1]), Equals(disjointSets->getRepresentative(sets[4])));
81 AssertThat(disjointSets->getRepresentative(sets[1]), Equals(disjointSets->find(sets[1])));
82 AssertThat(disjointSets->getRepresentative(sets[1]), Equals(disjointSets->find(sets[2])));
83 AssertThat(disjointSets->getRepresentative(sets[1]), Equals(disjointSets->find(sets[3])));
84 AssertThat(disjointSets->getRepresentative(sets[1]), Equals(disjointSets->find(sets[4])));
85 AssertThat(sets[5], !Equals(disjointSets->find(sets[4])));
86 AssertThat(sets[5], !Equals(disjointSets->getRepresentative(sets[4])));
87 });
88
89 it("returns the same id for every item of a linked superset", [&](){
90 AssertThat(disjointSets->getRepresentative(13), Equals(13) && Equals(disjointSets->find(13)));
91 disjointSets->link(sets[1], sets[2]);
92 disjointSets->link(disjointSets->find(sets[2]), sets[3]);
93 disjointSets->link(disjointSets->find(sets[1]), sets[4]);
94 AssertThat(disjointSets->getRepresentative(sets[1]), Equals(disjointSets->getRepresentative(sets[2])));
95 AssertThat(disjointSets->getRepresentative(sets[1]), Equals(disjointSets->getRepresentative(sets[3])));
96 AssertThat(disjointSets->getRepresentative(sets[1]), Equals(disjointSets->getRepresentative(sets[4])));
97 AssertThat(disjointSets->getRepresentative(sets[1]), Equals(disjointSets->find(sets[1])));
98 AssertThat(disjointSets->getRepresentative(sets[1]), Equals(disjointSets->find(sets[2])));
99 AssertThat(disjointSets->getRepresentative(sets[1]), Equals(disjointSets->find(sets[3])));
100 AssertThat(disjointSets->getRepresentative(sets[1]), Equals(disjointSets->find(sets[4])));
101 AssertThat(sets[5], !Equals(disjointSets->find(sets[4])));
102 AssertThat(sets[5], !Equals(disjointSets->getRepresentative(sets[4])));
103 });
104
105 it("tracks the number of elements", [&](){
106 AssertThat(disjointSets->getNumberOfElements(), Equals(42));
107 disjointSets->quickUnion(sets[1], sets[2]);
108 disjointSets->quickUnion(sets[1], sets[2]);
109 disjointSets->link(disjointSets->getRepresentative(sets[1]), disjointSets->find(sets[3]));
110 disjointSets->link(disjointSets->find(sets[2]), disjointSets->getRepresentative(sets[3]));
111 AssertThat(disjointSets->getNumberOfElements(), Equals(42));
112 disjointSets->makeSet();
113 AssertThat(disjointSets->getNumberOfElements(), Equals(43));
114 });
115
116 it("tracks the number of sets when using link", [&](){
117 int successfullLinkCounter = 0;
118 successfullLinkCounter += disjointSets->link(sets[1], sets[2]) != -1;
119 successfullLinkCounter += disjointSets->link(disjointSets->find(sets[2]), sets[3]) != -1;
120 successfullLinkCounter += disjointSets->link(disjointSets->find(sets[1]), sets[4]) != -1;
121 successfullLinkCounter += disjointSets->link(disjointSets->find(sets[4]), disjointSets->find(sets[3])) != -1;
122 for (int i = 0; i < 42; i++) {
123 successfullLinkCounter += disjointSets->link(disjointSets->find(sets[4]), disjointSets->find(sets[3])) != -1;
124 }
125 AssertThat(disjointSets->getNumberOfSets(), Equals(42 - successfullLinkCounter));
126 AssertThat(successfullLinkCounter, IsLessThan(42));
127 });
128
129 it("tracks the number of sets when using quickUnion", [&](){
130 int successfullUnionCounter = 0;
131 successfullUnionCounter += disjointSets->quickUnion(sets[1], sets[2]);
132 successfullUnionCounter += disjointSets->quickUnion(sets[2], sets[3]);
133 successfullUnionCounter += disjointSets->quickUnion(sets[1], sets[4]);
134 for (int i = 0; i < 42; i++) {
135 successfullUnionCounter += disjointSets->quickUnion(sets[4], sets[3]);
136 }
137
138 AssertThat(disjointSets->getNumberOfSets(), Equals(42-successfullUnionCounter));
139 });
140
141#ifdef OGDF_USE_ASSERT_EXCEPTIONS
142 it("throws an exception, if the user tries to link two non-maximal disjoint sets", [&](){
143 disjointSets->link(sets[3], sets[4]);
144 int notMaximalSet = (disjointSets->getRepresentative(sets[3]) == sets[4] ? sets[3] : sets[4]);
145 AssertThrows(AssertionFailed, disjointSets->link(notMaximalSet, sets[5]));
146 });
147
148 it("detects invalid set ids", [&](){
149 AssertThrows(AssertionFailed, disjointSets->find(-1));
150 AssertThrows(AssertionFailed, disjointSets->getRepresentative(-1));
151 int notASetId = 0;
152 int max = 0;
153 for (int i : sets) {
154 max = (i > max ? i : max);
155 }
156 notASetId = max+1;
157 AssertThrows(AssertionFailed, disjointSets->find(notASetId));
158 AssertThrows(AssertionFailed, disjointSets->getRepresentative(notASetId));
159 });
160#endif
161 });
162}
163
164go_bandit([](){
165describe("Disjoint Sets", [](){
166 registerTestSuite<DisjointSets<>>("Default");
167 registerTestSuite<DisjointSets<LinkOptions::Index,
168 CompressionOptions::PathCompression,
169 InterleavingOptions::Rem>>("Linking by Index, Path Compression, Rem's Algorithm");
170 registerTestSuite<DisjointSets<LinkOptions::Rank,
171 CompressionOptions::PathSplitting,
172 InterleavingOptions::Tarjan>>("Linking by Rank, Path Splitting, Tarjan and van Leeuwen's Algorithm");
173 registerTestSuite<DisjointSets<LinkOptions::Naive,
174 CompressionOptions::Type1Reversal,
175 InterleavingOptions::Type0Reversal>>("No Linking, Reversal Type 1, Interleaved Reversal Type 0");
176 registerTestSuite<DisjointSets<LinkOptions::Index,
177 CompressionOptions::PathHalving,
178 InterleavingOptions::SplittingCompression>>("Linking by Index, Path Halving, Interleaved Path Splitting Path Compression");
179 registerTestSuite<DisjointSets<LinkOptions::Size,
180 CompressionOptions::Collapsing,
181 InterleavingOptions::Disabled>>("Linking by Size, Collapsing, No Interleaving");
182 registerTestSuite<DisjointSets<LinkOptions::Rank,
183 CompressionOptions::Disabled,
184 InterleavingOptions::Disabled>>("No Linking, No Compression, No Interleaving");
185});
186});
187