AU: Cyclebreaker optimization

cycle_breaker.h

 // 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.
 
 #ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_CYCLE_BREAKER_H__
 #define CHROMEOS_PLATFORM_UPDATE_ENGINE_CYCLE_BREAKER_H__
 
 // This is a modified implementation of Donald B. Johnson's algorithm for
 // finding all elementary cycles (a.k.a. circuits) in a directed graph.
 // See the paper "Finding All the Elementary Circuits of a Directed Graph"
@@ skipping 10 matching lines @@
 // 5 * 10^15 cycles.
 
 #include <set>
 #include <vector>
 #include "update_engine/graph_types.h"
 
 namespace chromeos_update_engine {
 
 class CycleBreaker {
  public:
+  CycleBreaker() : skipped_ops_(0) {}
   // out_cut_edges is replaced with the cut edges.
   void BreakCycles(const Graph& graph, std::set<Edge>* out_cut_edges);
+  
+  size_t skipped_ops() const { return skipped_ops_; }
 
  private:
   void HandleCircuit();
   void Unblock(Vertex::Index u);
   bool Circuit(Vertex::Index vertex, Vertex::Index depth);
   bool StackContainsCutEdge() const;
 
   std::vector<bool> blocked_;  // "blocked" in the paper
   Vertex::Index current_vertex_;  // "s" in the paper
   std::vector<Vertex::Index> stack_;  // the stack variable in the paper
   Graph subgraph_;  // "A_K" in the paper
   Graph blocked_graph_;  // "B" in the paper
 
   std::set<Edge> cut_edges_;
+  
+  // Number of operations skipped b/c we know they don't have any
+  // incoming edges.
+  size_t skipped_ops_;
 };
 
 }  // namespace chromeos_update_engine
 
 #endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_CYCLE_BREAKER_H__