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
36namespace ceres {
37namespace internal {
38
39TEST(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
47TEST(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
101TEST(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
129TEST(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
175TEST(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
228TEST(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
281TEST(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
298TEST(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