OLD | NEW |
1 // Copyright (c) 2010 The Chromium OS Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include <set> | 5 #include <set> |
6 #include <string> | 6 #include <string> |
7 #include <utility> | 7 #include <utility> |
8 #include <vector> | 8 #include <vector> |
9 #include <gtest/gtest.h> | 9 #include <gtest/gtest.h> |
10 #include "chromeos/obsolete_logging.h" | 10 #include "chromeos/obsolete_logging.h" |
(...skipping 110 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
121 breaker.BreakCycles(graph, &broken_edges); | 121 breaker.BreakCycles(graph, &broken_edges); |
122 | 122 |
123 // These are required to be broken: | 123 // These are required to be broken: |
124 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_b, n_a))); | 124 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_b, n_a))); |
125 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_b, n_c))); | 125 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_b, n_c))); |
126 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_d, n_e))); | 126 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_d, n_e))); |
127 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_f, n_g))); | 127 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_f, n_g))); |
128 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_h, n_i))); | 128 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_h, n_i))); |
129 } | 129 } |
130 | 130 |
| 131 TEST(CycleBreakerTest, UnblockGraphTest) { |
| 132 int counter = 0; |
| 133 const Vertex::Index n_a = counter++; |
| 134 const Vertex::Index n_b = counter++; |
| 135 const Vertex::Index n_c = counter++; |
| 136 const Vertex::Index n_d = counter++; |
| 137 const Graph::size_type kNodeCount = counter++; |
| 138 |
| 139 Graph graph(kNodeCount); |
| 140 |
| 141 graph[n_a].out_edges.insert(EdgeWithWeight(n_b, 1)); |
| 142 graph[n_a].out_edges.insert(EdgeWithWeight(n_c, 1)); |
| 143 graph[n_b].out_edges.insert(EdgeWithWeight(n_c, 2)); |
| 144 graph[n_c].out_edges.insert(EdgeWithWeight(n_b, 2)); |
| 145 graph[n_b].out_edges.insert(EdgeWithWeight(n_d, 2)); |
| 146 graph[n_d].out_edges.insert(EdgeWithWeight(n_a, 2)); |
| 147 |
| 148 CycleBreaker breaker; |
| 149 |
| 150 set<Edge> broken_edges; |
| 151 breaker.BreakCycles(graph, &broken_edges); |
| 152 |
| 153 // These are required to be broken: |
| 154 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_a, n_b))); |
| 155 EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_a, n_c))); |
| 156 } |
| 157 |
131 } // namespace chromeos_update_engine | 158 } // namespace chromeos_update_engine |
OLD | NEW |