OLD | NEW |
(Empty) | |
| 1 // Copyright (c) 2010 The Chromium OS Authors. All rights reserved. |
| 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. |
| 4 |
| 5 #include <utility> |
| 6 #include <gtest/gtest.h> |
| 7 #include "chromeos/obsolete_logging.h" |
| 8 #include "update_engine/graph_types.h" |
| 9 #include "update_engine/tarjan.h" |
| 10 #include "update_engine/utils.h" |
| 11 |
| 12 using std::make_pair; |
| 13 using std::pair; |
| 14 using std::set; |
| 15 using std::string; |
| 16 using std::vector; |
| 17 |
| 18 namespace chromeos_update_engine { |
| 19 |
| 20 class TarjanAlgorithmTest : public ::testing::Test {}; |
| 21 |
| 22 TEST(TarjanAlgorithmTest, SimpleTest) { |
| 23 const Vertex::Index n_a = 0; |
| 24 const Vertex::Index n_b = 1; |
| 25 const Vertex::Index n_c = 2; |
| 26 const Vertex::Index n_d = 3; |
| 27 const Vertex::Index n_e = 4; |
| 28 const Vertex::Index n_f = 5; |
| 29 const Vertex::Index n_g = 6; |
| 30 const Vertex::Index n_h = 7; |
| 31 const Graph::size_type kNodeCount = 8; |
| 32 |
| 33 Graph graph(kNodeCount); |
| 34 |
| 35 graph[n_a].out_edges.insert(make_pair(n_e, EdgeProperties())); |
| 36 graph[n_a].out_edges.insert(make_pair(n_f, EdgeProperties())); |
| 37 graph[n_b].out_edges.insert(make_pair(n_a, EdgeProperties())); |
| 38 graph[n_c].out_edges.insert(make_pair(n_d, EdgeProperties())); |
| 39 graph[n_d].out_edges.insert(make_pair(n_e, EdgeProperties())); |
| 40 graph[n_d].out_edges.insert(make_pair(n_f, EdgeProperties())); |
| 41 graph[n_e].out_edges.insert(make_pair(n_b, EdgeProperties())); |
| 42 graph[n_e].out_edges.insert(make_pair(n_c, EdgeProperties())); |
| 43 graph[n_e].out_edges.insert(make_pair(n_f, EdgeProperties())); |
| 44 graph[n_f].out_edges.insert(make_pair(n_g, EdgeProperties())); |
| 45 graph[n_g].out_edges.insert(make_pair(n_h, EdgeProperties())); |
| 46 graph[n_h].out_edges.insert(make_pair(n_g, EdgeProperties())); |
| 47 |
| 48 TarjanAlgorithm tarjan; |
| 49 |
| 50 for (Vertex::Index i = n_a; i <= n_e; i++) { |
| 51 vector<Vertex::Index> vertex_indexes; |
| 52 tarjan.Execute(i, &graph, &vertex_indexes); |
| 53 |
| 54 EXPECT_EQ(5, vertex_indexes.size()); |
| 55 EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_a)); |
| 56 EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_b)); |
| 57 EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_c)); |
| 58 EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_d)); |
| 59 EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_e)); |
| 60 } |
| 61 |
| 62 { |
| 63 vector<Vertex::Index> vertex_indexes; |
| 64 tarjan.Execute(n_f, &graph, &vertex_indexes); |
| 65 |
| 66 EXPECT_EQ(1, vertex_indexes.size()); |
| 67 EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_f)); |
| 68 } |
| 69 |
| 70 for (Vertex::Index i = n_g; i <= n_h; i++) { |
| 71 vector<Vertex::Index> vertex_indexes; |
| 72 tarjan.Execute(i, &graph, &vertex_indexes); |
| 73 |
| 74 EXPECT_EQ(2, vertex_indexes.size()); |
| 75 EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_g)); |
| 76 EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_h)); |
| 77 } |
| 78 } |
| 79 |
| 80 } // namespace chromeos_update_engine |
OLD | NEW |