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
47 namespace ceres {
48 namespace internal {
49
50 class VisibilityTest : public ::testing::Test {
51 };
52
TEST(VisibilityTest,SimpleMatrix)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
TEST(VisibilityTest,NoEBlocks)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