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