topological_sort_unittest.cc revision aab50e31f0b80ed53a9b8d5dbabcf943974bd32c
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/topological_sort.h" 6 7#include <utility> 8#include <vector> 9 10#include <gtest/gtest.h> 11 12#include "update_engine/payload_generator/graph_types.h" 13 14using std::make_pair; 15using std::vector; 16 17namespace chromeos_update_engine { 18 19class TopologicalSortTest : public ::testing::Test {}; 20 21namespace { 22// Returns true if the value is found in vect. If found, the index is stored 23// in out_index if out_index is not null. 24template<typename T> 25bool IndexOf(const vector<T>& vect, 26 const T& value, 27 typename vector<T>::size_type* out_index) { 28 for (typename vector<T>::size_type i = 0; i < vect.size(); i++) { 29 if (vect[i] == value) { 30 if (out_index) { 31 *out_index = i; 32 } 33 return true; 34 } 35 } 36 return false; 37} 38} // namespace 39 40TEST(TopologicalSortTest, SimpleTest) { 41 int counter = 0; 42 const Vertex::Index n_a = counter++; 43 const Vertex::Index n_b = counter++; 44 const Vertex::Index n_c = counter++; 45 const Vertex::Index n_d = counter++; 46 const Vertex::Index n_e = counter++; 47 const Vertex::Index n_f = counter++; 48 const Vertex::Index n_g = counter++; 49 const Vertex::Index n_h = counter++; 50 const Vertex::Index n_i = counter++; 51 const Vertex::Index n_j = counter++; 52 const Graph::size_type kNodeCount = counter++; 53 54 Graph graph(kNodeCount); 55 56 graph[n_i].out_edges.insert(make_pair(n_j, EdgeProperties())); 57 graph[n_i].out_edges.insert(make_pair(n_c, EdgeProperties())); 58 graph[n_i].out_edges.insert(make_pair(n_e, EdgeProperties())); 59 graph[n_i].out_edges.insert(make_pair(n_h, EdgeProperties())); 60 graph[n_c].out_edges.insert(make_pair(n_b, EdgeProperties())); 61 graph[n_b].out_edges.insert(make_pair(n_a, EdgeProperties())); 62 graph[n_e].out_edges.insert(make_pair(n_d, EdgeProperties())); 63 graph[n_e].out_edges.insert(make_pair(n_g, EdgeProperties())); 64 graph[n_g].out_edges.insert(make_pair(n_d, EdgeProperties())); 65 graph[n_g].out_edges.insert(make_pair(n_f, EdgeProperties())); 66 graph[n_d].out_edges.insert(make_pair(n_a, EdgeProperties())); 67 68 vector<Vertex::Index> sorted; 69 TopologicalSort(graph, &sorted); 70 71 for (Vertex::Index i = 0; i < graph.size(); i++) { 72 vector<Vertex::Index>::size_type src_index = 0; 73 EXPECT_TRUE(IndexOf(sorted, i, &src_index)); 74 for (Vertex::EdgeMap::const_iterator it = graph[i].out_edges.begin(); 75 it != graph[i].out_edges.end(); ++it) { 76 vector<Vertex::Index>::size_type dst_index = 0; 77 EXPECT_TRUE(IndexOf(sorted, it->first, &dst_index)); 78 EXPECT_LT(dst_index, src_index); 79 } 80 } 81} 82 83} // namespace chromeos_update_engine 84