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
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());