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