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: sameeragarwal@google.com (Sameer Agarwal)
30
31 #include "ceres/graph_algorithms.h"
32
33 #include <algorithm>
34 #include "gtest/gtest.h"
35 #include "ceres/collections_port.h"
36 #include "ceres/graph.h"
37 #include "ceres/internal/port.h"
38 #include "ceres/internal/scoped_ptr.h"
39
40 namespace ceres {
41 namespace internal {
42
TEST(IndependentSetOrdering,Chain)43 TEST(IndependentSetOrdering, Chain) {
44 Graph<int> graph;
45 graph.AddVertex(0);
46 graph.AddVertex(1);
47 graph.AddVertex(2);
48 graph.AddVertex(3);
49 graph.AddVertex(4);
50
51 graph.AddEdge(0, 1);
52 graph.AddEdge(1, 2);
53 graph.AddEdge(2, 3);
54 graph.AddEdge(3, 4);
55
56 // 0-1-2-3-4
57 // 0, 2, 4 should be in the independent set.
58 vector<int> ordering;
59 int independent_set_size = IndependentSetOrdering(graph, &ordering);
60
61 sort(ordering.begin(), ordering.begin() + 3);
62 sort(ordering.begin() + 3, ordering.end());
63
64 EXPECT_EQ(independent_set_size, 3);
65 EXPECT_EQ(ordering.size(), 5);
66 EXPECT_EQ(ordering[0], 0);
67 EXPECT_EQ(ordering[1], 2);
68 EXPECT_EQ(ordering[2], 4);
69 EXPECT_EQ(ordering[3], 1);
70 EXPECT_EQ(ordering[4], 3);
71 }
72
TEST(IndependentSetOrdering,Star)73 TEST(IndependentSetOrdering, Star) {
74 Graph<int> graph;
75 graph.AddVertex(0);
76 graph.AddVertex(1);
77 graph.AddVertex(2);
78 graph.AddVertex(3);
79 graph.AddVertex(4);
80
81 graph.AddEdge(0, 1);
82 graph.AddEdge(0, 2);
83 graph.AddEdge(0, 3);
84 graph.AddEdge(0, 4);
85
86 // 1
87 // |
88 // 4-0-2
89 // |
90 // 3
91 // 1, 2, 3, 4 should be in the indepdendent set.
92 vector<int> ordering;
93 int independent_set_size = IndependentSetOrdering(graph, &ordering);
94 EXPECT_EQ(independent_set_size, 4);
95 EXPECT_EQ(ordering.size(), 5);
96 EXPECT_EQ(ordering[4], 0);
97 sort(ordering.begin(), ordering.begin() + 4);
98 EXPECT_EQ(ordering[0], 1);
99 EXPECT_EQ(ordering[1], 2);
100 EXPECT_EQ(ordering[2], 3);
101 EXPECT_EQ(ordering[3], 4);
102 }
103
TEST(Degree2MaximumSpanningForest,PreserveWeights)104 TEST(Degree2MaximumSpanningForest, PreserveWeights) {
105 Graph<int> graph;
106 graph.AddVertex(0, 1.0);
107 graph.AddVertex(1, 2.0);
108 graph.AddEdge(0, 1, 0.5);
109 graph.AddEdge(1, 0, 0.5);
110
111 scoped_ptr<Graph<int> > forest(Degree2MaximumSpanningForest(graph));
112
113 const HashSet<int>& vertices = forest->vertices();
114 EXPECT_EQ(vertices.size(), 2);
115 EXPECT_EQ(forest->VertexWeight(0), 1.0);
116 EXPECT_EQ(forest->VertexWeight(1), 2.0);
117 EXPECT_EQ(forest->Neighbors(0).size(), 1.0);
118 EXPECT_EQ(forest->EdgeWeight(0, 1), 0.5);
119 }
120
TEST(Degree2MaximumSpanningForest,StarGraph)121 TEST(Degree2MaximumSpanningForest, StarGraph) {
122 Graph<int> graph;
123 graph.AddVertex(0);
124 graph.AddVertex(1);
125 graph.AddVertex(2);
126 graph.AddVertex(3);
127 graph.AddVertex(4);
128
129 graph.AddEdge(0, 1, 1.0);
130 graph.AddEdge(0, 2, 2.0);
131 graph.AddEdge(0, 3, 3.0);
132 graph.AddEdge(0, 4, 4.0);
133
134 scoped_ptr<Graph<int> > forest(Degree2MaximumSpanningForest(graph));
135 const HashSet<int>& vertices = forest->vertices();
136 EXPECT_EQ(vertices.size(), 5);
137
138 {
139 const HashSet<int>& neighbors = forest->Neighbors(0);
140 EXPECT_EQ(neighbors.size(), 2);
141 EXPECT_TRUE(neighbors.find(4) != neighbors.end());
142 EXPECT_TRUE(neighbors.find(3) != neighbors.end());
143 }
144
145 {
146 const HashSet<int>& neighbors = forest->Neighbors(3);
147 EXPECT_EQ(neighbors.size(), 1);
148 EXPECT_TRUE(neighbors.find(0) != neighbors.end());
149 }
150
151 {
152 const HashSet<int>& neighbors = forest->Neighbors(4);
153 EXPECT_EQ(neighbors.size(), 1);
154 EXPECT_TRUE(neighbors.find(0) != neighbors.end());
155 }
156
157 {
158 const HashSet<int>& neighbors = forest->Neighbors(1);
159 EXPECT_EQ(neighbors.size(), 0);
160 }
161
162 {
163 const HashSet<int>& neighbors = forest->Neighbors(2);
164 EXPECT_EQ(neighbors.size(), 0);
165 }
166 }
167
TEST(VertexTotalOrdering,TotalOrdering)168 TEST(VertexTotalOrdering, TotalOrdering) {
169 Graph<int> graph;
170 graph.AddVertex(0);
171 graph.AddVertex(1);
172 graph.AddVertex(2);
173 graph.AddVertex(3);
174
175 // 0-1
176 // |
177 // 2-3
178 // 0,1 and 2 have degree 1 and 3 has degree 2.
179 graph.AddEdge(0, 1, 1.0);
180 graph.AddEdge(2, 3, 1.0);
181 VertexTotalOrdering<int> less_than(graph);
182
183 for (int i = 0; i < 4; ++i) {
184 EXPECT_FALSE(less_than(i, i)) << "Failing vertex: " << i;
185 for (int j = 0; j < 4; ++j) {
186 if (i != j) {
187 EXPECT_TRUE(less_than(i, j) ^ less_than(j, i))
188 << "Failing vertex pair: " << i << " " << j;
189 }
190 }
191 }
192
193 for (int i = 0; i < 3; ++i) {
194 EXPECT_TRUE(less_than(i, 3));
195 EXPECT_FALSE(less_than(3, i));
196 }
197 }
198
199
TEST(StableIndependentSet,BreakTies)200 TEST(StableIndependentSet, BreakTies) {
201 Graph<int> graph;
202 graph.AddVertex(0);
203 graph.AddVertex(1);
204 graph.AddVertex(2);
205 graph.AddVertex(3);
206
207 graph.AddEdge(0, 1);
208 graph.AddEdge(0, 2);
209 graph.AddEdge(0, 3);
210 graph.AddEdge(1, 2);
211 graph.AddEdge(1, 3);
212 graph.AddEdge(2, 3);
213
214 // Since this is a completely connected graph, the independent set
215 // contains exactly one vertex. StableIndependentSetOrdering
216 // guarantees that it will always be the first vertex in the
217 // ordering vector.
218 {
219 vector<int> ordering;
220 ordering.push_back(0);
221 ordering.push_back(1);
222 ordering.push_back(2);
223 ordering.push_back(3);
224 const int independent_set_size =
225 StableIndependentSetOrdering(graph, &ordering);
226 EXPECT_EQ(independent_set_size, 1);
227 EXPECT_EQ(ordering[0], 0);
228 }
229
230 {
231 vector<int> ordering;
232 ordering.push_back(1);
233 ordering.push_back(0);
234 ordering.push_back(2);
235 ordering.push_back(3);
236 const int independent_set_size =
237 StableIndependentSetOrdering(graph, &ordering);
238 EXPECT_EQ(independent_set_size, 1);
239 EXPECT_EQ(ordering[0], 1);
240 }
241
242 }
243 } // namespace internal
244 } // namespace ceres
245