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 
24 namespace 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.
38 void 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