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_TOPOLOGICAL_SORT_H_
18#define UPDATE_ENGINE_PAYLOAD_GENERATOR_TOPOLOGICAL_SORT_H_
19
20#include <vector>
21
22#include "update_engine/payload_generator/graph_types.h"
23
24namespace chromeos_update_engine {
25
26// Performs a topological sort on the directed graph 'graph' and stores
27// the nodes, in order visited, in 'out'.
28// For example, this graph:
29// A ---> C ----.
30//  \           v
31//   `--> B --> D
32// Might result in this in 'out':
33// out[0] = D
34// out[1] = B
35// out[2] = C
36// out[3] = A
37// Note: results are undefined if there is a cycle in the graph.
38void TopologicalSort(const Graph& graph, std::vector<Vertex::Index>* out);
39
40}  // namespace chromeos_update_engine
41
42#endif  // UPDATE_ENGINE_PAYLOAD_GENERATOR_TOPOLOGICAL_SORT_H_
43