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 #ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_TARJAN_H__ |
| 6 #define CHROMEOS_PLATFORM_UPDATE_ENGINE_TARJAN_H__ |
| 7 |
| 8 // This is an implemenation 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 #include "update_engine/graph_types.h" |
| 17 |
| 18 namespace chromeos_update_engine { |
| 19 |
| 20 class TarjanAlgorithm { |
| 21 public: |
| 22 TarjanAlgorithm() : index_(0), required_vertex_(0) {} |
| 23 |
| 24 // 'out' is set to the result if there is one, otherwise it's untouched. |
| 25 void Execute(Vertex::Index vertex, |
| 26 Graph* graph, |
| 27 std::vector<Vertex::Index>* out); |
| 28 private: |
| 29 void Tarjan(Vertex::Index vertex, Graph* graph); |
| 30 |
| 31 Vertex::Index index_; |
| 32 Vertex::Index required_vertex_; |
| 33 std::vector<Vertex::Index> stack_; |
| 34 std::vector<std::vector<Vertex::Index> > components_; |
| 35 }; |
| 36 |
| 37 } // namespace chromeos_update_engine |
| 38 |
| 39 #endif // CHROMEOS_PLATFORM_UPDATE_ENGINE_TARJAN_H__ |
OLD | NEW |