AU: Fix bug in impl of Johnson's circuit finding algorithm.

cycle_breaker_unittest.cc

 // Copyright (c) 2010 The Chromium OS Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include <set>
 #include <string>
 #include <utility>
 #include <vector>
 #include <gtest/gtest.h>
 #include "chromeos/obsolete_logging.h"
@@ skipping 110 matching lines @@
   breaker.BreakCycles(graph, &broken_edges);
 
   // These are required to be broken:
   EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_b, n_a)));
   EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_b, n_c)));
   EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_d, n_e)));
   EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_f, n_g)));
   EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_h, n_i)));
 }
 
+TEST(CycleBreakerTest, UnblockGraphTest) {
+  int counter = 0;
+  const Vertex::Index n_a = counter++;
+  const Vertex::Index n_b = counter++;
+  const Vertex::Index n_c = counter++;
+  const Vertex::Index n_d = counter++;
+  const Graph::size_type kNodeCount = counter++;
+
+  Graph graph(kNodeCount);
+
+  graph[n_a].out_edges.insert(EdgeWithWeight(n_b, 1));
+  graph[n_a].out_edges.insert(EdgeWithWeight(n_c, 1));
+  graph[n_b].out_edges.insert(EdgeWithWeight(n_c, 2));
+  graph[n_c].out_edges.insert(EdgeWithWeight(n_b, 2));
+  graph[n_b].out_edges.insert(EdgeWithWeight(n_d, 2));
+  graph[n_d].out_edges.insert(EdgeWithWeight(n_a, 2));
+
+  CycleBreaker breaker;
+  
+  set<Edge> broken_edges;
+  breaker.BreakCycles(graph, &broken_edges);
+
+  // These are required to be broken:
+  EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_a, n_b)));
+  EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_a, n_c)));
+}
+
 }  // namespace chromeos_update_engine