Squashed 'third_party/ceres/' content from commit e51e9b4
Change-Id: I763587619d57e594d3fa158dc3a7fe0b89a1743b
git-subtree-dir: third_party/ceres
git-subtree-split: e51e9b46f6ca88ab8b2266d0e362771db6d98067
diff --git a/internal/ceres/graph_algorithms_test.cc b/internal/ceres/graph_algorithms_test.cc
new file mode 100644
index 0000000..2aef327
--- /dev/null
+++ b/internal/ceres/graph_algorithms_test.cc
@@ -0,0 +1,248 @@
+// Ceres Solver - A fast non-linear least squares minimizer
+// Copyright 2015 Google Inc. All rights reserved.
+// http://ceres-solver.org/
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//
+// * Redistributions of source code must retain the above copyright notice,
+// this list of conditions and the following disclaimer.
+// * Redistributions in binary form must reproduce the above copyright notice,
+// this list of conditions and the following disclaimer in the documentation
+// and/or other materials provided with the distribution.
+// * Neither the name of Google Inc. nor the names of its contributors may be
+// used to endorse or promote products derived from this software without
+// specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+// POSSIBILITY OF SUCH DAMAGE.
+//
+// Author: sameeragarwal@google.com (Sameer Agarwal)
+
+#include "ceres/graph_algorithms.h"
+
+#include <algorithm>
+#include <memory>
+#include <unordered_set>
+
+#include "ceres/graph.h"
+#include "ceres/internal/port.h"
+#include "gtest/gtest.h"
+
+namespace ceres {
+namespace internal {
+
+using std::vector;
+
+TEST(IndependentSetOrdering, Chain) {
+ Graph<int> graph;
+ graph.AddVertex(0);
+ graph.AddVertex(1);
+ graph.AddVertex(2);
+ graph.AddVertex(3);
+ graph.AddVertex(4);
+
+ graph.AddEdge(0, 1);
+ graph.AddEdge(1, 2);
+ graph.AddEdge(2, 3);
+ graph.AddEdge(3, 4);
+
+ // 0-1-2-3-4
+ // 0, 2, 4 should be in the independent set.
+ vector<int> ordering;
+ int independent_set_size = IndependentSetOrdering(graph, &ordering);
+
+ sort(ordering.begin(), ordering.begin() + 3);
+ sort(ordering.begin() + 3, ordering.end());
+
+ EXPECT_EQ(independent_set_size, 3);
+ EXPECT_EQ(ordering.size(), 5);
+ EXPECT_EQ(ordering[0], 0);
+ EXPECT_EQ(ordering[1], 2);
+ EXPECT_EQ(ordering[2], 4);
+ EXPECT_EQ(ordering[3], 1);
+ EXPECT_EQ(ordering[4], 3);
+}
+
+TEST(IndependentSetOrdering, Star) {
+ Graph<int> graph;
+ graph.AddVertex(0);
+ graph.AddVertex(1);
+ graph.AddVertex(2);
+ graph.AddVertex(3);
+ graph.AddVertex(4);
+
+ graph.AddEdge(0, 1);
+ graph.AddEdge(0, 2);
+ graph.AddEdge(0, 3);
+ graph.AddEdge(0, 4);
+
+ // 1
+ // |
+ // 4-0-2
+ // |
+ // 3
+ // 1, 2, 3, 4 should be in the independent set.
+ vector<int> ordering;
+ int independent_set_size = IndependentSetOrdering(graph, &ordering);
+ EXPECT_EQ(independent_set_size, 4);
+ EXPECT_EQ(ordering.size(), 5);
+ EXPECT_EQ(ordering[4], 0);
+ sort(ordering.begin(), ordering.begin() + 4);
+ EXPECT_EQ(ordering[0], 1);
+ EXPECT_EQ(ordering[1], 2);
+ EXPECT_EQ(ordering[2], 3);
+ EXPECT_EQ(ordering[3], 4);
+}
+
+TEST(Degree2MaximumSpanningForest, PreserveWeights) {
+ WeightedGraph<int> graph;
+ graph.AddVertex(0, 1.0);
+ graph.AddVertex(1, 2.0);
+ graph.AddEdge(0, 1, 0.5);
+ graph.AddEdge(1, 0, 0.5);
+
+ std::unique_ptr<WeightedGraph<int> > forest(
+ Degree2MaximumSpanningForest(graph));
+
+ const std::unordered_set<int>& vertices = forest->vertices();
+ EXPECT_EQ(vertices.size(), 2);
+ EXPECT_EQ(forest->VertexWeight(0), 1.0);
+ EXPECT_EQ(forest->VertexWeight(1), 2.0);
+ EXPECT_EQ(forest->Neighbors(0).size(), 1.0);
+ EXPECT_EQ(forest->EdgeWeight(0, 1), 0.5);
+}
+
+TEST(Degree2MaximumSpanningForest, StarGraph) {
+ WeightedGraph<int> graph;
+ graph.AddVertex(0);
+ graph.AddVertex(1);
+ graph.AddVertex(2);
+ graph.AddVertex(3);
+ graph.AddVertex(4);
+
+ graph.AddEdge(0, 1, 1.0);
+ graph.AddEdge(0, 2, 2.0);
+ graph.AddEdge(0, 3, 3.0);
+ graph.AddEdge(0, 4, 4.0);
+
+ std::unique_ptr<WeightedGraph<int> > forest(Degree2MaximumSpanningForest(graph));
+ const std::unordered_set<int>& vertices = forest->vertices();
+ EXPECT_EQ(vertices.size(), 5);
+
+ {
+ const std::unordered_set<int>& neighbors = forest->Neighbors(0);
+ EXPECT_EQ(neighbors.size(), 2);
+ EXPECT_TRUE(neighbors.find(4) != neighbors.end());
+ EXPECT_TRUE(neighbors.find(3) != neighbors.end());
+ }
+
+ {
+ const std::unordered_set<int>& neighbors = forest->Neighbors(3);
+ EXPECT_EQ(neighbors.size(), 1);
+ EXPECT_TRUE(neighbors.find(0) != neighbors.end());
+ }
+
+ {
+ const std::unordered_set<int>& neighbors = forest->Neighbors(4);
+ EXPECT_EQ(neighbors.size(), 1);
+ EXPECT_TRUE(neighbors.find(0) != neighbors.end());
+ }
+
+ {
+ const std::unordered_set<int>& neighbors = forest->Neighbors(1);
+ EXPECT_EQ(neighbors.size(), 0);
+ }
+
+ {
+ const std::unordered_set<int>& neighbors = forest->Neighbors(2);
+ EXPECT_EQ(neighbors.size(), 0);
+ }
+}
+
+TEST(VertexTotalOrdering, TotalOrdering) {
+ Graph<int> graph;
+ graph.AddVertex(0);
+ graph.AddVertex(1);
+ graph.AddVertex(2);
+ graph.AddVertex(3);
+
+ // 0-1
+ // |
+ // 2-3
+ // 0,1 and 2 have degree 1 and 3 has degree 2.
+ graph.AddEdge(0, 1);
+ graph.AddEdge(2, 3);
+ VertexTotalOrdering<int> less_than(graph);
+
+ for (int i = 0; i < 4; ++i) {
+ EXPECT_FALSE(less_than(i, i)) << "Failing vertex: " << i;
+ for (int j = 0; j < 4; ++j) {
+ if (i != j) {
+ EXPECT_TRUE(less_than(i, j) ^ less_than(j, i))
+ << "Failing vertex pair: " << i << " " << j;
+ }
+ }
+ }
+
+ for (int i = 0; i < 3; ++i) {
+ EXPECT_TRUE(less_than(i, 3));
+ EXPECT_FALSE(less_than(3, i));
+ }
+}
+
+
+TEST(StableIndependentSet, BreakTies) {
+ Graph<int> graph;
+ graph.AddVertex(0);
+ graph.AddVertex(1);
+ graph.AddVertex(2);
+ graph.AddVertex(3);
+
+ graph.AddEdge(0, 1);
+ graph.AddEdge(0, 2);
+ graph.AddEdge(0, 3);
+ graph.AddEdge(1, 2);
+ graph.AddEdge(1, 3);
+ graph.AddEdge(2, 3);
+
+ // Since this is a completely connected graph, the independent set
+ // contains exactly one vertex. StableIndependentSetOrdering
+ // guarantees that it will always be the first vertex in the
+ // ordering vector.
+ {
+ vector<int> ordering;
+ ordering.push_back(0);
+ ordering.push_back(1);
+ ordering.push_back(2);
+ ordering.push_back(3);
+ const int independent_set_size =
+ StableIndependentSetOrdering(graph, &ordering);
+ EXPECT_EQ(independent_set_size, 1);
+ EXPECT_EQ(ordering[0], 0);
+ }
+
+ {
+ vector<int> ordering;
+ ordering.push_back(1);
+ ordering.push_back(0);
+ ordering.push_back(2);
+ ordering.push_back(3);
+ const int independent_set_size =
+ StableIndependentSetOrdering(graph, &ordering);
+ EXPECT_EQ(independent_set_size, 1);
+ EXPECT_EQ(ordering[0], 1);
+ }
+}
+
+} // namespace internal
+} // namespace ceres