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/internal/scoped_ptr.h" 35 36 namespace ceres { 37 namespace internal { 38 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 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 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 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 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 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 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 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
