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@google.com (Avanish Kushal)
30//         sameeragarwal@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
47namespace ceres {
48namespace internal {
49
50class VisibilityTest : public ::testing::Test {
51};
52
53TEST(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
133TEST(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