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
