internal/ceres/visibility_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: kushalav@google.com (Avanish Kushal)
  30 //         sameeragarwal@google.com (Sameer Agarwal)
  31
  32 #include "ceres/visibility.h"
  33
  34 #include <set>
  35 #include <vector>
  36 #include "ceres/block_structure.h"
  37 #include "ceres/graph.h"
  38 #include "ceres/internal/scoped_ptr.h"
  39 #include "glog/logging.h"
  40 #include "gtest/gtest.h"
  41
  42 namespace ceres {
  43 namespace internal {
  44
  45 using std::set;
  46 using std::vector;
  47
  48 class VisibilityTest : public ::testing::Test {
  49 };
  50
  51 TEST(VisibilityTest, SimpleMatrix) {
  52   //   A = [1 0 0 0 0 1
  53   //        1 0 0 1 0 0
  54   //        0 1 1 0 0 0
  55   //        0 1 0 0 1 0]
  56
  57   int num_cols = 6;
  58   int num_eliminate_blocks = 2;
  59   CompressedRowBlockStructure bs;
  60
  61   // Row 1
  62   {
  63     bs.rows.push_back(CompressedRow());
  64     CompressedRow& row = bs.rows.back();
  65     row.block.size = 2;
  66     row.block.position = 0;
  67     row.cells.push_back(Cell(0, 0));
  68     row.cells.push_back(Cell(5, 0));
  69   }
  70
  71   // Row 2
  72   {
  73     bs.rows.push_back(CompressedRow());
  74     CompressedRow& row = bs.rows.back();
  75     row.block.size = 2;
  76     row.block.position = 2;
  77     row.cells.push_back(Cell(0, 1));
  78     row.cells.push_back(Cell(3, 1));
  79   }
  80
  81   // Row 3
  82   {
  83     bs.rows.push_back(CompressedRow());
  84     CompressedRow& row = bs.rows.back();
  85     row.block.size = 2;
  86     row.block.position = 4;
  87     row.cells.push_back(Cell(1, 2));
  88     row.cells.push_back(Cell(2, 2));
  89   }
  90
  91   // Row 4
  92   {
  93     bs.rows.push_back(CompressedRow());
  94     CompressedRow& row = bs.rows.back();
  95     row.block.size = 2;
  96     row.block.position = 6;
  97     row.cells.push_back(Cell(1, 3));
  98     row.cells.push_back(Cell(4, 3));
  99   }
 100   bs.cols.resize(num_cols);
 101
 102   vector< set<int> > visibility;
 103   ComputeVisibility(bs, num_eliminate_blocks, &visibility);
 104   ASSERT_EQ(visibility.size(), num_cols - num_eliminate_blocks);
 105   for (int i = 0; i < visibility.size(); ++i) {
 106     ASSERT_EQ(visibility[i].size(), 1);
 107   }
 108
 109   scoped_ptr<WeightedGraph<int> > graph(CreateSchurComplementGraph(visibility));
 110   EXPECT_EQ(graph->vertices().size(), visibility.size());
 111   for (int i = 0; i < visibility.size(); ++i) {
 112     EXPECT_EQ(graph->VertexWeight(i), 1.0);
 113   }
 114
 115   for (int i = 0; i < visibility.size(); ++i) {
 116     for (int j = i; j < visibility.size(); ++j) {
 117       double edge_weight = 0.0;
 118       if ((i == 1 && j == 3) || (i == 0 && j == 2) || (i == j)) {
 119         edge_weight = 1.0;
 120       }
 121
 122       EXPECT_EQ(graph->EdgeWeight(i, j), edge_weight)
 123           << "Edge: " << i << " " << j
 124           << " weight: " << graph->EdgeWeight(i, j)
 125           << " expected weight: " << edge_weight;
 126     }
 127   }
 128 }
 129
 130
 131 TEST(VisibilityTest, NoEBlocks) {
 132   //   A = [1 0 0 0 0 0
 133   //        1 0 0 0 0 0
 134   //        0 1 0 0 0 0
 135   //        0 1 0 0 0 0]
 136
 137   int num_cols = 6;
 138   int num_eliminate_blocks = 2;
 139   CompressedRowBlockStructure bs;
 140
 141   // Row 1
 142   {
 143     bs.rows.push_back(CompressedRow());
 144     CompressedRow& row = bs.rows.back();
 145     row.block.size = 2;
 146     row.block.position = 0;
 147     row.cells.push_back(Cell(0, 0));
 148   }
 149
 150   // Row 2
 151   {
 152     bs.rows.push_back(CompressedRow());
 153     CompressedRow& row = bs.rows.back();
 154     row.block.size = 2;
 155     row.block.position = 2;
 156     row.cells.push_back(Cell(0, 1));
 157   }
 158
 159   // Row 3
 160   {
 161     bs.rows.push_back(CompressedRow());
 162     CompressedRow& row = bs.rows.back();
 163     row.block.size = 2;
 164     row.block.position = 4;
 165     row.cells.push_back(Cell(1, 2));
 166   }
 167
 168   // Row 4
 169   {
 170     bs.rows.push_back(CompressedRow());
 171     CompressedRow& row = bs.rows.back();
 172     row.block.size = 2;
 173     row.block.position = 6;
 174     row.cells.push_back(Cell(1, 3));
 175   }
 176   bs.cols.resize(num_cols);
 177
 178   vector<set<int> > visibility;
 179   ComputeVisibility(bs, num_eliminate_blocks, &visibility);
 180   ASSERT_EQ(visibility.size(), num_cols - num_eliminate_blocks);
 181   for (int i = 0; i < visibility.size(); ++i) {
 182     ASSERT_EQ(visibility[i].size(), 0);
 183   }
 184
 185   scoped_ptr<WeightedGraph<int> > graph(CreateSchurComplementGraph(visibility));
 186   EXPECT_EQ(graph->vertices().size(), visibility.size());
 187   for (int i = 0; i < visibility.size(); ++i) {
 188     EXPECT_EQ(graph->VertexWeight(i), 1.0);
 189   }
 190
 191   for (int i = 0; i < visibility.size(); ++i) {
 192     for (int j = i; j < visibility.size(); ++j) {
 193       double edge_weight = 0.0;
 194       if (i == j) {
 195         edge_weight = 1.0;
 196       }
 197       EXPECT_EQ(graph->EdgeWeight(i, j), edge_weight)
 198           << "Edge: " << i << " " << j
 199           << " weight: " << graph->EdgeWeight(i, j)
 200           << " expected weight: " << edge_weight;
 201     }
 202   }
 203 }
 204
 205 }  // namespace internal
 206 }  // namespace ceres