blob: 6c86668f12d01d78bdd8772ca8cfedc70b9b8fae [file] [log] [blame]
// Ceres Solver - A fast non-linear least squares minimizer
// Copyright 2023 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 <vector>
#include "ceres/graph.h"
#include "ceres/internal/export.h"
#include "gtest/gtest.h"
namespace ceres::internal {
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.
std::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.
std::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.
{
std::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);
}
{
std::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 ceres::internal