1 // Ceres Solver - A fast non-linear least squares minimizer
2 // Copyright 2010, 2011, 2012 Google Inc. All rights reserved.
3 // http://code.google.com/p/ceres-solver/
4 //
5 // Redistribution and use in source and binary forms, with or without
6 // modification, are permitted provided that the following conditions are met:
7 //
8 // * Redistributions of source code must retain the above copyright notice,
9 // this list of conditions and the following disclaimer.
10 // * Redistributions in binary form must reproduce the above copyright notice,
11 // this list of conditions and the following disclaimer in the documentation
12 // and/or other materials provided with the distribution.
13 // * Neither the name of Google Inc. nor the names of its contributors may be
14 // used to endorse or promote products derived from this software without
15 // specific prior written permission.
16 //
17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
21 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27 // POSSIBILITY OF SUCH DAMAGE.
28 //
29 // Author: sameeragarwal@google.com (Sameer Agarwal)
30
31 #include "ceres/triplet_sparse_matrix.h"
32
33 #include "gtest/gtest.h"
34 #include "ceres/internal/scoped_ptr.h"
35
36 namespace ceres {
37 namespace internal {
38
TEST(TripletSparseMatrix,DefaultConstructorReturnsEmptyObject)39 TEST(TripletSparseMatrix, DefaultConstructorReturnsEmptyObject) {
40 TripletSparseMatrix m;
41 EXPECT_EQ(m.num_rows(), 0);
42 EXPECT_EQ(m.num_cols(), 0);
43 EXPECT_EQ(m.num_nonzeros(), 0);
44 EXPECT_EQ(m.max_num_nonzeros(), 0);
45 }
46
TEST(TripletSparseMatrix,SimpleConstructorAndBasicOperations)47 TEST(TripletSparseMatrix, SimpleConstructorAndBasicOperations) {
48 // Build a matrix
49 TripletSparseMatrix m(2, 5, 4);
50 EXPECT_EQ(m.num_rows(), 2);
51 EXPECT_EQ(m.num_cols(), 5);
52 EXPECT_EQ(m.num_nonzeros(), 0);
53 EXPECT_EQ(m.max_num_nonzeros(), 4);
54
55 m.mutable_rows()[0] = 0;
56 m.mutable_cols()[0] = 1;
57 m.mutable_values()[0] = 2.5;
58
59 m.mutable_rows()[1] = 1;
60 m.mutable_cols()[1] = 4;
61 m.mutable_values()[1] = 5.2;
62 m.set_num_nonzeros(2);
63
64 EXPECT_EQ(m.num_nonzeros(), 2);
65
66 ASSERT_TRUE(m.AllTripletsWithinBounds());
67
68 // We should never be able resize and lose data
69 EXPECT_DEATH_IF_SUPPORTED(m.Reserve(1), "Reallocation will cause data loss");
70
71 // We should be able to resize while preserving data
72 m.Reserve(50);
73 EXPECT_EQ(m.max_num_nonzeros(), 50);
74
75 m.Reserve(3);
76 EXPECT_EQ(m.max_num_nonzeros(), 50); // The space is already reserved.
77
78 EXPECT_EQ(m.rows()[0], 0);
79 EXPECT_EQ(m.rows()[1], 1);
80
81 EXPECT_EQ(m.cols()[0], 1);
82 EXPECT_EQ(m.cols()[1], 4);
83
84 EXPECT_DOUBLE_EQ(m.values()[0], 2.5);
85 EXPECT_DOUBLE_EQ(m.values()[1], 5.2);
86
87 // Bounds check should fail
88 m.mutable_rows()[0] = 10;
89 EXPECT_FALSE(m.AllTripletsWithinBounds());
90
91 m.mutable_rows()[0] = 1;
92 m.mutable_cols()[0] = 100;
93 EXPECT_FALSE(m.AllTripletsWithinBounds());
94
95 // Remove all data and then resize the data store
96 m.SetZero();
97 EXPECT_EQ(m.num_nonzeros(), 0);
98 m.Reserve(1);
99 }
100
TEST(TripletSparseMatrix,CopyConstructor)101 TEST(TripletSparseMatrix, CopyConstructor) {
102 TripletSparseMatrix orig(2, 5, 4);
103 orig.mutable_rows()[0] = 0;
104 orig.mutable_cols()[0] = 1;
105 orig.mutable_values()[0] = 2.5;
106
107 orig.mutable_rows()[1] = 1;
108 orig.mutable_cols()[1] = 4;
109 orig.mutable_values()[1] = 5.2;
110 orig.set_num_nonzeros(2);
111
112 TripletSparseMatrix cpy(orig);
113
114 EXPECT_EQ(cpy.num_rows(), 2);
115 EXPECT_EQ(cpy.num_cols(), 5);
116 ASSERT_EQ(cpy.num_nonzeros(), 2);
117 EXPECT_EQ(cpy.max_num_nonzeros(), 4);
118
119 EXPECT_EQ(cpy.rows()[0], 0);
120 EXPECT_EQ(cpy.rows()[1], 1);
121
122 EXPECT_EQ(cpy.cols()[0], 1);
123 EXPECT_EQ(cpy.cols()[1], 4);
124
125 EXPECT_DOUBLE_EQ(cpy.values()[0], 2.5);
126 EXPECT_DOUBLE_EQ(cpy.values()[1], 5.2);
127 }
128
TEST(TripletSparseMatrix,AssignmentOperator)129 TEST(TripletSparseMatrix, AssignmentOperator) {
130 TripletSparseMatrix orig(2, 5, 4);
131 orig.mutable_rows()[0] = 0;
132 orig.mutable_cols()[0] = 1;
133 orig.mutable_values()[0] = 2.5;
134
135 orig.mutable_rows()[1] = 1;
136 orig.mutable_cols()[1] = 4;
137 orig.mutable_values()[1] = 5.2;
138 orig.set_num_nonzeros(2);
139
140 TripletSparseMatrix cpy(3, 50, 40);
141 cpy.mutable_rows()[0] = 0;
142 cpy.mutable_cols()[0] = 10;
143 cpy.mutable_values()[0] = 10.22;
144
145 cpy.mutable_rows()[1] = 2;
146 cpy.mutable_cols()[1] = 23;
147 cpy.mutable_values()[1] = 34.45;
148
149 cpy.mutable_rows()[0] = 0;
150 cpy.mutable_cols()[0] = 10;
151 cpy.mutable_values()[0] = 10.22;
152
153 cpy.mutable_rows()[1] = 0;
154 cpy.mutable_cols()[1] = 3;
155 cpy.mutable_values()[1] = 4.4;
156 cpy.set_num_nonzeros(3);
157
158 cpy = orig;
159
160 EXPECT_EQ(cpy.num_rows(), 2);
161 EXPECT_EQ(cpy.num_cols(), 5);
162 ASSERT_EQ(cpy.num_nonzeros(), 2);
163 EXPECT_EQ(cpy.max_num_nonzeros(), 4);
164
165 EXPECT_EQ(cpy.rows()[0], 0);
166 EXPECT_EQ(cpy.rows()[1], 1);
167
168 EXPECT_EQ(cpy.cols()[0], 1);
169 EXPECT_EQ(cpy.cols()[1], 4);
170
171 EXPECT_DOUBLE_EQ(cpy.values()[0], 2.5);
172 EXPECT_DOUBLE_EQ(cpy.values()[1], 5.2);
173 }
174
TEST(TripletSparseMatrix,AppendRows)175 TEST(TripletSparseMatrix, AppendRows) {
176 // Build one matrix.
177 TripletSparseMatrix m(2, 5, 4);
178 m.mutable_rows()[0] = 0;
179 m.mutable_cols()[0] = 1;
180 m.mutable_values()[0] = 2.5;
181
182 m.mutable_rows()[1] = 1;
183 m.mutable_cols()[1] = 4;
184 m.mutable_values()[1] = 5.2;
185 m.set_num_nonzeros(2);
186
187 // Build another matrix.
188 TripletSparseMatrix a(10, 5, 4);
189 a.mutable_rows()[0] = 0;
190 a.mutable_cols()[0] = 1;
191 a.mutable_values()[0] = 3.5;
192
193 a.mutable_rows()[1] = 1;
194 a.mutable_cols()[1] = 4;
195 a.mutable_values()[1] = 6.2;
196
197 a.mutable_rows()[2] = 9;
198 a.mutable_cols()[2] = 5;
199 a.mutable_values()[2] = 1;
200 a.set_num_nonzeros(3);
201
202 // Glue the second matrix to the bottom of the first.
203 m.AppendRows(a);
204
205 EXPECT_EQ(m.num_rows(), 12);
206 EXPECT_EQ(m.num_cols(), 5);
207 ASSERT_EQ(m.num_nonzeros(), 5);
208
209 EXPECT_EQ(m.values()[0], 2.5);
210 EXPECT_EQ(m.values()[1], 5.2);
211 EXPECT_EQ(m.values()[2], 3.5);
212 EXPECT_EQ(m.values()[3], 6.2);
213 EXPECT_EQ(m.values()[4], 1);
214
215 EXPECT_EQ(m.rows()[0], 0);
216 EXPECT_EQ(m.rows()[1], 1);
217 EXPECT_EQ(m.rows()[2], 2);
218 EXPECT_EQ(m.rows()[3], 3);
219 EXPECT_EQ(m.rows()[4], 11);
220
221 EXPECT_EQ(m.cols()[0], 1);
222 EXPECT_EQ(m.cols()[1], 4);
223 EXPECT_EQ(m.cols()[2], 1);
224 EXPECT_EQ(m.cols()[3], 4);
225 EXPECT_EQ(m.cols()[4], 5);
226 }
227
TEST(TripletSparseMatrix,AppendCols)228 TEST(TripletSparseMatrix, AppendCols) {
229 // Build one matrix.
230 TripletSparseMatrix m(2, 5, 4);
231 m.mutable_rows()[0] = 0;
232 m.mutable_cols()[0] = 1;
233 m.mutable_values()[0] = 2.5;
234
235 m.mutable_rows()[1] = 1;
236 m.mutable_cols()[1] = 4;
237 m.mutable_values()[1] = 5.2;
238 m.set_num_nonzeros(2);
239
240 // Build another matrix.
241 TripletSparseMatrix a(2, 15, 4);
242 a.mutable_rows()[0] = 0;
243 a.mutable_cols()[0] = 1;
244 a.mutable_values()[0] = 3.5;
245
246 a.mutable_rows()[1] = 1;
247 a.mutable_cols()[1] = 4;
248 a.mutable_values()[1] = 6.2;
249
250 a.mutable_rows()[2] = 0;
251 a.mutable_cols()[2] = 10;
252 a.mutable_values()[2] = 1;
253 a.set_num_nonzeros(3);
254
255 // Glue the second matrix to the left of the first.
256 m.AppendCols(a);
257
258 EXPECT_EQ(m.num_rows(), 2);
259 EXPECT_EQ(m.num_cols(), 20);
260 ASSERT_EQ(m.num_nonzeros(), 5);
261
262 EXPECT_EQ(m.values()[0], 2.5);
263 EXPECT_EQ(m.values()[1], 5.2);
264 EXPECT_EQ(m.values()[2], 3.5);
265 EXPECT_EQ(m.values()[3], 6.2);
266 EXPECT_EQ(m.values()[4], 1);
267
268 EXPECT_EQ(m.rows()[0], 0);
269 EXPECT_EQ(m.rows()[1], 1);
270 EXPECT_EQ(m.rows()[2], 0);
271 EXPECT_EQ(m.rows()[3], 1);
272 EXPECT_EQ(m.rows()[4], 0);
273
274 EXPECT_EQ(m.cols()[0], 1);
275 EXPECT_EQ(m.cols()[1], 4);
276 EXPECT_EQ(m.cols()[2], 6);
277 EXPECT_EQ(m.cols()[3], 9);
278 EXPECT_EQ(m.cols()[4], 15);
279 }
280
TEST(TripletSparseMatrix,CreateDiagonalMatrix)281 TEST(TripletSparseMatrix, CreateDiagonalMatrix) {
282 scoped_array<double> values(new double[10]);
283 for (int i = 0; i < 10; ++i)
284 values[i] = i;
285
286 scoped_ptr<TripletSparseMatrix> m(
287 TripletSparseMatrix::CreateSparseDiagonalMatrix(values.get(), 10));
288 EXPECT_EQ(m->num_rows(), 10);
289 EXPECT_EQ(m->num_cols(), 10);
290 ASSERT_EQ(m->num_nonzeros(), 10);
291 for (int i = 0; i < 10 ; ++i) {
292 EXPECT_EQ(m->rows()[i], i);
293 EXPECT_EQ(m->cols()[i], i);
294 EXPECT_EQ(m->values()[i], i);
295 }
296 }
297
TEST(TripletSparseMatrix,Resize)298 TEST(TripletSparseMatrix, Resize) {
299 TripletSparseMatrix m(10, 20, 200);
300 int nnz = 0;
301 for (int i = 0; i < 10; ++i) {
302 for (int j = 0; j < 20; ++j) {
303 m.mutable_rows()[nnz] = i;
304 m.mutable_cols()[nnz] = j;
305 m.mutable_values()[nnz++] = i+j;
306 }
307 }
308 m.set_num_nonzeros(nnz);
309 m.Resize(5, 6);
310 EXPECT_EQ(m.num_rows(), 5);
311 EXPECT_EQ(m.num_cols(), 6);
312 ASSERT_EQ(m.num_nonzeros(), 30);
313 for (int i = 0; i < 30; ++i) {
314 EXPECT_EQ(m.values()[i], m.rows()[i] + m.cols()[i]);
315 }
316 }
317
318 } // namespace internal
319 } // namespace ceres
320