AU: delta generation: cut cycles in graph more aggressively

cycle_breaker.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 "update_engine/cycle_breaker.h"
 #include <set>
 #include <utility>
 #include "update_engine/graph_utils.h"
 #include "update_engine/tarjan.h"
 #include "update_engine/utils.h"
@@ skipping 59 matching lines @@
   
   out_cut_edges->swap(cut_edges_);
   DCHECK(stack_.empty());
 }
 
 void CycleBreaker::HandleCircuit() {
   stack_.push_back(current_vertex_);
   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));
     if (cut_edges_.find(edge) != cut_edges_.end()) {
       stack_.pop_back();
       return;
     }
     uint64_t edge_weight = graph_utils::EdgeWeight(subgraph_, edge);
     if (edge_weight < min_edge_weight) {
       min_edge_weight = edge_weight;
       min_edge = edge;
     }
+    edges_considered++;
+    if (edges_considered == kMaxEdgesToConsider)
+      break;
   }
   cut_edges_.insert(min_edge);
   stack_.pop_back();
 }
 
 void CycleBreaker::Unblock(Vertex::Index u) {
   blocked_[u] = false;
 
   for (Vertex::EdgeMap::iterator it = blocked_graph_[u].out_edges.begin();
        it != blocked_graph_[u].out_edges.end(); ) {
     Vertex::Index w = it->first;
     blocked_graph_[u].out_edges.erase(it++);
     if (blocked_[w])
       Unblock(w);
   }
 }
 
+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.
   stack_.push_back(vertex);
   blocked_[vertex] = true;
 
   for (Vertex::SubgraphEdgeMap::iterator w =
            subgraph_[vertex].subgraph_edges.begin();
        w != subgraph_[vertex].subgraph_edges.end(); ++w) {
     if (*w == current_vertex_) {
       // The original paper called for printing stack_ followed by
       // current_vertex_ here, which is a cycle. Instead, we call
       // HandleCircuit() to break it.
       HandleCircuit();
       found = true;
     } else if (!blocked_[*w]) {
-      if (Circuit(*w))
+      if (Circuit(*w)) {
         found = true;
+        if (StackContainsCutEdge())

[petkov, 2010/07/23 06:32:23]

this seems to introduce n^2 kind of complexity... I assume sizes are OK to not
be a problem (or, maybe, there's a bigger problem already anyway).

+          break;
+      }
     }
   }
 
   if (found) {
     Unblock(vertex);
   } else {
     for (Vertex::SubgraphEdgeMap::iterator w =
              subgraph_[vertex].subgraph_edges.begin();
          w != subgraph_[vertex].subgraph_edges.end(); ++w) {
       subgraph_[*w].subgraph_edges.insert(vertex);
     }
   }
   CHECK_EQ(vertex, stack_.back());
   stack_.pop_back();
   return found;
 }
 
 }  // namespace chromeos_update_engine