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