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
40namespace ceres {
41namespace internal {
42
43TEST(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
73TEST(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
104TEST(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
121TEST(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
168TEST(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
200TEST(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