internal/ceres/graph_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.h"
  32
  33 #include "gtest/gtest.h"
  34 #include "ceres/collections_port.h"
  35 #include "ceres/internal/scoped_ptr.h"
  36
  37 namespace ceres {
  38 namespace internal {
  39
  40 TEST(Graph, EmptyGraph) {
  41   Graph<int> graph;
  42   EXPECT_EQ(graph.vertices().size(), 0);
  43 }
  44
  45 TEST(Graph, AddVertexAndEdge) {
  46   Graph<int> graph;
  47   graph.AddVertex(0);
  48   graph.AddVertex(1);
  49   graph.AddEdge(0, 1);
  50
  51   const HashSet<int>& vertices = graph.vertices();
  52   EXPECT_EQ(vertices.size(), 2);
  53   EXPECT_EQ(graph.Neighbors(0).size(), 1);
  54   EXPECT_EQ(graph.Neighbors(1).size(), 1);
  55 }
  56
  57 TEST(Graph, AddVertexIdempotence) {
  58   Graph<int> graph;
  59   graph.AddVertex(0);
  60   graph.AddVertex(1);
  61   graph.AddEdge(0, 1);
  62
  63   const HashSet<int>& vertices = graph.vertices();
  64
  65   EXPECT_EQ(vertices.size(), 2);
  66
  67   // Try adding the vertex again with a new weight.
  68   graph.AddVertex(0);
  69   EXPECT_EQ(vertices.size(), 2);
  70
  71   // Rest of the graph remains the same.
  72   EXPECT_EQ(graph.Neighbors(0).size(), 1);
  73   EXPECT_EQ(graph.Neighbors(1).size(), 1);
  74 }
  75
  76 TEST(Graph, DieOnNonExistentVertex) {
  77   Graph<int> graph;
  78   graph.AddVertex(0);
  79   graph.AddVertex(1);
  80   graph.AddEdge(0, 1);
  81
  82   EXPECT_DEATH_IF_SUPPORTED(graph.Neighbors(2), "key not found");
  83 }
  84
  85 TEST(WeightedGraph, EmptyGraph) {
  86   WeightedGraph<int> graph;
  87   EXPECT_EQ(graph.vertices().size(), 0);
  88 }
  89
  90 TEST(WeightedGraph, AddVertexAndEdge) {
  91   WeightedGraph<int> graph;
  92   graph.AddVertex(0, 1.0);
  93   graph.AddVertex(1, 2.0);
  94   graph.AddEdge(0, 1, 0.5);
  95
  96   const HashSet<int>& vertices = graph.vertices();
  97   EXPECT_EQ(vertices.size(), 2);
  98   EXPECT_EQ(graph.VertexWeight(0), 1.0);
  99   EXPECT_EQ(graph.VertexWeight(1), 2.0);
 100   EXPECT_EQ(graph.Neighbors(0).size(), 1);
 101   EXPECT_EQ(graph.Neighbors(1).size(), 1);
 102   EXPECT_EQ(graph.EdgeWeight(0, 1), 0.5);
 103   EXPECT_EQ(graph.EdgeWeight(1, 0), 0.5);
 104 }
 105
 106 TEST(WeightedGraph, AddVertexIdempotence) {
 107   WeightedGraph<int> graph;
 108   graph.AddVertex(0, 1.0);
 109   graph.AddVertex(1, 2.0);
 110   graph.AddEdge(0, 1, 0.5);
 111
 112   const HashSet<int>& vertices = graph.vertices();
 113
 114   EXPECT_EQ(vertices.size(), 2);
 115
 116   // Try adding the vertex again with a new weight.
 117   graph.AddVertex(0, 3.0);
 118   EXPECT_EQ(vertices.size(), 2);
 119
 120   // The vertex weight is reset.
 121   EXPECT_EQ(graph.VertexWeight(0), 3.0);
 122
 123   // Rest of the graph remains the same.
 124   EXPECT_EQ(graph.VertexWeight(1), 2.0);
 125   EXPECT_EQ(graph.Neighbors(0).size(), 1);
 126   EXPECT_EQ(graph.Neighbors(1).size(), 1);
 127   EXPECT_EQ(graph.EdgeWeight(0, 1), 0.5);
 128   EXPECT_EQ(graph.EdgeWeight(1, 0), 0.5);
 129 }
 130
 131 TEST(WeightedGraph, DieOnNonExistentVertex) {
 132   WeightedGraph<int> graph;
 133   graph.AddVertex(0, 1.0);
 134   graph.AddVertex(1, 2.0);
 135   graph.AddEdge(0, 1, 0.5);
 136
 137   EXPECT_DEATH_IF_SUPPORTED(graph.VertexWeight(2), "key not found");
 138   EXPECT_DEATH_IF_SUPPORTED(graph.Neighbors(2), "key not found");
 139 }
 140
 141 TEST(WeightedGraph, NonExistentEdge) {
 142   WeightedGraph<int> graph;
 143   graph.AddVertex(0, 1.0);
 144   graph.AddVertex(1, 2.0);
 145   graph.AddEdge(0, 1, 0.5);
 146
 147   // Default value for non-existent edges is 0.
 148   EXPECT_EQ(graph.EdgeWeight(2, 3), 0);
 149 }
 150
 151 }  // namespace internal
 152 }  // namespace ceres