tarjan_unittest.cc revision 161c4a132743f15fc4757112b673085c2a7a7f29
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 "update_engine/payload_generator/tarjan.h" 6 7#include <utility> 8 9#include <base/logging.h> 10#include <gtest/gtest.h> 11 12#include "update_engine/payload_generator/graph_types.h" 13#include "update_engine/utils.h" 14 15using std::make_pair; 16using std::pair; 17using std::set; 18using std::string; 19using std::vector; 20 21namespace chromeos_update_engine { 22 23class TarjanAlgorithmTest : public ::testing::Test {}; 24 25TEST(TarjanAlgorithmTest, SimpleTest) { 26 const Vertex::Index n_a = 0; 27 const Vertex::Index n_b = 1; 28 const Vertex::Index n_c = 2; 29 const Vertex::Index n_d = 3; 30 const Vertex::Index n_e = 4; 31 const Vertex::Index n_f = 5; 32 const Vertex::Index n_g = 6; 33 const Vertex::Index n_h = 7; 34 const Graph::size_type kNodeCount = 8; 35 36 Graph graph(kNodeCount); 37 38 graph[n_a].out_edges.insert(make_pair(n_e, EdgeProperties())); 39 graph[n_a].out_edges.insert(make_pair(n_f, EdgeProperties())); 40 graph[n_b].out_edges.insert(make_pair(n_a, EdgeProperties())); 41 graph[n_c].out_edges.insert(make_pair(n_d, EdgeProperties())); 42 graph[n_d].out_edges.insert(make_pair(n_e, EdgeProperties())); 43 graph[n_d].out_edges.insert(make_pair(n_f, EdgeProperties())); 44 graph[n_e].out_edges.insert(make_pair(n_b, EdgeProperties())); 45 graph[n_e].out_edges.insert(make_pair(n_c, EdgeProperties())); 46 graph[n_e].out_edges.insert(make_pair(n_f, EdgeProperties())); 47 graph[n_f].out_edges.insert(make_pair(n_g, EdgeProperties())); 48 graph[n_g].out_edges.insert(make_pair(n_h, EdgeProperties())); 49 graph[n_h].out_edges.insert(make_pair(n_g, EdgeProperties())); 50 51 TarjanAlgorithm tarjan; 52 53 for (Vertex::Index i = n_a; i <= n_e; i++) { 54 vector<Vertex::Index> vertex_indexes; 55 tarjan.Execute(i, &graph, &vertex_indexes); 56 57 EXPECT_EQ(5, vertex_indexes.size()); 58 EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_a)); 59 EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_b)); 60 EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_c)); 61 EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_d)); 62 EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_e)); 63 } 64 65 { 66 vector<Vertex::Index> vertex_indexes; 67 tarjan.Execute(n_f, &graph, &vertex_indexes); 68 69 EXPECT_EQ(1, vertex_indexes.size()); 70 EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_f)); 71 } 72 73 for (Vertex::Index i = n_g; i <= n_h; i++) { 74 vector<Vertex::Index> vertex_indexes; 75 tarjan.Execute(i, &graph, &vertex_indexes); 76 77 EXPECT_EQ(2, vertex_indexes.size()); 78 EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_g)); 79 EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_h)); 80 } 81} 82 83} // namespace chromeos_update_engine 84