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