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