cycle_breaker.h revision 161c4a132743f15fc4757112b673085c2a7a7f29
13839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// Copyright (c) 2010 The Chromium OS Authors. All rights reserved. 23839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// Use of this source code is governed by a BSD-style license that can be 33839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// found in the LICENSE file. 421c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o 521c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_CYCLE_BREAKER_H_ 621c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_CYCLE_BREAKER_H_ 721c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o 821c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o// This is a modified implementation of Donald B. Johnson's algorithm for 921c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o// finding all elementary cycles (a.k.a. circuits) in a directed graph. 103839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// See the paper "Finding All the Elementary Circuits of a Directed Graph" 113839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// at http://dutta.csc.ncsu.edu/csc791_spring07/wrap/circuits_johnson.pdf 123839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// for reference. 133839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o 143839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// Note: this version of the algorithm not only finds cycles, but breaks them. 153839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// It uses a simple greedy algorithm for cutting: when a cycle is discovered, 163839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// the edge with the least weight is cut. Longer term we may wish to do 173839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// something more intelligent, since the goal is (ideally) to minimize the 183839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// sum of the weights of all cut cycles. In practice, it's intractable 193839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// to consider all cycles before cutting any; there are simply too many. 203839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// In a sample graph representative of a typical workload, I found over 213839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// 5 * 10^15 cycles. 223839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o 233839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o#include <set> 243839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o#include <vector> 253839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o 263839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o#include "update_engine/payload_generator/graph_types.h" 273839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o 283839e65723771b85975f4263102dd3ceec4523cTheodore Ts'onamespace chromeos_update_engine { 293839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o 303839e65723771b85975f4263102dd3ceec4523cTheodore Ts'oclass CycleBreaker { 313839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o public: 323839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o CycleBreaker() : skipped_ops_(0) {} 333839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o // out_cut_edges is replaced with the cut edges. 343839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o void BreakCycles(const Graph& graph, std::set<Edge>* out_cut_edges); 353839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o 363839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o size_t skipped_ops() const { return skipped_ops_; } 373839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o 383839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o private: 393839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o void HandleCircuit(); 403839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o void Unblock(Vertex::Index u); 41aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o bool Circuit(Vertex::Index vertex, Vertex::Index depth); 423839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o bool StackContainsCutEdge() const; 433839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o 44b969b1b8a5c13992cadb026114731958644540d8Matthias Andree std::vector<bool> blocked_; // "blocked" in the paper 4548e6e81362f264aee4f3945c14928efaf71a06c9Theodore Ts'o Vertex::Index current_vertex_; // "s" in the paper 4648e6e81362f264aee4f3945c14928efaf71a06c9Theodore Ts'o std::vector<Vertex::Index> stack_; // the stack variable in the paper 473839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Graph subgraph_; // "A_K" in the paper 4821c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o Graph blocked_graph_; // "B" in the paper 490926668d3af802b4d385d0fc3525a5a4e679574aTheodore Ts'o 503839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o std::set<Edge> cut_edges_; 51aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o 52aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o // Number of operations skipped b/c we know they don't have any 53aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o // incoming edges. 54aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o size_t skipped_ops_; 55aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o}; 56aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o 57ad4fa4660404ed88a3231fee338397af11e041b4Theodore Ts'o} // namespace chromeos_update_engine 588fdc9985c1e2a4467630b33719b7feb281b7b33bTheodore Ts'o 593839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o#endif // CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_CYCLE_BREAKER_H_ 603839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o