internal/ceres/graph_algorithms_test.cc

   1 // Ceres Solver - A fast non-linear least squares minimizer
   2 // Copyright 2015 Google Inc. All rights reserved.
   3 // http://ceres-solver.org/
   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
  40 namespace ceres {
  41 namespace internal {
  42
  43 using std::vector;
  44
  45 TEST(IndependentSetOrdering, Chain) {
  46   Graph<int> graph;
  47   graph.AddVertex(0);
  48   graph.AddVertex(1);
  49   graph.AddVertex(2);
  50   graph.AddVertex(3);
  51   graph.AddVertex(4);
  52
  53   graph.AddEdge(0, 1);
  54   graph.AddEdge(1, 2);
  55   graph.AddEdge(2, 3);
  56   graph.AddEdge(3, 4);
  57
  58   // 0-1-2-3-4
  59   // 0, 2, 4 should be in the independent set.
  60   vector<int> ordering;
  61   int independent_set_size = IndependentSetOrdering(graph, &ordering);
  62
  63   sort(ordering.begin(), ordering.begin() + 3);
  64   sort(ordering.begin() + 3, ordering.end());
  65
  66   EXPECT_EQ(independent_set_size, 3);
  67   EXPECT_EQ(ordering.size(), 5);
  68   EXPECT_EQ(ordering[0], 0);
  69   EXPECT_EQ(ordering[1], 2);
  70   EXPECT_EQ(ordering[2], 4);
  71   EXPECT_EQ(ordering[3], 1);
  72   EXPECT_EQ(ordering[4], 3);
  73 }
  74
  75 TEST(IndependentSetOrdering, Star) {
  76   Graph<int> graph;
  77   graph.AddVertex(0);
  78   graph.AddVertex(1);
  79   graph.AddVertex(2);
  80   graph.AddVertex(3);
  81   graph.AddVertex(4);
  82
  83   graph.AddEdge(0, 1);
  84   graph.AddEdge(0, 2);
  85   graph.AddEdge(0, 3);
  86   graph.AddEdge(0, 4);
  87
  88   //      1
  89   //      |
  90   //    4-0-2
  91   //      |
  92   //      3
  93   // 1, 2, 3, 4 should be in the independent set.
  94   vector<int> ordering;
  95   int independent_set_size = IndependentSetOrdering(graph, &ordering);
  96   EXPECT_EQ(independent_set_size, 4);
  97   EXPECT_EQ(ordering.size(), 5);
  98   EXPECT_EQ(ordering[4], 0);
  99   sort(ordering.begin(), ordering.begin() + 4);
 100   EXPECT_EQ(ordering[0], 1);
 101   EXPECT_EQ(ordering[1], 2);
 102   EXPECT_EQ(ordering[2], 3);
 103   EXPECT_EQ(ordering[3], 4);
 104 }
 105
 106 TEST(Degree2MaximumSpanningForest, PreserveWeights) {
 107   WeightedGraph<int> graph;
 108   graph.AddVertex(0, 1.0);
 109   graph.AddVertex(1, 2.0);
 110   graph.AddEdge(0, 1, 0.5);
 111   graph.AddEdge(1, 0, 0.5);
 112
 113   scoped_ptr<WeightedGraph<int> > forest(Degree2MaximumSpanningForest(graph));
 114
 115   const HashSet<int>& vertices = forest->vertices();
 116   EXPECT_EQ(vertices.size(), 2);
 117   EXPECT_EQ(forest->VertexWeight(0), 1.0);
 118   EXPECT_EQ(forest->VertexWeight(1), 2.0);
 119   EXPECT_EQ(forest->Neighbors(0).size(), 1.0);
 120   EXPECT_EQ(forest->EdgeWeight(0, 1), 0.5);
 121 }
 122
 123 TEST(Degree2MaximumSpanningForest, StarGraph) {
 124   WeightedGraph<int> graph;
 125   graph.AddVertex(0);
 126   graph.AddVertex(1);
 127   graph.AddVertex(2);
 128   graph.AddVertex(3);
 129   graph.AddVertex(4);
 130
 131   graph.AddEdge(0, 1, 1.0);
 132   graph.AddEdge(0, 2, 2.0);
 133   graph.AddEdge(0, 3, 3.0);
 134   graph.AddEdge(0, 4, 4.0);
 135
 136   scoped_ptr<WeightedGraph<int> > forest(Degree2MaximumSpanningForest(graph));
 137   const HashSet<int>& vertices = forest->vertices();
 138   EXPECT_EQ(vertices.size(), 5);
 139
 140   {
 141     const HashSet<int>& neighbors = forest->Neighbors(0);
 142     EXPECT_EQ(neighbors.size(), 2);
 143     EXPECT_TRUE(neighbors.find(4) != neighbors.end());
 144     EXPECT_TRUE(neighbors.find(3) != neighbors.end());
 145   }
 146
 147   {
 148     const HashSet<int>& neighbors = forest->Neighbors(3);
 149     EXPECT_EQ(neighbors.size(), 1);
 150     EXPECT_TRUE(neighbors.find(0) != neighbors.end());
 151   }
 152
 153   {
 154     const HashSet<int>& neighbors = forest->Neighbors(4);
 155     EXPECT_EQ(neighbors.size(), 1);
 156     EXPECT_TRUE(neighbors.find(0) != neighbors.end());
 157   }
 158
 159   {
 160     const HashSet<int>& neighbors = forest->Neighbors(1);
 161     EXPECT_EQ(neighbors.size(), 0);
 162   }
 163
 164   {
 165     const HashSet<int>& neighbors = forest->Neighbors(2);
 166     EXPECT_EQ(neighbors.size(), 0);
 167   }
 168 }
 169
 170 TEST(VertexTotalOrdering, TotalOrdering) {
 171   Graph<int> graph;
 172   graph.AddVertex(0);
 173   graph.AddVertex(1);
 174   graph.AddVertex(2);
 175   graph.AddVertex(3);
 176
 177   // 0-1
 178   //   |
 179   // 2-3
 180   // 0,1 and 2 have degree 1 and 3 has degree 2.
 181   graph.AddEdge(0, 1);
 182   graph.AddEdge(2, 3);
 183   VertexTotalOrdering<int> less_than(graph);
 184
 185   for (int i = 0; i < 4; ++i) {
 186     EXPECT_FALSE(less_than(i, i)) << "Failing vertex: " << i;
 187     for (int j = 0; j < 4; ++j) {
 188       if (i != j) {
 189         EXPECT_TRUE(less_than(i, j) ^ less_than(j, i))
 190             << "Failing vertex pair: " << i << " " << j;
 191       }
 192     }
 193   }
 194
 195   for (int i = 0; i < 3; ++i) {
 196     EXPECT_TRUE(less_than(i, 3));
 197     EXPECT_FALSE(less_than(3, i));
 198   }
 199 }
 200
 201
 202 TEST(StableIndependentSet, BreakTies) {
 203   Graph<int> graph;
 204   graph.AddVertex(0);
 205   graph.AddVertex(1);
 206   graph.AddVertex(2);
 207   graph.AddVertex(3);
 208
 209   graph.AddEdge(0, 1);
 210   graph.AddEdge(0, 2);
 211   graph.AddEdge(0, 3);
 212   graph.AddEdge(1, 2);
 213   graph.AddEdge(1, 3);
 214   graph.AddEdge(2, 3);
 215
 216   // Since this is a completely connected graph, the independent set
 217   // contains exactly one vertex. StableIndependentSetOrdering
 218   // guarantees that it will always be the first vertex in the
 219   // ordering vector.
 220   {
 221     vector<int> ordering;
 222     ordering.push_back(0);
 223     ordering.push_back(1);
 224     ordering.push_back(2);
 225     ordering.push_back(3);
 226     const int independent_set_size =
 227         StableIndependentSetOrdering(graph, &ordering);
 228     EXPECT_EQ(independent_set_size, 1);
 229     EXPECT_EQ(ordering[0], 0);
 230   }
 231
 232   {
 233     vector<int> ordering;
 234     ordering.push_back(1);
 235     ordering.push_back(0);
 236     ordering.push_back(2);
 237     ordering.push_back(3);
 238     const int independent_set_size =
 239         StableIndependentSetOrdering(graph, &ordering);
 240     EXPECT_EQ(independent_set_size, 1);
 241     EXPECT_EQ(ordering[0], 1);
 242   }
 243 }
 244
 245 }  // namespace internal
 246 }  // namespace ceres