AU: delta generation: cut cycles in graph more aggressively
I found that with some deltas I was generating, finding and cutting
all cycles in the graph was taking way too long (hours). This CL
increases the agressiveness used to cut edges and presents a test case
that performs particularly poorly without this optimization.
BUG=chromium-os:5060
TEST=attached unittest, tested generating/applying delta w/ images that
needed this optimization
Review URL: http://codereview.chromium.org/3015023
diff --git a/cycle_breaker.cc b/cycle_breaker.cc
index 0998dac..f9e3de6 100644
--- a/cycle_breaker.cc
+++ b/cycle_breaker.cc
@@ -77,6 +77,8 @@
CHECK_GE(stack_.size(), 2);
Edge min_edge = make_pair(stack_[0], stack_[1]);
uint64_t min_edge_weight = kuint64max;
+ const int kMaxEdgesToConsider = 4;
+ int edges_considered = 0;
for (vector<Vertex::Index>::const_iterator it = stack_.begin();
it != (stack_.end() - 1); ++it) {
Edge edge = make_pair(*it, *(it + 1));
@@ -89,6 +91,9 @@
min_edge_weight = edge_weight;
min_edge = edge;
}
+ edges_considered++;
+ if (edges_considered == kMaxEdgesToConsider)
+ break;
}
cut_edges_.insert(min_edge);
stack_.pop_back();
@@ -106,6 +111,17 @@
}
}
+bool CycleBreaker::StackContainsCutEdge() const {
+ for (std::vector<Vertex::Index>::const_iterator it = ++stack_.begin(),
+ e = stack_.end(); it != e; ++it) {
+ Edge edge = make_pair(*(it - 1), *it);
+ if (utils::SetContainsKey(cut_edges_, edge)) {
+ return true;
+ }
+ }
+ return false;
+}
+
bool CycleBreaker::Circuit(Vertex::Index vertex) {
// "vertex" was "v" in the original paper.
bool found = false; // Was "f" in the original paper.
@@ -122,8 +138,11 @@
HandleCircuit();
found = true;
} else if (!blocked_[*w]) {
- if (Circuit(*w))
+ if (Circuit(*w)) {
found = true;
+ if (StackContainsCutEdge())
+ break;
+ }
}
}