OLD | NEW |
1 // Copyright (c) 2010 The Chromium OS Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_CYCLE_BREAKER_H__ | 5 #ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_CYCLE_BREAKER_H__ |
6 #define CHROMEOS_PLATFORM_UPDATE_ENGINE_CYCLE_BREAKER_H__ | 6 #define CHROMEOS_PLATFORM_UPDATE_ENGINE_CYCLE_BREAKER_H__ |
7 | 7 |
8 // This is a modified implementation of Donald B. Johnson's algorithm for | 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. | 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" | 10 // See the paper "Finding All the Elementary Circuits of a Directed Graph" |
(...skipping 10 matching lines...) Expand all Loading... |
21 // 5 * 10^15 cycles. | 21 // 5 * 10^15 cycles. |
22 | 22 |
23 #include <set> | 23 #include <set> |
24 #include <vector> | 24 #include <vector> |
25 #include "update_engine/graph_types.h" | 25 #include "update_engine/graph_types.h" |
26 | 26 |
27 namespace chromeos_update_engine { | 27 namespace chromeos_update_engine { |
28 | 28 |
29 class CycleBreaker { | 29 class CycleBreaker { |
30 public: | 30 public: |
| 31 CycleBreaker() : skipped_ops_(0) {} |
31 // out_cut_edges is replaced with the cut edges. | 32 // out_cut_edges is replaced with the cut edges. |
32 void BreakCycles(const Graph& graph, std::set<Edge>* out_cut_edges); | 33 void BreakCycles(const Graph& graph, std::set<Edge>* out_cut_edges); |
| 34 |
| 35 size_t skipped_ops() const { return skipped_ops_; } |
33 | 36 |
34 private: | 37 private: |
35 void HandleCircuit(); | 38 void HandleCircuit(); |
36 void Unblock(Vertex::Index u); | 39 void Unblock(Vertex::Index u); |
37 bool Circuit(Vertex::Index vertex, Vertex::Index depth); | 40 bool Circuit(Vertex::Index vertex, Vertex::Index depth); |
38 bool StackContainsCutEdge() const; | 41 bool StackContainsCutEdge() const; |
39 | 42 |
40 std::vector<bool> blocked_; // "blocked" in the paper | 43 std::vector<bool> blocked_; // "blocked" in the paper |
41 Vertex::Index current_vertex_; // "s" in the paper | 44 Vertex::Index current_vertex_; // "s" in the paper |
42 std::vector<Vertex::Index> stack_; // the stack variable in the paper | 45 std::vector<Vertex::Index> stack_; // the stack variable in the paper |
43 Graph subgraph_; // "A_K" in the paper | 46 Graph subgraph_; // "A_K" in the paper |
44 Graph blocked_graph_; // "B" in the paper | 47 Graph blocked_graph_; // "B" in the paper |
45 | 48 |
46 std::set<Edge> cut_edges_; | 49 std::set<Edge> cut_edges_; |
| 50 |
| 51 // Number of operations skipped b/c we know they don't have any |
| 52 // incoming edges. |
| 53 size_t skipped_ops_; |
47 }; | 54 }; |
48 | 55 |
49 } // namespace chromeos_update_engine | 56 } // namespace chromeos_update_engine |
50 | 57 |
51 #endif // CHROMEOS_PLATFORM_UPDATE_ENGINE_CYCLE_BREAKER_H__ | 58 #endif // CHROMEOS_PLATFORM_UPDATE_ENGINE_CYCLE_BREAKER_H__ |
OLD | NEW |