OLD | NEW |
---|---|
(Empty) | |
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 implemenation of Donald B. Johnson's algorithm for | |
Daniel Erat
2010/03/10 22:50:01
s/implemenation/implementation/
adlr
2010/03/11 00:41:42
Done.
| |
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: | |
31 // out_cut_edges is replaced with the cut edges. | |
32 void BreakCycles(const Graph& graph, std::set<Edge>* out_cut_edges); | |
33 | |
34 private: | |
35 void HandleCircuit(); | |
36 void Unblock(Vertex::Index u); | |
37 bool Circuit(Vertex::Index vertex); | |
38 | |
39 std::vector<bool> blocked_; // "blocked" in the paper | |
40 Vertex::Index current_vertex_; // "s" in the paper | |
41 std::vector<Vertex::Index> stack_; // the stack variable in the paper | |
42 Graph subgraph_; // "A_K" in the paper | |
43 Graph blocked_graph_; // "B" in the paper | |
44 | |
45 std::set<Edge> cut_edges_; | |
46 }; | |
47 | |
48 } // namespace chromeos_update_engine | |
49 | |
50 #endif // CHROMEOS_PLATFORM_UPDATE_ENGINE_CYCLE_BREAKER_H__ | |
OLD | NEW |