1 // 2 // Copyright (C) 2010 The Android Open Source Project 3 // 4 // Licensed under the Apache License, Version 2.0 (the "License"); 5 // you may not use this file except in compliance with the License. 6 // You may obtain a copy of the License at 7 // 8 // http://www.apache.org/licenses/LICENSE-2.0 9 // 10 // Unless required by applicable law or agreed to in writing, software 11 // distributed under the License is distributed on an "AS IS" BASIS, 12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 // See the License for the specific language governing permissions and 14 // limitations under the License. 15 // 16 #include "update_engine/payload_generator/tarjan.h" 17 18 #include <algorithm> 19 #include <vector> 20 21 #include <base/logging.h> 22 23 #include "update_engine/common/utils.h" 24 25 using std::min; 26 using std::vector; 27 28 namespace chromeos_update_engine { 29 30 namespace { 31 const vector<Vertex>::size_type kInvalidIndex = -1; 32 } 33 34 void TarjanAlgorithm::Execute(Vertex::Index vertex, 35 Graph* graph, 36 vector<Vertex::Index>* out) { 37 stack_.clear(); 38 components_.clear(); 39 index_ = 0; 40 for (Graph::iterator it = graph->begin(); it != graph->end(); ++it) 41 it->index = it->lowlink = kInvalidIndex; 42 required_vertex_ = vertex; 43 44 Tarjan(vertex, graph); 45 if (!components_.empty()) 46 out->swap(components_[0]); 47 } 48 49 void TarjanAlgorithm::Tarjan(Vertex::Index vertex, Graph* graph) { 50 CHECK_EQ((*graph)[vertex].index, kInvalidIndex); 51 (*graph)[vertex].index = index_; 52 (*graph)[vertex].lowlink = index_; 53 index_++; 54 stack_.push_back(vertex); 55 for (Vertex::EdgeMap::iterator it = (*graph)[vertex].out_edges.begin(); 56 it != (*graph)[vertex].out_edges.end(); ++it) { 57 Vertex::Index vertex_next = it->first; 58 if ((*graph)[vertex_next].index == kInvalidIndex) { 59 Tarjan(vertex_next, graph); 60 (*graph)[vertex].lowlink = min((*graph)[vertex].lowlink, 61 (*graph)[vertex_next].lowlink); 62 } else if (utils::VectorContainsValue(stack_, vertex_next)) { 63 (*graph)[vertex].lowlink = min((*graph)[vertex].lowlink, 64 (*graph)[vertex_next].index); 65 } 66 } 67 if ((*graph)[vertex].lowlink == (*graph)[vertex].index) { 68 vector<Vertex::Index> component; 69 Vertex::Index other_vertex; 70 do { 71 other_vertex = stack_.back(); 72 stack_.pop_back(); 73 component.push_back(other_vertex); 74 } while (other_vertex != vertex && !stack_.empty()); 75 76 if (utils::VectorContainsValue(component, required_vertex_)) { 77 components_.resize(components_.size() + 1); 78 component.swap(components_.back()); 79 } 80 } 81 } 82 83 } // namespace chromeos_update_engine 84
