1 // 2 // Copyright (C) 2010 The Android Open Source Project 3 // 4 // Licensed under the Apache License, Version 2.0 (the "License"); 5 // you may not use this file except in compliance with the License. 6 // You may obtain a copy of the License at 7 // 8 // http://www.apache.org/licenses/LICENSE-2.0 9 // 10 // Unless required by applicable law or agreed to in writing, software 11 // distributed under the License is distributed on an "AS IS" BASIS, 12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 // See the License for the specific language governing permissions and 14 // limitations under the License. 15 // 16 17 #include "update_engine/payload_generator/tarjan.h" 18 19 #include <string> 20 #include <utility> 21 22 #include <base/logging.h> 23 #include <gtest/gtest.h> 24 25 #include "update_engine/common/utils.h" 26 #include "update_engine/payload_generator/graph_types.h" 27 28 using std::make_pair; 29 using std::string; 30 using std::vector; 31 32 namespace chromeos_update_engine { 33 34 class TarjanAlgorithmTest : public ::testing::Test {}; 35 36 TEST(TarjanAlgorithmTest, SimpleTest) { 37 const Vertex::Index n_a = 0; 38 const Vertex::Index n_b = 1; 39 const Vertex::Index n_c = 2; 40 const Vertex::Index n_d = 3; 41 const Vertex::Index n_e = 4; 42 const Vertex::Index n_f = 5; 43 const Vertex::Index n_g = 6; 44 const Vertex::Index n_h = 7; 45 const Graph::size_type kNodeCount = 8; 46 47 Graph graph(kNodeCount); 48 49 graph[n_a].out_edges.insert(make_pair(n_e, EdgeProperties())); 50 graph[n_a].out_edges.insert(make_pair(n_f, EdgeProperties())); 51 graph[n_b].out_edges.insert(make_pair(n_a, EdgeProperties())); 52 graph[n_c].out_edges.insert(make_pair(n_d, EdgeProperties())); 53 graph[n_d].out_edges.insert(make_pair(n_e, EdgeProperties())); 54 graph[n_d].out_edges.insert(make_pair(n_f, EdgeProperties())); 55 graph[n_e].out_edges.insert(make_pair(n_b, EdgeProperties())); 56 graph[n_e].out_edges.insert(make_pair(n_c, EdgeProperties())); 57 graph[n_e].out_edges.insert(make_pair(n_f, EdgeProperties())); 58 graph[n_f].out_edges.insert(make_pair(n_g, EdgeProperties())); 59 graph[n_g].out_edges.insert(make_pair(n_h, EdgeProperties())); 60 graph[n_h].out_edges.insert(make_pair(n_g, EdgeProperties())); 61 62 TarjanAlgorithm tarjan; 63 64 for (Vertex::Index i = n_a; i <= n_e; i++) { 65 vector<Vertex::Index> vertex_indexes; 66 tarjan.Execute(i, &graph, &vertex_indexes); 67 68 EXPECT_EQ(5U, vertex_indexes.size()); 69 EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_a)); 70 EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_b)); 71 EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_c)); 72 EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_d)); 73 EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_e)); 74 } 75 76 { 77 vector<Vertex::Index> vertex_indexes; 78 tarjan.Execute(n_f, &graph, &vertex_indexes); 79 80 EXPECT_EQ(1U, vertex_indexes.size()); 81 EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_f)); 82 } 83 84 for (Vertex::Index i = n_g; i <= n_h; i++) { 85 vector<Vertex::Index> vertex_indexes; 86 tarjan.Execute(i, &graph, &vertex_indexes); 87 88 EXPECT_EQ(2U, vertex_indexes.size()); 89 EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_g)); 90 EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_h)); 91 } 92 } 93 94 } // namespace chromeos_update_engine 95
