| // 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 |