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 <algorithm> |
| 6 #include <vector> |
| 7 #include "chromeos/obsolete_logging.h" |
| 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 |
OLD | NEW |