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 #include "update_engine/cycle_breaker.h" | |
6 #include <set> | |
7 #include <utility> | |
8 #include "update_engine/graph_utils.h" | |
9 #include "update_engine/tarjan.h" | |
10 #include "update_engine/utils.h" | |
11 | |
12 using std::make_pair; | |
13 using std::set; | |
14 using std::vector; | |
15 | |
16 namespace chromeos_update_engine { | |
17 | |
18 // This is the outer function from the original paper. | |
19 void CycleBreaker::BreakCycles(const Graph& graph, set<Edge>* out_cut_edges) { | |
20 cut_edges_.clear(); | |
21 | |
22 // Make a copy, which we will modify by removing edges. Thus, in each | |
23 // iteration subgraph_ is the current subgraph or the original with | |
24 // vertices we desire. This variable was "A_K" in the original paper. | |
25 subgraph_ = graph; | |
26 | |
27 // The paper calls for the "adjacency structure (i.e., graph) of | |
28 // strong (-ly connected) component K with least vertex in subgraph | |
29 // induced by {s, s + 1, ..., n}". | |
30 // We arbitrarily order each vertex by its index in the graph. Thus, | |
31 // each iteration, we are looking at the subgraph {s, s + 1, ..., n} | |
32 // and looking for the strongly connected component with vertex s. | |
33 | |
34 TarjanAlgorithm tarjan; | |
35 | |
36 for (Graph::size_type i = 0; i < subgraph_.size(); i++) { | |
37 if (i > 0) { | |
38 // Erase node (i - 1) from subgraph_. First, erase what it points to | |
39 subgraph_[i - 1].out_edges.clear(); | |
40 // Now, erase any pointers to node (i - 1) | |
41 for (Graph::size_type j = i; j < subgraph_.size(); j++) { | |
42 subgraph_[j].out_edges.erase(i - 1); | |
43 } | |
44 } | |
45 | |
46 // Calculate SCC (strongly connected component) with vertex i. | |
47 vector<Vertex::Index> component_indexes; | |
48 tarjan.Execute(i, &subgraph_, &component_indexes); | |
49 | |
50 // Set subgraph edges for the components in the SCC. | |
51 for (vector<Vertex::Index>::iterator it = component_indexes.begin(); | |
52 it != component_indexes.end(); ++it) { | |
53 subgraph_[*it].subgraph_edges.clear(); | |
54 for (vector<Vertex::Index>::iterator jt = component_indexes.begin(); | |
55 jt != component_indexes.end(); ++jt) { | |
56 // If there's a link from *it -> *jt in the graph, | |
57 // add a subgraph_ edge | |
58 if (utils::MapContainsKey(subgraph_[*it].out_edges, *jt)) | |
59 subgraph_[*it].subgraph_edges.insert(*jt); | |
60 } | |
61 } | |
62 | |
63 current_vertex_ = i; | |
64 blocked_.clear(); | |
65 blocked_.resize(subgraph_.size()); | |
66 blocked_graph_.clear(); | |
67 blocked_graph_.resize(subgraph_.size()); | |
68 Circuit(current_vertex_); | |
69 } | |
70 | |
71 out_cut_edges->swap(cut_edges_); | |
Daniel Erat
2010/03/10 22:50:01
nit: DCHECK(stack_.empty()) here?
adlr
2010/03/11 00:41:42
Done.
| |
72 } | |
73 | |
74 void CycleBreaker::HandleCircuit() { | |
75 stack_.push_back(current_vertex_); | |
76 CHECK_GE(stack_.size(), 2); | |
77 Edge min_edge = make_pair(stack_[0], stack_[1]); | |
78 uint64 min_edge_weight = kuint64max; | |
79 for (vector<Vertex::Index>::const_iterator it = stack_.begin(); | |
80 it != (stack_.end() - 1); ++it) { | |
81 Edge edge = make_pair(*it, *(it + 1)); | |
82 if (cut_edges_.find(edge) != cut_edges_.end()) { | |
83 stack_.pop_back(); | |
84 return; | |
85 } | |
86 uint64 edge_weight = graph_utils::EdgeWeight(subgraph_, edge); | |
87 if (edge_weight < min_edge_weight) { | |
88 min_edge_weight = edge_weight; | |
89 min_edge = edge; | |
90 } | |
91 } | |
92 cut_edges_.insert(min_edge); | |
93 stack_.pop_back(); | |
94 } | |
95 | |
96 void CycleBreaker::Unblock(Vertex::Index u) { | |
97 blocked_[u] = false; | |
98 | |
99 for (Vertex::EdgeMap::iterator it = blocked_graph_[u].out_edges.begin(); | |
100 it != blocked_graph_[u].out_edges.end(); ) { | |
101 Vertex::Index w = it->first; | |
102 blocked_graph_[u].out_edges.erase(it++); | |
103 if (blocked_[w]) | |
104 Unblock(w); | |
105 } | |
106 } | |
107 | |
108 bool CycleBreaker::Circuit(Vertex::Index vertex) { | |
109 // "vertex" was "v" in the original paper. | |
110 bool found = false; // Was "f" in the original paper. | |
111 stack_.push_back(vertex); | |
112 blocked_[vertex] = true; | |
113 | |
114 for (Vertex::SubgraphEdgeMap::iterator w = | |
115 subgraph_[vertex].subgraph_edges.begin(); | |
116 w != subgraph_[vertex].subgraph_edges.end(); ++w) { | |
117 if (*w == current_vertex_) { | |
118 // The original paper called for printing stack_ followed by | |
119 // current_vertex_ here, which is a cycle. Instead, we call | |
120 // HandleCircuit() to break it. | |
121 HandleCircuit(); | |
122 found = true; | |
123 } else if (!blocked_[*w]) { | |
124 if (Circuit(*w)) | |
125 found = true; | |
126 } | |
127 } | |
128 | |
129 if (found) { | |
130 Unblock(vertex); | |
131 } else { | |
132 for (Vertex::SubgraphEdgeMap::iterator w = | |
133 subgraph_[vertex].subgraph_edges.begin(); | |
134 w != subgraph_[vertex].subgraph_edges.end(); ++w) { | |
135 subgraph_[*w].subgraph_edges.insert(vertex); | |
136 } | |
137 } | |
138 CHECK_EQ(vertex, stack_.back()); | |
139 stack_.pop_back(); | |
140 return found; | |
141 } | |
142 | |
143 } // namespace chromeos_update_engine | |
OLD | NEW |