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_TOPOLOGICAL_SORT_H__ |
| 6 #define CHROMEOS_PLATFORM_UPDATE_ENGINE_TOPOLOGICAL_SORT_H__ |
| 7 |
| 8 |
| 9 #include <vector> |
| 10 #include "update_engine/graph_types.h" |
| 11 |
| 12 namespace chromeos_update_engine { |
| 13 |
| 14 // Performs a topological sort on the directed graph 'graph' and stores |
| 15 // the nodes, in order visited, in 'out'. |
| 16 // For example, this graph: |
| 17 // A ---> C ----. |
| 18 // \ v |
| 19 // `--> B --> D |
| 20 // Might result in this in 'out': |
| 21 // out[0] = D |
| 22 // out[1] = B |
| 23 // out[2] = C |
| 24 // out[3] = A |
| 25 // Note: results are undefined if there is a cycle in the graph. |
| 26 void TopologicalSort(const Graph& graph, std::vector<Vertex::Index>* out); |
| 27 |
| 28 } // namespace chromeos_update_engine |
| 29 |
| 30 #endif // CHROMEOS_PLATFORM_UPDATE_ENGINE_TOPOLOGICAL_SORT_H__ |
OLD | NEW |