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 (at) google.com (Sameer Agarwal) 30 31 #include "ceres/triplet_sparse_matrix.h" 32 33 #include "gtest/gtest.h" 34 #include "ceres/matrix_proto.h" 35 #include "ceres/internal/scoped_ptr.h" 36 37 namespace ceres { 38 namespace internal { 39 40 TEST(TripletSparseMatrix, DefaultConstructorReturnsEmptyObject) { 41 TripletSparseMatrix m; 42 EXPECT_EQ(m.num_rows(), 0); 43 EXPECT_EQ(m.num_cols(), 0); 44 EXPECT_EQ(m.num_nonzeros(), 0); 45 EXPECT_EQ(m.max_num_nonzeros(), 0); 46 } 47 48 TEST(TripletSparseMatrix, SimpleConstructorAndBasicOperations) { 49 // Build a matrix 50 TripletSparseMatrix m(2, 5, 4); 51 EXPECT_EQ(m.num_rows(), 2); 52 EXPECT_EQ(m.num_cols(), 5); 53 EXPECT_EQ(m.num_nonzeros(), 0); 54 EXPECT_EQ(m.max_num_nonzeros(), 4); 55 56 m.mutable_rows()[0] = 0; 57 m.mutable_cols()[0] = 1; 58 m.mutable_values()[0] = 2.5; 59 60 m.mutable_rows()[1] = 1; 61 m.mutable_cols()[1] = 4; 62 m.mutable_values()[1] = 5.2; 63 m.set_num_nonzeros(2); 64 65 EXPECT_EQ(m.num_nonzeros(), 2); 66 67 ASSERT_TRUE(m.AllTripletsWithinBounds()); 68 69 // We should never be able resize and lose data 70 EXPECT_DEATH_IF_SUPPORTED(m.Reserve(1), "Reallocation will cause data loss"); 71 72 // We should be able to resize while preserving data 73 m.Reserve(50); 74 EXPECT_EQ(m.max_num_nonzeros(), 50); 75 76 m.Reserve(3); 77 EXPECT_EQ(m.max_num_nonzeros(), 50); // The space is already reserved. 78 79 EXPECT_EQ(m.rows()[0], 0); 80 EXPECT_EQ(m.rows()[1], 1); 81 82 EXPECT_EQ(m.cols()[0], 1); 83 EXPECT_EQ(m.cols()[1], 4); 84 85 EXPECT_DOUBLE_EQ(m.values()[0], 2.5); 86 EXPECT_DOUBLE_EQ(m.values()[1], 5.2); 87 88 // Bounds check should fail 89 m.mutable_rows()[0] = 10; 90 EXPECT_FALSE(m.AllTripletsWithinBounds()); 91 92 m.mutable_rows()[0] = 1; 93 m.mutable_cols()[0] = 100; 94 EXPECT_FALSE(m.AllTripletsWithinBounds()); 95 96 // Remove all data and then resize the data store 97 m.SetZero(); 98 EXPECT_EQ(m.num_nonzeros(), 0); 99 m.Reserve(1); 100 } 101 102 TEST(TripletSparseMatrix, CopyConstructor) { 103 TripletSparseMatrix orig(2, 5, 4); 104 orig.mutable_rows()[0] = 0; 105 orig.mutable_cols()[0] = 1; 106 orig.mutable_values()[0] = 2.5; 107 108 orig.mutable_rows()[1] = 1; 109 orig.mutable_cols()[1] = 4; 110 orig.mutable_values()[1] = 5.2; 111 orig.set_num_nonzeros(2); 112 113 TripletSparseMatrix cpy(orig); 114 115 EXPECT_EQ(cpy.num_rows(), 2); 116 EXPECT_EQ(cpy.num_cols(), 5); 117 ASSERT_EQ(cpy.num_nonzeros(), 2); 118 EXPECT_EQ(cpy.max_num_nonzeros(), 4); 119 120 EXPECT_EQ(cpy.rows()[0], 0); 121 EXPECT_EQ(cpy.rows()[1], 1); 122 123 EXPECT_EQ(cpy.cols()[0], 1); 124 EXPECT_EQ(cpy.cols()[1], 4); 125 126 EXPECT_DOUBLE_EQ(cpy.values()[0], 2.5); 127 EXPECT_DOUBLE_EQ(cpy.values()[1], 5.2); 128 } 129 130 TEST(TripletSparseMatrix, AssignmentOperator) { 131 TripletSparseMatrix orig(2, 5, 4); 132 orig.mutable_rows()[0] = 0; 133 orig.mutable_cols()[0] = 1; 134 orig.mutable_values()[0] = 2.5; 135 136 orig.mutable_rows()[1] = 1; 137 orig.mutable_cols()[1] = 4; 138 orig.mutable_values()[1] = 5.2; 139 orig.set_num_nonzeros(2); 140 141 TripletSparseMatrix cpy(3, 50, 40); 142 cpy.mutable_rows()[0] = 0; 143 cpy.mutable_cols()[0] = 10; 144 cpy.mutable_values()[0] = 10.22; 145 146 cpy.mutable_rows()[1] = 2; 147 cpy.mutable_cols()[1] = 23; 148 cpy.mutable_values()[1] = 34.45; 149 150 cpy.mutable_rows()[0] = 0; 151 cpy.mutable_cols()[0] = 10; 152 cpy.mutable_values()[0] = 10.22; 153 154 cpy.mutable_rows()[1] = 0; 155 cpy.mutable_cols()[1] = 3; 156 cpy.mutable_values()[1] = 4.4; 157 cpy.set_num_nonzeros(3); 158 159 cpy = orig; 160 161 EXPECT_EQ(cpy.num_rows(), 2); 162 EXPECT_EQ(cpy.num_cols(), 5); 163 ASSERT_EQ(cpy.num_nonzeros(), 2); 164 EXPECT_EQ(cpy.max_num_nonzeros(), 4); 165 166 EXPECT_EQ(cpy.rows()[0], 0); 167 EXPECT_EQ(cpy.rows()[1], 1); 168 169 EXPECT_EQ(cpy.cols()[0], 1); 170 EXPECT_EQ(cpy.cols()[1], 4); 171 172 EXPECT_DOUBLE_EQ(cpy.values()[0], 2.5); 173 EXPECT_DOUBLE_EQ(cpy.values()[1], 5.2); 174 } 175 176 TEST(TripletSparseMatrix, AppendRows) { 177 // Build one matrix. 178 TripletSparseMatrix m(2, 5, 4); 179 m.mutable_rows()[0] = 0; 180 m.mutable_cols()[0] = 1; 181 m.mutable_values()[0] = 2.5; 182 183 m.mutable_rows()[1] = 1; 184 m.mutable_cols()[1] = 4; 185 m.mutable_values()[1] = 5.2; 186 m.set_num_nonzeros(2); 187 188 // Build another matrix. 189 TripletSparseMatrix a(10, 5, 4); 190 a.mutable_rows()[0] = 0; 191 a.mutable_cols()[0] = 1; 192 a.mutable_values()[0] = 3.5; 193 194 a.mutable_rows()[1] = 1; 195 a.mutable_cols()[1] = 4; 196 a.mutable_values()[1] = 6.2; 197 198 a.mutable_rows()[2] = 9; 199 a.mutable_cols()[2] = 5; 200 a.mutable_values()[2] = 1; 201 a.set_num_nonzeros(3); 202 203 // Glue the second matrix to the bottom of the first. 204 m.AppendRows(a); 205 206 EXPECT_EQ(m.num_rows(), 12); 207 EXPECT_EQ(m.num_cols(), 5); 208 ASSERT_EQ(m.num_nonzeros(), 5); 209 210 EXPECT_EQ(m.values()[0], 2.5); 211 EXPECT_EQ(m.values()[1], 5.2); 212 EXPECT_EQ(m.values()[2], 3.5); 213 EXPECT_EQ(m.values()[3], 6.2); 214 EXPECT_EQ(m.values()[4], 1); 215 216 EXPECT_EQ(m.rows()[0], 0); 217 EXPECT_EQ(m.rows()[1], 1); 218 EXPECT_EQ(m.rows()[2], 2); 219 EXPECT_EQ(m.rows()[3], 3); 220 EXPECT_EQ(m.rows()[4], 11); 221 222 EXPECT_EQ(m.cols()[0], 1); 223 EXPECT_EQ(m.cols()[1], 4); 224 EXPECT_EQ(m.cols()[2], 1); 225 EXPECT_EQ(m.cols()[3], 4); 226 EXPECT_EQ(m.cols()[4], 5); 227 } 228 229 TEST(TripletSparseMatrix, AppendCols) { 230 // Build one matrix. 231 TripletSparseMatrix m(2, 5, 4); 232 m.mutable_rows()[0] = 0; 233 m.mutable_cols()[0] = 1; 234 m.mutable_values()[0] = 2.5; 235 236 m.mutable_rows()[1] = 1; 237 m.mutable_cols()[1] = 4; 238 m.mutable_values()[1] = 5.2; 239 m.set_num_nonzeros(2); 240 241 // Build another matrix. 242 TripletSparseMatrix a(2, 15, 4); 243 a.mutable_rows()[0] = 0; 244 a.mutable_cols()[0] = 1; 245 a.mutable_values()[0] = 3.5; 246 247 a.mutable_rows()[1] = 1; 248 a.mutable_cols()[1] = 4; 249 a.mutable_values()[1] = 6.2; 250 251 a.mutable_rows()[2] = 0; 252 a.mutable_cols()[2] = 10; 253 a.mutable_values()[2] = 1; 254 a.set_num_nonzeros(3); 255 256 // Glue the second matrix to the left of the first. 257 m.AppendCols(a); 258 259 EXPECT_EQ(m.num_rows(), 2); 260 EXPECT_EQ(m.num_cols(), 20); 261 ASSERT_EQ(m.num_nonzeros(), 5); 262 263 EXPECT_EQ(m.values()[0], 2.5); 264 EXPECT_EQ(m.values()[1], 5.2); 265 EXPECT_EQ(m.values()[2], 3.5); 266 EXPECT_EQ(m.values()[3], 6.2); 267 EXPECT_EQ(m.values()[4], 1); 268 269 EXPECT_EQ(m.rows()[0], 0); 270 EXPECT_EQ(m.rows()[1], 1); 271 EXPECT_EQ(m.rows()[2], 0); 272 EXPECT_EQ(m.rows()[3], 1); 273 EXPECT_EQ(m.rows()[4], 0); 274 275 EXPECT_EQ(m.cols()[0], 1); 276 EXPECT_EQ(m.cols()[1], 4); 277 EXPECT_EQ(m.cols()[2], 6); 278 EXPECT_EQ(m.cols()[3], 9); 279 EXPECT_EQ(m.cols()[4], 15); 280 } 281 282 TEST(TripletSparseMatrix, CreateDiagonalMatrix) { 283 scoped_array<double> values(new double[10]); 284 for (int i = 0; i < 10; ++i) 285 values[i] = i; 286 287 scoped_ptr<TripletSparseMatrix> m( 288 TripletSparseMatrix::CreateSparseDiagonalMatrix(values.get(), 10)); 289 EXPECT_EQ(m->num_rows(), 10); 290 EXPECT_EQ(m->num_cols(), 10); 291 ASSERT_EQ(m->num_nonzeros(), 10); 292 for (int i = 0; i < 10 ; ++i) { 293 EXPECT_EQ(m->rows()[i], i); 294 EXPECT_EQ(m->cols()[i], i); 295 EXPECT_EQ(m->values()[i], i); 296 } 297 } 298 299 TEST(TripletSparseMatrix, Resize) { 300 TripletSparseMatrix m(10, 20, 200); 301 int nnz = 0; 302 for (int i = 0; i < 10; ++i) { 303 for (int j = 0; j < 20; ++j) { 304 m.mutable_rows()[nnz] = i; 305 m.mutable_cols()[nnz] = j; 306 m.mutable_values()[nnz++] = i+j; 307 } 308 } 309 m.set_num_nonzeros(nnz); 310 m.Resize(5, 6); 311 EXPECT_EQ(m.num_rows(), 5); 312 EXPECT_EQ(m.num_cols(), 6); 313 ASSERT_EQ(m.num_nonzeros(), 30); 314 for (int i = 0; i < 30; ++i) { 315 EXPECT_EQ(m.values()[i], m.rows()[i] + m.cols()[i]); 316 } 317 } 318 319 #ifndef CERES_NO_PROTOCOL_BUFFERS 320 TEST(TripletSparseMatrix, Serialization) { 321 TripletSparseMatrix m(2, 5, 4); 322 323 m.mutable_rows()[0] = 0; 324 m.mutable_cols()[0] = 1; 325 m.mutable_values()[0] = 2.5; 326 327 m.mutable_rows()[1] = 1; 328 m.mutable_cols()[1] = 4; 329 m.mutable_values()[1] = 5.2; 330 m.set_num_nonzeros(2); 331 332 // Roundtrip through serialization and check for equality. 333 SparseMatrixProto proto; 334 m.ToProto(&proto); 335 336 TripletSparseMatrix n(proto); 337 338 ASSERT_EQ(n.num_rows(), 2); 339 ASSERT_EQ(n.num_cols(), 5); 340 341 // Note that max_num_nonzeros gets truncated; the serialization 342 ASSERT_EQ(n.num_nonzeros(), 2); 343 ASSERT_EQ(n.max_num_nonzeros(), 2); 344 345 for (int i = 0; i < m.num_nonzeros(); ++i) { 346 EXPECT_EQ(m.rows()[i], n.rows()[i]); 347 EXPECT_EQ(m.cols()[i], n.cols()[i]); 348 EXPECT_EQ(m.values()[i], n.values()[i]); 349 } 350 } 351 #endif 352 353 } // namespace internal 354 } // namespace ceres 355
