1 // 2 // Copyright (C) 2010 The Android Open Source Project 3 // 4 // Licensed under the Apache License, Version 2.0 (the "License"); 5 // you may not use this file except in compliance with the License. 6 // You may obtain a copy of the License at 7 // 8 // http://www.apache.org/licenses/LICENSE-2.0 9 // 10 // Unless required by applicable law or agreed to in writing, software 11 // distributed under the License is distributed on an "AS IS" BASIS, 12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 // See the License for the specific language governing permissions and 14 // limitations under the License. 15 // 16 17 #ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_CYCLE_BREAKER_H_ 18 #define UPDATE_ENGINE_PAYLOAD_GENERATOR_CYCLE_BREAKER_H_ 19 20 // This is a modified implementation of Donald B. Johnson's algorithm for 21 // finding all elementary cycles (a.k.a. circuits) in a directed graph. 22 // See the paper "Finding All the Elementary Circuits of a Directed Graph" 23 // at http://dutta.csc.ncsu.edu/csc791_spring07/wrap/circuits_johnson.pdf 24 // for reference. 25 26 // Note: this version of the algorithm not only finds cycles, but breaks them. 27 // It uses a simple greedy algorithm for cutting: when a cycle is discovered, 28 // the edge with the least weight is cut. Longer term we may wish to do 29 // something more intelligent, since the goal is (ideally) to minimize the 30 // sum of the weights of all cut cycles. In practice, it's intractable 31 // to consider all cycles before cutting any; there are simply too many. 32 // In a sample graph representative of a typical workload, I found over 33 // 5 * 10^15 cycles. 34 35 #include <set> 36 #include <vector> 37 38 #include "update_engine/payload_generator/graph_types.h" 39 40 namespace chromeos_update_engine { 41 42 class CycleBreaker { 43 public: 44 CycleBreaker() : skipped_ops_(0) {} 45 // out_cut_edges is replaced with the cut edges. 46 void BreakCycles(const Graph& graph, std::set<Edge>* out_cut_edges); 47 48 size_t skipped_ops() const { return skipped_ops_; } 49 50 private: 51 void HandleCircuit(); 52 void Unblock(Vertex::Index u); 53 bool Circuit(Vertex::Index vertex, Vertex::Index depth); 54 bool StackContainsCutEdge() const; 55 56 std::vector<bool> blocked_; // "blocked" in the paper 57 Vertex::Index current_vertex_; // "s" in the paper 58 std::vector<Vertex::Index> stack_; // the stack variable in the paper 59 Graph subgraph_; // "A_K" in the paper 60 Graph blocked_graph_; // "B" in the paper 61 62 std::set<Edge> cut_edges_; 63 64 // Number of operations skipped b/c we know they don't have any 65 // incoming edges. 66 size_t skipped_ops_; 67 }; 68 69 } // namespace chromeos_update_engine 70 71 #endif // UPDATE_ENGINE_PAYLOAD_GENERATOR_CYCLE_BREAKER_H_ 72
