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 17 #ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_TARJAN_H_ 18 #define UPDATE_ENGINE_PAYLOAD_GENERATOR_TARJAN_H_ 19 20 // This is an implementation of Tarjan's algorithm which finds all 21 // Strongly Connected Components in a graph. 22 23 // Note: a true Tarjan algorithm would find all strongly connected components 24 // in the graph. This implementation will only find the strongly connected 25 // component containing the vertex passed in. 26 27 #include <vector> 28 29 #include "update_engine/payload_generator/graph_types.h" 30 31 namespace chromeos_update_engine { 32 33 class TarjanAlgorithm { 34 public: 35 TarjanAlgorithm() : index_(0), required_vertex_(0) {} 36 37 // 'out' is set to the result if there is one, otherwise it's untouched. 38 void Execute(Vertex::Index vertex, 39 Graph* graph, 40 std::vector<Vertex::Index>* out); 41 private: 42 void Tarjan(Vertex::Index vertex, Graph* graph); 43 44 Vertex::Index index_; 45 Vertex::Index required_vertex_; 46 std::vector<Vertex::Index> stack_; 47 std::vector<std::vector<Vertex::Index>> components_; 48 }; 49 50 } // namespace chromeos_update_engine 51 52 #endif // UPDATE_ENGINE_PAYLOAD_GENERATOR_TARJAN_H_ 53
