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