cycle_breaker.h revision aea4c1cea20dda7ae7e85fc8924a2d784f70d806 
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
40namespace chromeos_update_engine {
41
42class 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