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

gtsam
Author(s):
autogenerated on Sat May 8 2021 02:46:26