testDSFVector.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/base/DSFVector.h>
20 
22 
23 
24 #include <iostream>
25 #include <set>
26 #include <list>
27 #include <utility>
28 
29 using std::pair;
30 using std::map;
31 using std::vector;
32 using namespace gtsam;
33 
34 /* ************************************************************************* */
35 TEST(DSFBase, find) {
36  DSFBase dsf(3);
37  EXPECT(dsf.find(0) != dsf.find(2));
38 }
39 
40 /* ************************************************************************* */
41 TEST(DSFBase, merge) {
42  DSFBase dsf(3);
43  dsf.merge(0,2);
44  EXPECT(dsf.find(0) == dsf.find(2));
45 }
46 
47 /* ************************************************************************* */
48 TEST(DSFBase, makeUnion2) {
49  DSFBase dsf(3);
50  dsf.merge(2,0);
51  EXPECT(dsf.find(0) == dsf.find(2));
52 }
53 
54 /* ************************************************************************* */
55 TEST(DSFBase, makeUnion3) {
56  DSFBase dsf(3);
57  dsf.merge(0,1);
58  dsf.merge(1,2);
59  EXPECT(dsf.find(0) == dsf.find(2));
60 }
61 
62 /* ************************************************************************* */
63 TEST(DSFBase, mergePairwiseMatches) {
64 
65  // Create some "matches"
66  typedef pair<size_t,size_t> Match;
67  const vector<Match> matches{Match(1, 2), Match(2, 3), Match(4, 5),
68  Match(4, 6)};
69 
70  // Merge matches
71  DSFBase dsf(7); // We allow for keys 0..6
72  for(const Match& m: matches)
73  dsf.merge(m.first,m.second);
74 
75  // Each point is now associated with a set, represented by one of its members
76  size_t rep1 = 1, rep2 = 4;
77  EXPECT_LONGS_EQUAL(rep1,dsf.find(1));
78  EXPECT_LONGS_EQUAL(rep1,dsf.find(2));
79  EXPECT_LONGS_EQUAL(rep1,dsf.find(3));
80  EXPECT_LONGS_EQUAL(rep2,dsf.find(4));
81  EXPECT_LONGS_EQUAL(rep2,dsf.find(5));
82  EXPECT_LONGS_EQUAL(rep2,dsf.find(6));
83 }
84 
85 /* ************************************************************************* */
86 TEST(DSFVector, merge2) {
87  std::shared_ptr<DSFBase::V> v = std::make_shared<DSFBase::V>(5);
88  const std::vector<size_t> keys {1, 3};
89  DSFVector dsf(v, keys);
90  dsf.merge(1,3);
91  EXPECT(dsf.find(1) == dsf.find(3));
92 }
93 
94 /* ************************************************************************* */
95 TEST(DSFVector, sets) {
96  DSFVector dsf(2);
97  dsf.merge(0,1);
98  map<size_t, std::set<size_t> > sets = dsf.sets();
99  LONGS_EQUAL(1, sets.size());
100 
101  const std::set<size_t> expected{0, 1};
102  EXPECT(expected == sets[dsf.find(0)]);
103 }
104 
105 /* ************************************************************************* */
106 TEST(DSFVector, arrays) {
107  DSFVector dsf(2);
108  dsf.merge(0,1);
109  map<size_t, vector<size_t> > arrays = dsf.arrays();
110  LONGS_EQUAL(1, arrays.size());
111 
112  const vector<size_t> expected{0, 1};
113  EXPECT(expected == arrays[dsf.find(0)]);
114 }
115 
116 /* ************************************************************************* */
117 TEST(DSFVector, sets2) {
118  DSFVector dsf(3);
119  dsf.merge(0,1);
120  dsf.merge(1,2);
121  map<size_t, std::set<size_t> > sets = dsf.sets();
122  LONGS_EQUAL(1, sets.size());
123 
124  const std::set<size_t> expected{0, 1, 2};
125  EXPECT(expected == sets[dsf.find(0)]);
126 }
127 
128 /* ************************************************************************* */
129 TEST(DSFVector, arrays2) {
130  DSFVector dsf(3);
131  dsf.merge(0,1);
132  dsf.merge(1,2);
133  map<size_t, vector<size_t> > arrays = dsf.arrays();
134  LONGS_EQUAL(1, arrays.size());
135 
136  const vector<size_t> expected{0, 1, 2};
137  EXPECT(expected == arrays[dsf.find(0)]);
138 }
139 
140 /* ************************************************************************* */
141 TEST(DSFVector, sets3) {
142  DSFVector dsf(3);
143  dsf.merge(0,1);
144  map<size_t, std::set<size_t> > sets = dsf.sets();
145  LONGS_EQUAL(2, sets.size());
146 
147  const std::set<size_t> expected{0, 1};
148  EXPECT(expected == sets[dsf.find(0)]);
149 }
150 
151 /* ************************************************************************* */
152 TEST(DSFVector, arrays3) {
153  DSFVector dsf(3);
154  dsf.merge(0,1);
155  map<size_t, vector<size_t> > arrays = dsf.arrays();
156  LONGS_EQUAL(2, arrays.size());
157 
158  const vector<size_t> expected{0, 1};
159  EXPECT(expected == arrays[dsf.find(0)]);
160 }
161 
162 /* ************************************************************************* */
164  DSFVector dsf(3);
165  dsf.merge(0,1);
166  std::set<size_t> set = dsf.set(0);
167  LONGS_EQUAL(2, set.size());
168 
169  const std::set<size_t> expected{0, 1};
170  EXPECT(expected == set);
171 }
172 
173 /* ************************************************************************* */
174 TEST(DSFVector, set2) {
175  DSFVector dsf(3);
176  dsf.merge(0,1);
177  dsf.merge(1,2);
178  std::set<size_t> set = dsf.set(0);
179  LONGS_EQUAL(3, set.size());
180 
181  const std::set<size_t> expected{0, 1, 2};
182  EXPECT(expected == set);
183 }
184 
185 /* ************************************************************************* */
186 TEST(DSFVector, isSingleton) {
187  DSFVector dsf(3);
188  dsf.merge(0,1);
189  EXPECT(!dsf.isSingleton(0));
190  EXPECT(!dsf.isSingleton(1));
191  EXPECT( dsf.isSingleton(2));
192 }
193 
194 /* ************************************************************************* */
195 TEST(DSFVector, mergePairwiseMatches) {
196 
197  // Create some measurements
198  const vector<size_t> keys{1, 2, 3, 4, 5, 6};
199 
200  // Create some "matches"
201  typedef pair<size_t,size_t> Match;
202  const vector<Match> matches{Match(1, 2), Match(2, 3), Match(4, 5),
203  Match(4, 6)};
204 
205  // Merge matches
206  DSFVector dsf(keys);
207  for(const Match& m: matches)
208  dsf.merge(m.first,m.second);
209 
210  // Check that we have two connected components, 1,2,3 and 4,5,6
211  map<size_t, std::set<size_t> > sets = dsf.sets();
212  LONGS_EQUAL(2, sets.size());
213  const std::set<size_t> expected1{1, 2, 3};
214  std::set<size_t> actual1 = sets[dsf.find(2)];
215  EXPECT(expected1 == actual1);
216  const std::set<size_t> expected2{4, 5, 6};
217  std::set<size_t> actual2 = sets[dsf.find(5)];
218  EXPECT(expected2 == actual2);
219 }
220 
221 /* ************************************************************************* */
222 int main() { TestResult tr; return TestRegistry::runAllTests(tr);}
223 /* ************************************************************************* */
224 
Matrix3f m
static int runAllTests(TestResult &result)
Matrix expected
Definition: testMatrix.cpp:971
size_t find(size_t key) const
Find the label of the set in which {key} lives.
Definition: DSFVector.cpp:44
int main()
A faster implementation for DSF, which uses vector rather than btree.
Scalar Scalar int size
Definition: benchVecAdd.cpp:17
std::map< size_t, std::vector< size_t > > arrays() const
Return all sets, i.e. a partition of all elements.
Definition: DSFVector.cpp:110
#define EXPECT(condition)
Definition: Test.h:150
Array< int, Dynamic, 1 > v
std::map< size_t, std::set< size_t > > sets() const
Return all sets, i.e. a partition of all elements.
Definition: DSFVector.cpp:102
bool isSingleton(const size_t &label) const
Find whether there is one and only one occurrence for the given {label}.
Definition: DSFVector.cpp:79
#define LONGS_EQUAL(expected, actual)
Definition: Test.h:134
traits
Definition: chartTesting.h:28
std::set< size_t > set(const size_t &label) const
Get the nodes in the tree with the given label.
Definition: DSFVector.cpp:93
#define EXPECT_LONGS_EQUAL(expected, actual)
Definition: Test.h:154
void merge(const size_t &i1, const size_t &i2)
Merge the sets containing i1 and i2. Does nothing if i1 and i2 are already in the same set...
Definition: DSFVector.cpp:54
TEST(SmartFactorBase, Pinhole)
const KeyVector keys


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