Andrew de los Reyes | 35a7af1 | 2010-03-10 16:33:26 -0800 | [diff] [blame] | 1 | // Copyright (c) 2010 The Chromium OS Authors. All rights reserved. |
| 2 | // Use of this source code is governed by a BSD-style license that can be |
| 3 | // found in the LICENSE file. |
| 4 | |
| 5 | #ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_CYCLE_BREAKER_H__ |
| 6 | #define CHROMEOS_PLATFORM_UPDATE_ENGINE_CYCLE_BREAKER_H__ |
| 7 | |
| 8 | // This is a modified implementation of Donald B. Johnson's algorithm for |
| 9 | // finding all elementary cycles (a.k.a. circuits) in a directed graph. |
| 10 | // See the paper "Finding All the Elementary Circuits of a Directed Graph" |
| 11 | // at http://dutta.csc.ncsu.edu/csc791_spring07/wrap/circuits_johnson.pdf |
| 12 | // for reference. |
| 13 | |
| 14 | // Note: this version of the algorithm not only finds cycles, but breaks them. |
| 15 | // It uses a simple greedy algorithm for cutting: when a cycle is discovered, |
| 16 | // the edge with the least weight is cut. Longer term we may wish to do |
| 17 | // something more intelligent, since the goal is (ideally) to minimize the |
| 18 | // sum of the weights of all cut cycles. In practice, it's intractable |
| 19 | // to consider all cycles before cutting any; there are simply too many. |
| 20 | // In a sample graph representative of a typical workload, I found over |
| 21 | // 5 * 10^15 cycles. |
| 22 | |
| 23 | #include <set> |
| 24 | #include <vector> |
| 25 | #include "update_engine/graph_types.h" |
| 26 | |
| 27 | namespace chromeos_update_engine { |
| 28 | |
| 29 | class CycleBreaker { |
| 30 | public: |
Andrew de los Reyes | 182a9f5 | 2010-10-05 16:33:51 -0700 | [diff] [blame^] | 31 | CycleBreaker() : skipped_ops_(0) {} |
Andrew de los Reyes | 35a7af1 | 2010-03-10 16:33:26 -0800 | [diff] [blame] | 32 | // out_cut_edges is replaced with the cut edges. |
| 33 | void BreakCycles(const Graph& graph, std::set<Edge>* out_cut_edges); |
Andrew de los Reyes | 182a9f5 | 2010-10-05 16:33:51 -0700 | [diff] [blame^] | 34 | |
| 35 | size_t skipped_ops() const { return skipped_ops_; } |
Andrew de los Reyes | 35a7af1 | 2010-03-10 16:33:26 -0800 | [diff] [blame] | 36 | |
| 37 | private: |
| 38 | void HandleCircuit(); |
| 39 | void Unblock(Vertex::Index u); |
Andrew de los Reyes | 21ab31c | 2010-08-19 14:59:00 -0700 | [diff] [blame] | 40 | bool Circuit(Vertex::Index vertex, Vertex::Index depth); |
Andrew de los Reyes | 4510989 | 2010-07-26 13:49:31 -0700 | [diff] [blame] | 41 | bool StackContainsCutEdge() const; |
Andrew de los Reyes | 35a7af1 | 2010-03-10 16:33:26 -0800 | [diff] [blame] | 42 | |
| 43 | std::vector<bool> blocked_; // "blocked" in the paper |
| 44 | Vertex::Index current_vertex_; // "s" in the paper |
| 45 | std::vector<Vertex::Index> stack_; // the stack variable in the paper |
| 46 | Graph subgraph_; // "A_K" in the paper |
| 47 | Graph blocked_graph_; // "B" in the paper |
| 48 | |
| 49 | std::set<Edge> cut_edges_; |
Andrew de los Reyes | 182a9f5 | 2010-10-05 16:33:51 -0700 | [diff] [blame^] | 50 | |
| 51 | // Number of operations skipped b/c we know they don't have any |
| 52 | // incoming edges. |
| 53 | size_t skipped_ops_; |
Andrew de los Reyes | 35a7af1 | 2010-03-10 16:33:26 -0800 | [diff] [blame] | 54 | }; |
| 55 | |
| 56 | } // namespace chromeos_update_engine |
| 57 | |
| 58 | #endif // CHROMEOS_PLATFORM_UPDATE_ENGINE_CYCLE_BREAKER_H__ |