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;
+ }
}
}
diff --git a/cycle_breaker.h b/cycle_breaker.h
index e9bb1e4..359f55b 100644
--- a/cycle_breaker.h
+++ b/cycle_breaker.h
@@ -35,6 +35,7 @@
void HandleCircuit();
void Unblock(Vertex::Index u);
bool Circuit(Vertex::Index vertex);
+ bool StackContainsCutEdge() const;
std::vector<bool> blocked_; // "blocked" in the paper
Vertex::Index current_vertex_; // "s" in the paper
diff --git a/cycle_breaker_unittest.cc b/cycle_breaker_unittest.cc
index 1c81e54..59d6825 100644
--- a/cycle_breaker_unittest.cc
+++ b/cycle_breaker_unittest.cc
@@ -80,6 +80,77 @@
}
} // namespace {}
+
+// This creates a bunch of cycles like this:
+//
+// root <------.
+// (t)-> / | \ |
+// V V V |
+// N N N |
+// \ | / |
+// VVV |
+// N |
+// / | \ |
+// V V V |
+// N N N |
+// ... |
+// (s)-> \ | / |
+// VVV |
+// N |
+// \_________/
+//
+// such that the original cutting algo would cut edges (s). We changed
+// the algorithm to cut cycles (t) instead, since they are closer to the
+// root, and that can massively speed up cycle cutting.
+TEST(CycleBreakerTest, AggressiveCutTest) {
+ int counter = 0;
+
+ const int kNodesPerGroup = 4;
+ const int kGroups = 33;
+
+ Graph graph(kGroups * kNodesPerGroup + 1); // + 1 for the root node
+
+ const Vertex::Index n_root = counter++;
+
+ Vertex::Index last_hub = n_root;
+ for (int i = 0; i < kGroups; i++) {
+ uint64_t weight = 5;
+ if (i == 0)
+ weight = 2;
+ else if (i == (kGroups - 1))
+ weight = 1;
+
+ const Vertex::Index next_hub = counter++;
+
+ for (int j = 0; j < (kNodesPerGroup - 1); j++) {
+ const Vertex::Index node = counter++;
+ graph[last_hub].out_edges.insert(EdgeWithWeight(node, weight));
+ graph[node].out_edges.insert(EdgeWithWeight(next_hub, weight));
+ }
+ last_hub = next_hub;
+ }
+
+ graph[last_hub].out_edges.insert(EdgeWithWeight(n_root, 5));
+
+
+ EXPECT_EQ(counter, graph.size());
+
+ CycleBreaker breaker;
+
+ set<Edge> broken_edges;
+ LOG(INFO) << "If this hangs for more than 1 second, the test has failed.";
+ breaker.BreakCycles(graph, &broken_edges);
+
+ set<Edge> expected_cuts;
+
+ for (Vertex::EdgeMap::const_iterator it = graph[n_root].out_edges.begin(),
+ e = graph[n_root].out_edges.end(); it != e; ++it) {
+ expected_cuts.insert(make_pair(n_root, it->first));
+ }
+
+ EXPECT_TRUE(broken_edges == expected_cuts);
+}
+
TEST(CycleBreakerTest, WeightTest) {
int counter = 0;
const Vertex::Index n_a = counter++;