Andrew de los Reyes | 81ebcd8 | 2010-03-09 15:56:18 -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 <algorithm> |
| 6 | #include <vector> |
Chris Masone | 790e62e | 2010-08-12 10:41:18 -0700 | [diff] [blame^] | 7 | #include "base/logging.h" |
Andrew de los Reyes | 81ebcd8 | 2010-03-09 15:56:18 -0800 | [diff] [blame] | 8 | #include "update_engine/tarjan.h" |
| 9 | #include "update_engine/utils.h" |
| 10 | |
| 11 | using std::min; |
| 12 | using std::vector; |
| 13 | |
| 14 | namespace chromeos_update_engine { |
| 15 | |
| 16 | namespace { |
| 17 | const vector<Vertex>::size_type kInvalidIndex = -1; |
| 18 | } |
| 19 | |
| 20 | void TarjanAlgorithm::Execute(Vertex::Index vertex, |
| 21 | Graph* graph, |
| 22 | vector<Vertex::Index>* out) { |
| 23 | stack_.clear(); |
| 24 | components_.clear(); |
| 25 | index_ = 0; |
| 26 | for (Graph::iterator it = graph->begin(); it != graph->end(); ++it) |
| 27 | it->index = it->lowlink = kInvalidIndex; |
| 28 | required_vertex_ = vertex; |
| 29 | |
| 30 | Tarjan(vertex, graph); |
| 31 | if (!components_.empty()) |
| 32 | out->swap(components_[0]); |
| 33 | } |
| 34 | |
| 35 | void TarjanAlgorithm::Tarjan(Vertex::Index vertex, Graph* graph) { |
| 36 | CHECK_EQ((*graph)[vertex].index, kInvalidIndex); |
| 37 | (*graph)[vertex].index = index_; |
| 38 | (*graph)[vertex].lowlink = index_; |
| 39 | index_++; |
| 40 | stack_.push_back(vertex); |
| 41 | for (Vertex::EdgeMap::iterator it = (*graph)[vertex].out_edges.begin(); |
| 42 | it != (*graph)[vertex].out_edges.end(); ++it) { |
| 43 | Vertex::Index vertex_next = it->first; |
| 44 | if ((*graph)[vertex_next].index == kInvalidIndex) { |
| 45 | Tarjan(vertex_next, graph); |
| 46 | (*graph)[vertex].lowlink = min((*graph)[vertex].lowlink, |
| 47 | (*graph)[vertex_next].lowlink); |
| 48 | } else if (utils::VectorContainsValue(stack_, vertex_next)) { |
| 49 | (*graph)[vertex].lowlink = min((*graph)[vertex].lowlink, |
| 50 | (*graph)[vertex_next].index); |
| 51 | } |
| 52 | } |
| 53 | if ((*graph)[vertex].lowlink == (*graph)[vertex].index) { |
| 54 | vector<Vertex::Index> component; |
| 55 | Vertex::Index other_vertex; |
| 56 | do { |
| 57 | other_vertex = stack_.back(); |
| 58 | stack_.pop_back(); |
| 59 | component.push_back(other_vertex); |
| 60 | } while (other_vertex != vertex && !stack_.empty()); |
| 61 | |
| 62 | if (utils::VectorContainsValue(component, required_vertex_)) { |
| 63 | components_.resize(components_.size() + 1); |
| 64 | component.swap(components_.back()); |
| 65 | } |
| 66 | } |
| 67 | } |
| 68 | |
| 69 | } // namespace chromeos_update_engine |
| 70 | |