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 17 matching lines...) Expand all Loading... |
28 | 28 |
29 class CycleBreaker { | 29 class CycleBreaker { |
30 public: | 30 public: |
31 // out_cut_edges is replaced with the cut edges. | 31 // out_cut_edges is replaced with the cut edges. |
32 void BreakCycles(const Graph& graph, std::set<Edge>* out_cut_edges); | 32 void BreakCycles(const Graph& graph, std::set<Edge>* out_cut_edges); |
33 | 33 |
34 private: | 34 private: |
35 void HandleCircuit(); | 35 void HandleCircuit(); |
36 void Unblock(Vertex::Index u); | 36 void Unblock(Vertex::Index u); |
37 bool Circuit(Vertex::Index vertex); | 37 bool Circuit(Vertex::Index vertex); |
| 38 bool StackContainsCutEdge() const; |
38 | 39 |
39 std::vector<bool> blocked_; // "blocked" in the paper | 40 std::vector<bool> blocked_; // "blocked" in the paper |
40 Vertex::Index current_vertex_; // "s" in the paper | 41 Vertex::Index current_vertex_; // "s" in the paper |
41 std::vector<Vertex::Index> stack_; // the stack variable in the paper | 42 std::vector<Vertex::Index> stack_; // the stack variable in the paper |
42 Graph subgraph_; // "A_K" in the paper | 43 Graph subgraph_; // "A_K" in the paper |
43 Graph blocked_graph_; // "B" in the paper | 44 Graph blocked_graph_; // "B" in the paper |
44 | 45 |
45 std::set<Edge> cut_edges_; | 46 std::set<Edge> cut_edges_; |
46 }; | 47 }; |
47 | 48 |
48 } // namespace chromeos_update_engine | 49 } // namespace chromeos_update_engine |
49 | 50 |
50 #endif // CHROMEOS_PLATFORM_UPDATE_ENGINE_CYCLE_BREAKER_H__ | 51 #endif // CHROMEOS_PLATFORM_UPDATE_ENGINE_CYCLE_BREAKER_H__ |
OLD | NEW |