10ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Ceres Solver - A fast non-linear least squares minimizer 20ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Copyright 2010, 2011, 2012 Google Inc. All rights reserved. 30ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// http://code.google.com/p/ceres-solver/ 40ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 50ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Redistribution and use in source and binary forms, with or without 60ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// modification, are permitted provided that the following conditions are met: 70ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 80ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// * Redistributions of source code must retain the above copyright notice, 90ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// this list of conditions and the following disclaimer. 100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// * Redistributions in binary form must reproduce the above copyright notice, 110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// this list of conditions and the following disclaimer in the documentation 120ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// and/or other materials provided with the distribution. 130ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// * Neither the name of Google Inc. nor the names of its contributors may be 140ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// used to endorse or promote products derived from this software without 150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// specific prior written permission. 160ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 170ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 210ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 220ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 240ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// POSSIBILITY OF SUCH DAMAGE. 280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Author: sameeragarwal@google.com (Sameer Agarwal) 300ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 310ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/graph_algorithms.h" 320ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 330ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include <algorithm> 340ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "gtest/gtest.h" 350ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/collections_port.h" 360ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/graph.h" 370ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/internal/port.h" 380ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/internal/scoped_ptr.h" 390ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 400ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongnamespace ceres { 410ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongnamespace internal { 420ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 430ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus KongTEST(IndependentSetOrdering, Chain) { 440ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong Graph<int> graph; 450ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddVertex(0); 460ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddVertex(1); 470ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddVertex(2); 480ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddVertex(3); 490ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddVertex(4); 500ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 510ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddEdge(0, 1); 520ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddEdge(1, 2); 530ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddEdge(2, 3); 540ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddEdge(3, 4); 550ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 560ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 0-1-2-3-4 570ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 0, 2, 4 should be in the independent set. 580ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong vector<int> ordering; 590ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int independent_set_size = IndependentSetOrdering(graph, &ordering); 600ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 610ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong sort(ordering.begin(), ordering.begin() + 3); 620ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong sort(ordering.begin() + 3, ordering.end()); 630ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 640ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_EQ(independent_set_size, 3); 650ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_EQ(ordering.size(), 5); 660ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_EQ(ordering[0], 0); 670ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_EQ(ordering[1], 2); 680ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_EQ(ordering[2], 4); 690ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_EQ(ordering[3], 1); 700ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_EQ(ordering[4], 3); 710ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} 720ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 730ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus KongTEST(IndependentSetOrdering, Star) { 740ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong Graph<int> graph; 750ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddVertex(0); 760ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddVertex(1); 770ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddVertex(2); 780ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddVertex(3); 790ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddVertex(4); 800ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 810ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddEdge(0, 1); 820ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddEdge(0, 2); 830ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddEdge(0, 3); 840ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddEdge(0, 4); 850ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 860ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 1 870ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // | 880ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 4-0-2 890ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // | 900ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 3 910ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 1, 2, 3, 4 should be in the indepdendent set. 920ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong vector<int> ordering; 930ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int independent_set_size = IndependentSetOrdering(graph, &ordering); 940ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_EQ(independent_set_size, 4); 950ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_EQ(ordering.size(), 5); 960ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_EQ(ordering[4], 0); 970ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong sort(ordering.begin(), ordering.begin() + 4); 980ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_EQ(ordering[0], 1); 990ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_EQ(ordering[1], 2); 1000ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_EQ(ordering[2], 3); 1010ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_EQ(ordering[3], 4); 1020ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} 1030ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1040ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus KongTEST(Degree2MaximumSpanningForest, PreserveWeights) { 1050ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong Graph<int> graph; 1060ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddVertex(0, 1.0); 1070ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddVertex(1, 2.0); 1080ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddEdge(0, 1, 0.5); 1090ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddEdge(1, 0, 0.5); 1100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong scoped_ptr<Graph<int> > forest(Degree2MaximumSpanningForest(graph)); 1120ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1130ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const HashSet<int>& vertices = forest->vertices(); 1140ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_EQ(vertices.size(), 2); 1150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_EQ(forest->VertexWeight(0), 1.0); 1160ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_EQ(forest->VertexWeight(1), 2.0); 1170ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_EQ(forest->Neighbors(0).size(), 1.0); 1180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_EQ(forest->EdgeWeight(0, 1), 0.5); 1190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} 1200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1210ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus KongTEST(Degree2MaximumSpanningForest, StarGraph) { 1220ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong Graph<int> graph; 1230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddVertex(0); 1240ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddVertex(1); 1250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddVertex(2); 1260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddVertex(3); 1270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddVertex(4); 1280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddEdge(0, 1, 1.0); 1300ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddEdge(0, 2, 2.0); 1310ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddEdge(0, 3, 3.0); 1320ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddEdge(0, 4, 4.0); 1330ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1340ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong scoped_ptr<Graph<int> > forest(Degree2MaximumSpanningForest(graph)); 1350ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const HashSet<int>& vertices = forest->vertices(); 1360ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_EQ(vertices.size(), 5); 1370ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1380ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong { 1390ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const HashSet<int>& neighbors = forest->Neighbors(0); 1400ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_EQ(neighbors.size(), 2); 1410ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_TRUE(neighbors.find(4) != neighbors.end()); 1420ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_TRUE(neighbors.find(3) != neighbors.end()); 1430ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 1440ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1450ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong { 1460ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const HashSet<int>& neighbors = forest->Neighbors(3); 1470ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_EQ(neighbors.size(), 1); 1480ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_TRUE(neighbors.find(0) != neighbors.end()); 1490ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 1500ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1510ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong { 1520ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const HashSet<int>& neighbors = forest->Neighbors(4); 1530ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_EQ(neighbors.size(), 1); 1540ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_TRUE(neighbors.find(0) != neighbors.end()); 1550ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 1560ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1570ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong { 1580ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const HashSet<int>& neighbors = forest->Neighbors(1); 1590ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_EQ(neighbors.size(), 0); 1600ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 1610ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1620ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong { 1630ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong const HashSet<int>& neighbors = forest->Neighbors(2); 1640ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_EQ(neighbors.size(), 0); 1650ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 1660ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} 1670ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1681d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha HaeberlingTEST(VertexTotalOrdering, TotalOrdering) { 1690ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong Graph<int> graph; 1700ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddVertex(0); 1710ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddVertex(1); 1720ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddVertex(2); 1730ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddVertex(3); 1740ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1750ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 0-1 1760ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // | 1770ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 2-3 1780ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 0,1 and 2 have degree 1 and 3 has degree 2. 1790ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddEdge(0, 1, 1.0); 1800ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong graph.AddEdge(2, 3, 1.0); 1811d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling VertexTotalOrdering<int> less_than(graph); 1820ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1830ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong for (int i = 0; i < 4; ++i) { 1841d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling EXPECT_FALSE(less_than(i, i)) << "Failing vertex: " << i; 1850ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong for (int j = 0; j < 4; ++j) { 1860ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong if (i != j) { 1870ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_TRUE(less_than(i, j) ^ less_than(j, i)) 1880ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong << "Failing vertex pair: " << i << " " << j; 1890ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 1900ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 1910ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 1920ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1930ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong for (int i = 0; i < 3; ++i) { 1940ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_TRUE(less_than(i, 3)); 1950ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong EXPECT_FALSE(less_than(3, i)); 1960ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 1970ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} 1980ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1991d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2001d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha HaeberlingTEST(StableIndependentSet, BreakTies) { 2011d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling Graph<int> graph; 2021d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling graph.AddVertex(0); 2031d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling graph.AddVertex(1); 2041d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling graph.AddVertex(2); 2051d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling graph.AddVertex(3); 2061d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2071d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling graph.AddEdge(0, 1); 2081d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling graph.AddEdge(0, 2); 2091d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling graph.AddEdge(0, 3); 2101d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling graph.AddEdge(1, 2); 2111d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling graph.AddEdge(1, 3); 2121d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling graph.AddEdge(2, 3); 2131d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2141d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // Since this is a completely connected graph, the independent set 2151d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // contains exactly one vertex. StableIndependentSetOrdering 2161d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // guarantees that it will always be the first vertex in the 2171d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling // ordering vector. 2181d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling { 2191d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling vector<int> ordering; 2201d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ordering.push_back(0); 2211d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ordering.push_back(1); 2221d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ordering.push_back(2); 2231d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ordering.push_back(3); 2241d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const int independent_set_size = 2251d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling StableIndependentSetOrdering(graph, &ordering); 2261d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling EXPECT_EQ(independent_set_size, 1); 2271d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling EXPECT_EQ(ordering[0], 0); 2281d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 2291d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2301d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling { 2311d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling vector<int> ordering; 2321d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ordering.push_back(1); 2331d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ordering.push_back(0); 2341d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ordering.push_back(2); 2351d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling ordering.push_back(3); 2361d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling const int independent_set_size = 2371d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling StableIndependentSetOrdering(graph, &ordering); 2381d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling EXPECT_EQ(independent_set_size, 1); 2391d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling EXPECT_EQ(ordering[0], 1); 2401d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling } 2411d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling 2421d2624a10e2c559f8ba9ef89eaa30832c0a83a96Sascha Haeberling} 2430ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} // namespace internal 2440ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} // namespace ceres 245