testDSF.cpp
Go to the documentation of this file.
1 /* ----------------------------------------------------------------------------
2 
3  * GTSAM Copyright 2010, Georgia Tech Research Corporation,
4  * Atlanta, Georgia 30332-0415
5  * All Rights Reserved
6  * Authors: Frank Dellaert, et al. (see THANKS for the full author list)
7 
8  * See LICENSE for the license information
9 
10  * -------------------------------------------------------------------------- */
11 
19 #include <gtsam_unstable/base/DSF.h>
20 
21 #include <CppUnitLite/TestHarness.h>
22 
23 #include <iostream>
24 
25 using namespace std;
26 using namespace gtsam;
27 
28 /* ************************************************************************* */
29 TEST(DSF, makeSet) {
30  DSFInt dsf;
31  dsf = dsf.makeSet(5);
32  LONGS_EQUAL(1, dsf.size());
33 }
34 
35 /* ************************************************************************* */
36 TEST(DSF, findSet) {
37  DSFInt dsf;
38  dsf = dsf.makeSet(5);
39  dsf = dsf.makeSet(6);
40  dsf = dsf.makeSet(7);
41  EXPECT(dsf.findSet(5) != dsf.findSet(7));
42 }
43 
44 /* ************************************************************************* */
45 TEST(DSF, makeUnion) {
46  DSFInt dsf;
47  dsf = dsf.makeSet(5);
48  dsf = dsf.makeSet(6);
49  dsf = dsf.makeSet(7);
50  dsf = dsf.makeUnion(5,7);
51  EXPECT(dsf.findSet(5) == dsf.findSet(7));
52 }
53 
54 /* ************************************************************************* */
55 TEST(DSF, makeUnion2) {
56  DSFInt dsf;
57  dsf = dsf.makeSet(5);
58  dsf = dsf.makeSet(6);
59  dsf = dsf.makeSet(7);
60  dsf = dsf.makeUnion(7,5);
61  EXPECT(dsf.findSet(5) == dsf.findSet(7));
62 }
63 
64 /* ************************************************************************* */
65 TEST(DSF, makeUnion3) {
66  DSFInt dsf;
67  dsf = dsf.makeSet(5);
68  dsf = dsf.makeSet(6);
69  dsf = dsf.makeSet(7);
70  dsf = dsf.makeUnion(5,6);
71  dsf = dsf.makeUnion(6,7);
72  EXPECT(dsf.findSet(5) == dsf.findSet(7));
73 }
74 
75 /* ************************************************************************* */
76 TEST(DSF, makePair) {
77  DSFInt dsf;
78  dsf = dsf.makePair(0, 1);
79  dsf = dsf.makePair(1, 2);
80  dsf = dsf.makePair(3, 2);
81  EXPECT(dsf.findSet(0) == dsf.findSet(3));
82 }
83 
84 /* ************************************************************************* */
85 TEST(DSF, makeList) {
86  DSFInt dsf;
87  list<int> keys{5, 6, 7};
88  dsf = dsf.makeList(keys);
89  EXPECT(dsf.findSet(5) == dsf.findSet(7));
90 }
91 
92 /* ************************************************************************* */
93 TEST(DSF, numSets) {
94  DSFInt dsf;
95  dsf = dsf.makeSet(5);
96  dsf = dsf.makeSet(6);
97  dsf = dsf.makeSet(7);
98  dsf = dsf.makeUnion(5,6);
99  LONGS_EQUAL(2, dsf.numSets());
100 }
101 
102 /* ************************************************************************* */
103 TEST(DSF, sets) {
104  DSFInt dsf;
105  dsf = dsf.makeSet(5);
106  dsf = dsf.makeSet(6);
107  dsf = dsf.makeUnion(5,6);
108  map<int, set<int> > sets = dsf.sets();
109  LONGS_EQUAL(1, sets.size());
110 
111  set<int> expected{5, 6};
112  EXPECT(expected == sets[dsf.findSet(5)]);
113 }
114 
115 /* ************************************************************************* */
116 TEST(DSF, sets2) {
117  DSFInt dsf;
118  dsf = dsf.makeSet(5);
119  dsf = dsf.makeSet(6);
120  dsf = dsf.makeSet(7);
121  dsf = dsf.makeUnion(5,6);
122  dsf = dsf.makeUnion(6,7);
123  map<int, set<int> > sets = dsf.sets();
124  LONGS_EQUAL(1, sets.size());
125 
126  set<int> expected{5, 6, 7};
127  EXPECT(expected == sets[dsf.findSet(5)]);
128 }
129 
130 /* ************************************************************************* */
131 TEST(DSF, sets3) {
132  DSFInt dsf;
133  dsf = dsf.makeSet(5);
134  dsf = dsf.makeSet(6);
135  dsf = dsf.makeSet(7);
136  dsf = dsf.makeUnion(5,6);
137  map<int, set<int> > sets = dsf.sets();
138  LONGS_EQUAL(2, sets.size());
139 
140  set<int> expected{5, 6};
141  EXPECT(expected == sets[dsf.findSet(5)]);
142 }
143 
144 /* ************************************************************************* */
145 TEST(DSF, partition) {
146  DSFInt dsf;
147  dsf = dsf.makeSet(5);
148  dsf = dsf.makeSet(6);
149  dsf = dsf.makeUnion(5,6);
150 
151  list<int> keys{5};
152  map<int, set<int> > partitions = dsf.partition(keys);
153  LONGS_EQUAL(1, partitions.size());
154 
155  set<int> expected{5};
156  EXPECT(expected == partitions[dsf.findSet(5)]);
157 }
158 
159 /* ************************************************************************* */
160 TEST(DSF, partition2) {
161  DSFInt dsf;
162  dsf = dsf.makeSet(5);
163  dsf = dsf.makeSet(6);
164  dsf = dsf.makeSet(7);
165  dsf = dsf.makeUnion(5,6);
166 
167  list<int> keys{7};
168  map<int, set<int> > partitions = dsf.partition(keys);
169  LONGS_EQUAL(1, partitions.size());
170 
171  set<int> expected{7};
172  EXPECT(expected == partitions[dsf.findSet(7)]);
173 }
174 
175 /* ************************************************************************* */
176 TEST(DSF, partition3) {
177  DSFInt dsf;
178  dsf = dsf.makeSet(5);
179  dsf = dsf.makeSet(6);
180  dsf = dsf.makeSet(7);
181  dsf = dsf.makeUnion(5,6);
182 
183  list<int> keys{5, 7};
184  map<int, set<int> > partitions = dsf.partition(keys);
185  LONGS_EQUAL(2, partitions.size());
186 
187  set<int> expected{5};
188  EXPECT(expected == partitions[dsf.findSet(5)]);
189 }
190 
191 /* ************************************************************************* */
192 TEST(DSF, set) {
193  DSFInt dsf;
194  dsf = dsf.makeSet(5);
195  dsf = dsf.makeSet(6);
196  dsf = dsf.makeSet(7);
197  dsf = dsf.makeUnion(5,6);
198  set<int> set = dsf.set(5);
199  LONGS_EQUAL(2, set.size());
200 
201  std::set<int> expected{5, 6};
202  EXPECT(expected == set);
203 }
204 
205 /* ************************************************************************* */
206 TEST(DSF, set2) {
207  DSFInt dsf;
208  dsf = dsf.makeSet(5);
209  dsf = dsf.makeSet(6);
210  dsf = dsf.makeSet(7);
211  dsf = dsf.makeUnion(5,6);
212  dsf = dsf.makeUnion(6,7);
213  set<int> set = dsf.set(5);
214  LONGS_EQUAL(3, set.size());
215 
216  std::set<int> expected{5, 6, 7};
217  EXPECT(expected == set);
218 }
219 
220 /* ************************************************************************* */
221 int func(const int& a) { return a + 10; }
222 TEST(DSF, map) {
223  DSFInt dsf;
224  dsf = dsf.makeSet(5);
225  dsf = dsf.makeSet(6);
226  dsf = dsf.makeSet(7);
227  dsf = dsf.makeUnion(5,6);
228 
229  DSFInt actual = dsf.map(&func);
230  DSFInt expected;
231  expected = expected.makeSet(15);
232  expected = expected.makeSet(16);
233  expected = expected.makeSet(17);
234  expected = expected.makeUnion(15,16);
235  EXPECT(actual == expected);
236 }
237 
238 /* ************************************************************************* */
239 TEST(DSF, flatten) {
240  DSFInt dsf;
241  dsf = dsf.makePair(1, 2);
242  dsf = dsf.makePair(2, 3);
243  dsf = dsf.makePair(5, 6);
244  dsf = dsf.makePair(6, 7);
245  dsf = dsf.makeUnion(2, 6);
246 
247  DSFInt actual = dsf.flatten();
248  DSFInt expected;
249  expected = expected.makePair(1, 2);
250  expected = expected.makePair(1, 3);
251  expected = expected.makePair(1, 5);
252  expected = expected.makePair(1, 6);
253  expected = expected.makePair(1, 7);
254  EXPECT(actual == expected);
255 }
256 
257 /* ************************************************************************* */
258 TEST(DSF, flatten2) {
259  static string x1("x1"), x2("x2"), x3("x3"), x4("x4");
260  list<string> keys{x1, x2, x3, x4};
261  DSF<string> dsf(keys);
262  dsf = dsf.makeUnion(x1,x2);
263  dsf = dsf.makeUnion(x3,x4);
264  dsf = dsf.makeUnion(x1,x3);
265 
266  EXPECT(dsf != dsf.flatten());
267 
268  DSF<string> expected2;
269  expected2 = expected2.makePair(x1, x2);
270  expected2 = expected2.makePair(x1, x3);
271  expected2 = expected2.makePair(x1, x4);
272  EXPECT(expected2 == dsf.flatten());
273 }
274 
275 /* ************************************************************************* */
276 TEST(DSF, mergePairwiseMatches) {
277 
278  // Create some measurements with image index and feature index
279  typedef pair<size_t,size_t> Measurement;
280  Measurement m11(1,1),m12(1,2),m14(1,4); // in image 1
281  Measurement m22(2,2),m23(2,3),m25(2,5),m26(2,6); // in image 2
282 
283  // Add them all
284  list<Measurement> measurements{m11, m12, m14, m22, m23, m25, m26};
285 
286  // Create some "matches"
287  typedef pair<Measurement,Measurement> Match;
288  list<Match> matches{Match(m11, m22), Match(m12, m23), Match(m14, m25),
289  Match(m14, m26)};
290 
291  // Merge matches
292  DSF<Measurement> dsf(measurements);
293  for(const Match& m: matches)
294  dsf.makeUnionInPlace(m.first,m.second);
295 
296  // Check that sets are merged correctly
297  EXPECT(dsf.findSet(m11)==m11);
298  EXPECT(dsf.findSet(m12)==m12);
299  EXPECT(dsf.findSet(m14)==m14);
300  EXPECT(dsf.findSet(m22)==m11);
301  EXPECT(dsf.findSet(m23)==m12);
302  EXPECT(dsf.findSet(m25)==m14);
303  EXPECT(dsf.findSet(m26)==m14);
304 
305  // Check that we have three connected components
306  EXPECT_LONGS_EQUAL(3, dsf.numSets());
307 
308  set<Measurement> expected1{m11,m22};
309  set<Measurement> actual1 = dsf.set(m11);
310  EXPECT(expected1 == actual1);
311 
312  set<Measurement> expected2{m12,m23};
313  set<Measurement> actual2 = dsf.set(m12);
314  EXPECT(expected2 == actual2);
315 
316  set<Measurement> expected3{m14,m25,m26};
317  set<Measurement> actual3 = dsf.set(m14);
318  EXPECT(expected3 == actual3);
319 }
320 
321 /* ************************************************************************* */
322 int main() { TestResult tr; return TestRegistry::runAllTests(tr);}
323 /* ************************************************************************* */
324 
m
Matrix3f m
Definition: AngleAxis_mimic_euler.cpp:1
gtsam::DSF::flatten
DSF flatten() const
Definition: DSF.h:117
gtsam::DSF::partition
std::map< KEY, Set > partition(const std::list< KEY > &keys) const
Definition: DSF.h:155
TestRegistry::runAllTests
static int runAllTests(TestResult &result)
Definition: TestRegistry.cpp:27
gtsam::DSF::numSets
size_t numSets() const
Definition: DSF.h:133
cholesky::expected
Matrix expected
Definition: testMatrix.cpp:971
std
Definition: BFloat16.h:88
x2
Pose3 x2(Rot3::Ypr(0.0, 0.0, 0.0), l2)
gtsam::DSF::makeList
Self makeList(const std::list< KEY > &keys) const
Definition: DSF.h:109
size
Scalar Scalar int size
Definition: benchVecAdd.cpp:17
gtsam::DSF::makePair
Self makePair(const KEY &key1, const KEY &key2) const
Definition: DSF.h:104
gtsam::DSF::sets
std::map< KEY, Set > sets() const
Definition: DSF.h:147
gtsam::DSF::makeUnionInPlace
void makeUnionInPlace(const KEY &key1, const KEY &key2)
Definition: DSF.h:99
simulated2D::Measurement
GenericMeasurement< Point2, Point2 > Measurement
Definition: simulated2D.h:278
EXPECT
#define EXPECT(condition)
Definition: Test.h:150
gtsam::DSF::makeUnion
Self makeUnion(const KEY &key1, const KEY &key2) const
Definition: DSF.h:92
gtsam::DSF::makeSet
Self makeSet(const KEY &key) const
Definition: DSF.h:72
DSF.h
An implementation of Disjoint set forests (see CLR page 446 and up)
main
int main()
Definition: testDSF.cpp:322
TEST
TEST(DSF, makeSet)
Definition: testDSF.cpp:29
gtsam::DSF::findSet
KEY findSet(const KEY &key) const
Definition: DSF.h:86
x3
Pose3 x3(Rot3::Ypr(M_PI/4.0, 0.0, 0.0), l2)
LONGS_EQUAL
#define LONGS_EQUAL(expected, actual)
Definition: Test.h:134
gtsam
traits
Definition: chartTesting.h:28
gtsam::DSF::map
DSF map(std::function< KEY(const KEY &)> func) const
Definition: DSF.h:125
func
int func(const int &a)
Definition: testDSF.cpp:221
EXPECT_LONGS_EQUAL
#define EXPECT_LONGS_EQUAL(expected, actual)
Definition: Test.h:154
x1
Pose3 x1
Definition: testPose3.cpp:663
gtsam::DSF::set
Set set(const KEY &label) const
Definition: DSF.h:163
a
ArrayXXi a
Definition: Array_initializer_list_23_cxx11.cpp:1
keys
const KeyVector keys
Definition: testRegularImplicitSchurFactor.cpp:40
x4
static string x4("x4")
gtsam::DSF::size
size_t size() const
Definition: DSF.h:142
gtsam::DSF
Definition: DSF.h:39

gtsam
Author(s):
autogenerated on Tue Jul 4 2023 02:38:01