commit 8a51e5c4d3386aeed55b0af1993a00f60856a3e2
author Andrew de los Reyes <adlr@chromium.org> Mon Jul 26 13:40:03 2010 -0700
committer Andrew de los Reyes <adlr@chromium.org> Mon Jul 26 13:40:03 2010 -0700
tree f3645a73cd488fa747614781c731ea0fb48dec79
parent 296889c68c92b04d307035c5803681f8d2c8f9d3

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

The original paper at
http://dutta.csc.ncsu.edu/csc791_spring07/wrap/circuits_johnson.pdf is
correct in the algorithm description. I made a mistake when
translating it from pseudo code to C++. This CL corrects that mistake.

BUG=chromium-os:5043
TEST=unittest, tested building and applying an update that exposed this issue

Review URL: http://codereview.chromium.org/3020026

cycle_breaker.cc

diff --git a/cycle_breaker.cc b/cycle_breaker.cc
index 6e06898..0998dac 100644
--- a/cycle_breaker.cc
+++ b/cycle_breaker.cc
@@ -133,7 +133,11 @@
     for (Vertex::SubgraphEdgeMap::iterator w =
              subgraph_[vertex].subgraph_edges.begin();
          w != subgraph_[vertex].subgraph_edges.end(); ++w) {
-      subgraph_[*w].subgraph_edges.insert(vertex);
+      if (blocked_graph_[*w].out_edges.find(vertex) ==
+          blocked_graph_[*w].out_edges.end()) {
+        blocked_graph_[*w].out_edges.insert(make_pair(vertex,
+                                                      EdgeProperties()));
+      }
     }
   }
   CHECK_EQ(vertex, stack_.back());

cycle_breaker_unittest.cc

diff --git a/cycle_breaker_unittest.cc b/cycle_breaker_unittest.cc
index 47a6e75..1c81e54 100644
--- a/cycle_breaker_unittest.cc
+++ b/cycle_breaker_unittest.cc
@@ -128,4 +128,31 @@
   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