| Andrew de los Reyes | 5815155 | 2010-03-10 20:07:08 -0800 | [diff] [blame] | 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__ |