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 31namespace chromeos_update_engine { 32 33class 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