internal/ceres/triplet_sparse_matrix_test.cc

   1 // Ceres Solver - A fast non-linear least squares minimizer
   2 // Copyright 2015 Google Inc. All rights reserved.
   3 // http://ceres-solver.org/
   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
  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