cycle_breaker.h revision 072359ca138504065e1e0c1189eb38c09576d324
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 UPDATE_ENGINE_PAYLOAD_GENERATOR_CYCLE_BREAKER_H_ 6#define UPDATE_ENGINE_PAYLOAD_GENERATOR_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 26#include "update_engine/payload_generator/graph_types.h" 27 28namespace chromeos_update_engine { 29 30class CycleBreaker { 31 public: 32 CycleBreaker() : skipped_ops_(0) {} 33 // out_cut_edges is replaced with the cut edges. 34 void BreakCycles(const Graph& graph, std::set<Edge>* out_cut_edges); 35 36 size_t skipped_ops() const { return skipped_ops_; } 37 38 private: 39 void HandleCircuit(); 40 void Unblock(Vertex::Index u); 41 bool Circuit(Vertex::Index vertex, Vertex::Index depth); 42 bool StackContainsCutEdge() const; 43 44 std::vector<bool> blocked_; // "blocked" in the paper 45 Vertex::Index current_vertex_; // "s" in the paper 46 std::vector<Vertex::Index> stack_; // the stack variable in the paper 47 Graph subgraph_; // "A_K" in the paper 48 Graph blocked_graph_; // "B" in the paper 49 50 std::set<Edge> cut_edges_; 51 52 // Number of operations skipped b/c we know they don't have any 53 // incoming edges. 54 size_t skipped_ops_; 55}; 56 57} // namespace chromeos_update_engine 58 59#endif // UPDATE_ENGINE_PAYLOAD_GENERATOR_CYCLE_BREAKER_H_ 60