Andrew de los Reyes | 35a7af1 | 2010-03-10 16:33:26 -0800 | [diff] [blame] | 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_); |
| 72 | DCHECK(stack_.empty()); |
| 73 | } |
| 74 | |
| 75 | void CycleBreaker::HandleCircuit() { |
| 76 | stack_.push_back(current_vertex_); |
| 77 | CHECK_GE(stack_.size(), 2); |
| 78 | Edge min_edge = make_pair(stack_[0], stack_[1]); |
Andrew de los Reyes | 09e56d6 | 2010-04-23 13:45:53 -0700 | [diff] [blame^] | 79 | uint64_t min_edge_weight = kuint64max; |
Andrew de los Reyes | 35a7af1 | 2010-03-10 16:33:26 -0800 | [diff] [blame] | 80 | for (vector<Vertex::Index>::const_iterator it = stack_.begin(); |
| 81 | it != (stack_.end() - 1); ++it) { |
| 82 | Edge edge = make_pair(*it, *(it + 1)); |
| 83 | if (cut_edges_.find(edge) != cut_edges_.end()) { |
| 84 | stack_.pop_back(); |
| 85 | return; |
| 86 | } |
Andrew de los Reyes | 09e56d6 | 2010-04-23 13:45:53 -0700 | [diff] [blame^] | 87 | uint64_t edge_weight = graph_utils::EdgeWeight(subgraph_, edge); |
Andrew de los Reyes | 35a7af1 | 2010-03-10 16:33:26 -0800 | [diff] [blame] | 88 | if (edge_weight < min_edge_weight) { |
| 89 | min_edge_weight = edge_weight; |
| 90 | min_edge = edge; |
| 91 | } |
| 92 | } |
| 93 | cut_edges_.insert(min_edge); |
| 94 | stack_.pop_back(); |
| 95 | } |
| 96 | |
| 97 | void CycleBreaker::Unblock(Vertex::Index u) { |
| 98 | blocked_[u] = false; |
| 99 | |
| 100 | for (Vertex::EdgeMap::iterator it = blocked_graph_[u].out_edges.begin(); |
| 101 | it != blocked_graph_[u].out_edges.end(); ) { |
| 102 | Vertex::Index w = it->first; |
| 103 | blocked_graph_[u].out_edges.erase(it++); |
| 104 | if (blocked_[w]) |
| 105 | Unblock(w); |
| 106 | } |
| 107 | } |
| 108 | |
| 109 | bool CycleBreaker::Circuit(Vertex::Index vertex) { |
| 110 | // "vertex" was "v" in the original paper. |
| 111 | bool found = false; // Was "f" in the original paper. |
| 112 | stack_.push_back(vertex); |
| 113 | blocked_[vertex] = true; |
| 114 | |
| 115 | for (Vertex::SubgraphEdgeMap::iterator w = |
| 116 | subgraph_[vertex].subgraph_edges.begin(); |
| 117 | w != subgraph_[vertex].subgraph_edges.end(); ++w) { |
| 118 | if (*w == current_vertex_) { |
| 119 | // The original paper called for printing stack_ followed by |
| 120 | // current_vertex_ here, which is a cycle. Instead, we call |
| 121 | // HandleCircuit() to break it. |
| 122 | HandleCircuit(); |
| 123 | found = true; |
| 124 | } else if (!blocked_[*w]) { |
| 125 | if (Circuit(*w)) |
| 126 | found = true; |
| 127 | } |
| 128 | } |
| 129 | |
| 130 | if (found) { |
| 131 | Unblock(vertex); |
| 132 | } else { |
| 133 | for (Vertex::SubgraphEdgeMap::iterator w = |
| 134 | subgraph_[vertex].subgraph_edges.begin(); |
| 135 | w != subgraph_[vertex].subgraph_edges.end(); ++w) { |
| 136 | subgraph_[*w].subgraph_edges.insert(vertex); |
| 137 | } |
| 138 | } |
| 139 | CHECK_EQ(vertex, stack_.back()); |
| 140 | stack_.pop_back(); |
| 141 | return found; |
| 142 | } |
| 143 | |
| 144 | } // namespace chromeos_update_engine |