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
12/**
13 * @file testDSF.cpp
14 * @date Mar 26, 2010
15 * @author nikai
16 * @brief unit tests for DSF
17 */
18
19#include <gtsam_unstable/base/DSF.h>
20
21#include <CppUnitLite/TestHarness.h>
22
23#include <iostream>
24
25using namespace std;
26using namespace gtsam;
27
28/* ************************************************************************* */
29TEST(DSF, makeSet) {
30 DSFInt dsf;
31 dsf = dsf.makeSet(key: 5);
32 LONGS_EQUAL(1, dsf.size());
33}
34
35/* ************************************************************************* */
36TEST(DSF, findSet) {
37 DSFInt dsf;
38 dsf = dsf.makeSet(key: 5);
39 dsf = dsf.makeSet(key: 6);
40 dsf = dsf.makeSet(key: 7);
41 EXPECT(dsf.findSet(5) != dsf.findSet(7));
42}
43
44/* ************************************************************************* */
45TEST(DSF, makeUnion) {
46 DSFInt dsf;
47 dsf = dsf.makeSet(key: 5);
48 dsf = dsf.makeSet(key: 6);
49 dsf = dsf.makeSet(key: 7);
50 dsf = dsf.makeUnion(key1: 5,key2: 7);
51 EXPECT(dsf.findSet(5) == dsf.findSet(7));
52}
53
54/* ************************************************************************* */
55TEST(DSF, makeUnion2) {
56 DSFInt dsf;
57 dsf = dsf.makeSet(key: 5);
58 dsf = dsf.makeSet(key: 6);
59 dsf = dsf.makeSet(key: 7);
60 dsf = dsf.makeUnion(key1: 7,key2: 5);
61 EXPECT(dsf.findSet(5) == dsf.findSet(7));
62}
63
64/* ************************************************************************* */
65TEST(DSF, makeUnion3) {
66 DSFInt dsf;
67 dsf = dsf.makeSet(key: 5);
68 dsf = dsf.makeSet(key: 6);
69 dsf = dsf.makeSet(key: 7);
70 dsf = dsf.makeUnion(key1: 5,key2: 6);
71 dsf = dsf.makeUnion(key1: 6,key2: 7);
72 EXPECT(dsf.findSet(5) == dsf.findSet(7));
73}
74
75/* ************************************************************************* */
76TEST(DSF, makePair) {
77 DSFInt dsf;
78 dsf = dsf.makePair(key1: 0, key2: 1);
79 dsf = dsf.makePair(key1: 1, key2: 2);
80 dsf = dsf.makePair(key1: 3, key2: 2);
81 EXPECT(dsf.findSet(0) == dsf.findSet(3));
82}
83
84/* ************************************************************************* */
85TEST(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/* ************************************************************************* */
93TEST(DSF, numSets) {
94 DSFInt dsf;
95 dsf = dsf.makeSet(key: 5);
96 dsf = dsf.makeSet(key: 6);
97 dsf = dsf.makeSet(key: 7);
98 dsf = dsf.makeUnion(key1: 5,key2: 6);
99 LONGS_EQUAL(2, dsf.numSets());
100}
101
102/* ************************************************************************* */
103TEST(DSF, sets) {
104 DSFInt dsf;
105 dsf = dsf.makeSet(key: 5);
106 dsf = dsf.makeSet(key: 6);
107 dsf = dsf.makeUnion(key1: 5,key2: 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/* ************************************************************************* */
116TEST(DSF, sets2) {
117 DSFInt dsf;
118 dsf = dsf.makeSet(key: 5);
119 dsf = dsf.makeSet(key: 6);
120 dsf = dsf.makeSet(key: 7);
121 dsf = dsf.makeUnion(key1: 5,key2: 6);
122 dsf = dsf.makeUnion(key1: 6,key2: 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/* ************************************************************************* */
131TEST(DSF, sets3) {
132 DSFInt dsf;
133 dsf = dsf.makeSet(key: 5);
134 dsf = dsf.makeSet(key: 6);
135 dsf = dsf.makeSet(key: 7);
136 dsf = dsf.makeUnion(key1: 5,key2: 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/* ************************************************************************* */
145TEST(DSF, partition) {
146 DSFInt dsf;
147 dsf = dsf.makeSet(key: 5);
148 dsf = dsf.makeSet(key: 6);
149 dsf = dsf.makeUnion(key1: 5,key2: 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/* ************************************************************************* */
160TEST(DSF, partition2) {
161 DSFInt dsf;
162 dsf = dsf.makeSet(key: 5);
163 dsf = dsf.makeSet(key: 6);
164 dsf = dsf.makeSet(key: 7);
165 dsf = dsf.makeUnion(key1: 5,key2: 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/* ************************************************************************* */
176TEST(DSF, partition3) {
177 DSFInt dsf;
178 dsf = dsf.makeSet(key: 5);
179 dsf = dsf.makeSet(key: 6);
180 dsf = dsf.makeSet(key: 7);
181 dsf = dsf.makeUnion(key1: 5,key2: 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/* ************************************************************************* */
192TEST(DSF, set) {
193 DSFInt dsf;
194 dsf = dsf.makeSet(key: 5);
195 dsf = dsf.makeSet(key: 6);
196 dsf = dsf.makeSet(key: 7);
197 dsf = dsf.makeUnion(key1: 5,key2: 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/* ************************************************************************* */
206TEST(DSF, set2) {
207 DSFInt dsf;
208 dsf = dsf.makeSet(key: 5);
209 dsf = dsf.makeSet(key: 6);
210 dsf = dsf.makeSet(key: 7);
211 dsf = dsf.makeUnion(key1: 5,key2: 6);
212 dsf = dsf.makeUnion(key1: 6,key2: 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/* ************************************************************************* */
221int func(const int& a) { return a + 10; }
222TEST(DSF, map) {
223 DSFInt dsf;
224 dsf = dsf.makeSet(key: 5);
225 dsf = dsf.makeSet(key: 6);
226 dsf = dsf.makeSet(key: 7);
227 dsf = dsf.makeUnion(key1: 5,key2: 6);
228
229 DSFInt actual = dsf.map(func: &func);
230 DSFInt expected;
231 expected = expected.makeSet(key: 15);
232 expected = expected.makeSet(key: 16);
233 expected = expected.makeSet(key: 17);
234 expected = expected.makeUnion(key1: 15,key2: 16);
235 EXPECT(actual == expected);
236}
237
238/* ************************************************************************* */
239TEST(DSF, flatten) {
240 DSFInt dsf;
241 dsf = dsf.makePair(key1: 1, key2: 2);
242 dsf = dsf.makePair(key1: 2, key2: 3);
243 dsf = dsf.makePair(key1: 5, key2: 6);
244 dsf = dsf.makePair(key1: 6, key2: 7);
245 dsf = dsf.makeUnion(key1: 2, key2: 6);
246
247 DSFInt actual = dsf.flatten();
248 DSFInt expected;
249 expected = expected.makePair(key1: 1, key2: 2);
250 expected = expected.makePair(key1: 1, key2: 3);
251 expected = expected.makePair(key1: 1, key2: 5);
252 expected = expected.makePair(key1: 1, key2: 6);
253 expected = expected.makePair(key1: 1, key2: 7);
254 EXPECT(actual == expected);
255}
256
257/* ************************************************************************* */
258TEST(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(key1: x1,key2: x2);
263 dsf = dsf.makeUnion(key1: x3,key2: x4);
264 dsf = dsf.makeUnion(key1: x1,key2: x3);
265
266 EXPECT(dsf != dsf.flatten());
267
268 DSF<string> expected2;
269 expected2 = expected2.makePair(key1: x1, key2: x2);
270 expected2 = expected2.makePair(key1: x1, key2: x3);
271 expected2 = expected2.makePair(key1: x1, key2: x4);
272 EXPECT(expected2 == dsf.flatten());
273}
274
275/* ************************************************************************* */
276TEST(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(key1: m.first,key2: 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/* ************************************************************************* */
322int main() { TestResult tr; return TestRegistry::runAllTests(result&: tr);}
323/* ************************************************************************* */
324
325