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 #include "update_engine/cycle_breaker.h" | 5 #include "update_engine/cycle_breaker.h" |
6 #include <set> | 6 #include <set> |
7 #include <utility> | 7 #include <utility> |
8 #include "update_engine/graph_utils.h" | 8 #include "update_engine/graph_utils.h" |
9 #include "update_engine/tarjan.h" | 9 #include "update_engine/tarjan.h" |
10 #include "update_engine/utils.h" | 10 #include "update_engine/utils.h" |
(...skipping 59 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
70 | 70 |
71 out_cut_edges->swap(cut_edges_); | 71 out_cut_edges->swap(cut_edges_); |
72 DCHECK(stack_.empty()); | 72 DCHECK(stack_.empty()); |
73 } | 73 } |
74 | 74 |
75 void CycleBreaker::HandleCircuit() { | 75 void CycleBreaker::HandleCircuit() { |
76 stack_.push_back(current_vertex_); | 76 stack_.push_back(current_vertex_); |
77 CHECK_GE(stack_.size(), 2); | 77 CHECK_GE(stack_.size(), 2); |
78 Edge min_edge = make_pair(stack_[0], stack_[1]); | 78 Edge min_edge = make_pair(stack_[0], stack_[1]); |
79 uint64_t min_edge_weight = kuint64max; | 79 uint64_t min_edge_weight = kuint64max; |
80 const int kMaxEdgesToConsider = 4; | |
81 int edges_considered = 0; | |
80 for (vector<Vertex::Index>::const_iterator it = stack_.begin(); | 82 for (vector<Vertex::Index>::const_iterator it = stack_.begin(); |
81 it != (stack_.end() - 1); ++it) { | 83 it != (stack_.end() - 1); ++it) { |
82 Edge edge = make_pair(*it, *(it + 1)); | 84 Edge edge = make_pair(*it, *(it + 1)); |
83 if (cut_edges_.find(edge) != cut_edges_.end()) { | 85 if (cut_edges_.find(edge) != cut_edges_.end()) { |
84 stack_.pop_back(); | 86 stack_.pop_back(); |
85 return; | 87 return; |
86 } | 88 } |
87 uint64_t edge_weight = graph_utils::EdgeWeight(subgraph_, edge); | 89 uint64_t edge_weight = graph_utils::EdgeWeight(subgraph_, edge); |
88 if (edge_weight < min_edge_weight) { | 90 if (edge_weight < min_edge_weight) { |
89 min_edge_weight = edge_weight; | 91 min_edge_weight = edge_weight; |
90 min_edge = edge; | 92 min_edge = edge; |
91 } | 93 } |
94 edges_considered++; | |
95 if (edges_considered == kMaxEdgesToConsider) | |
96 break; | |
92 } | 97 } |
93 cut_edges_.insert(min_edge); | 98 cut_edges_.insert(min_edge); |
94 stack_.pop_back(); | 99 stack_.pop_back(); |
95 } | 100 } |
96 | 101 |
97 void CycleBreaker::Unblock(Vertex::Index u) { | 102 void CycleBreaker::Unblock(Vertex::Index u) { |
98 blocked_[u] = false; | 103 blocked_[u] = false; |
99 | 104 |
100 for (Vertex::EdgeMap::iterator it = blocked_graph_[u].out_edges.begin(); | 105 for (Vertex::EdgeMap::iterator it = blocked_graph_[u].out_edges.begin(); |
101 it != blocked_graph_[u].out_edges.end(); ) { | 106 it != blocked_graph_[u].out_edges.end(); ) { |
102 Vertex::Index w = it->first; | 107 Vertex::Index w = it->first; |
103 blocked_graph_[u].out_edges.erase(it++); | 108 blocked_graph_[u].out_edges.erase(it++); |
104 if (blocked_[w]) | 109 if (blocked_[w]) |
105 Unblock(w); | 110 Unblock(w); |
106 } | 111 } |
107 } | 112 } |
108 | 113 |
114 bool CycleBreaker::StackContainsCutEdge() const { | |
115 for (std::vector<Vertex::Index>::const_iterator it = ++stack_.begin(), | |
116 e = stack_.end(); it != e; ++it) { | |
117 Edge edge = make_pair(*(it - 1), *it); | |
118 if (utils::SetContainsKey(cut_edges_, edge)) { | |
119 return true; | |
120 } | |
121 } | |
122 return false; | |
123 } | |
124 | |
109 bool CycleBreaker::Circuit(Vertex::Index vertex) { | 125 bool CycleBreaker::Circuit(Vertex::Index vertex) { |
110 // "vertex" was "v" in the original paper. | 126 // "vertex" was "v" in the original paper. |
111 bool found = false; // Was "f" in the original paper. | 127 bool found = false; // Was "f" in the original paper. |
112 stack_.push_back(vertex); | 128 stack_.push_back(vertex); |
113 blocked_[vertex] = true; | 129 blocked_[vertex] = true; |
114 | 130 |
115 for (Vertex::SubgraphEdgeMap::iterator w = | 131 for (Vertex::SubgraphEdgeMap::iterator w = |
116 subgraph_[vertex].subgraph_edges.begin(); | 132 subgraph_[vertex].subgraph_edges.begin(); |
117 w != subgraph_[vertex].subgraph_edges.end(); ++w) { | 133 w != subgraph_[vertex].subgraph_edges.end(); ++w) { |
118 if (*w == current_vertex_) { | 134 if (*w == current_vertex_) { |
119 // The original paper called for printing stack_ followed by | 135 // The original paper called for printing stack_ followed by |
120 // current_vertex_ here, which is a cycle. Instead, we call | 136 // current_vertex_ here, which is a cycle. Instead, we call |
121 // HandleCircuit() to break it. | 137 // HandleCircuit() to break it. |
122 HandleCircuit(); | 138 HandleCircuit(); |
123 found = true; | 139 found = true; |
124 } else if (!blocked_[*w]) { | 140 } else if (!blocked_[*w]) { |
125 if (Circuit(*w)) | 141 if (Circuit(*w)) { |
126 found = true; | 142 found = true; |
143 if (StackContainsCutEdge()) | |
petkov
2010/07/23 06:32:23
this seems to introduce n^2 kind of complexity...
| |
144 break; | |
145 } | |
127 } | 146 } |
128 } | 147 } |
129 | 148 |
130 if (found) { | 149 if (found) { |
131 Unblock(vertex); | 150 Unblock(vertex); |
132 } else { | 151 } else { |
133 for (Vertex::SubgraphEdgeMap::iterator w = | 152 for (Vertex::SubgraphEdgeMap::iterator w = |
134 subgraph_[vertex].subgraph_edges.begin(); | 153 subgraph_[vertex].subgraph_edges.begin(); |
135 w != subgraph_[vertex].subgraph_edges.end(); ++w) { | 154 w != subgraph_[vertex].subgraph_edges.end(); ++w) { |
136 subgraph_[*w].subgraph_edges.insert(vertex); | 155 subgraph_[*w].subgraph_edges.insert(vertex); |
137 } | 156 } |
138 } | 157 } |
139 CHECK_EQ(vertex, stack_.back()); | 158 CHECK_EQ(vertex, stack_.back()); |
140 stack_.pop_back(); | 159 stack_.pop_back(); |
141 return found; | 160 return found; |
142 } | 161 } |
143 | 162 |
144 } // namespace chromeos_update_engine | 163 } // namespace chromeos_update_engine |
OLD | NEW |