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 | #include "update_engine/topological_sort.h" |
| 6 | #include <set> |
| 7 | #include <vector> |
Andrew de los Reyes | b10320d | 2010-03-31 16:44:44 -0700 | [diff] [blame] | 8 | #include "base/logging.h" |
Andrew de los Reyes | 5815155 | 2010-03-10 20:07:08 -0800 | [diff] [blame] | 9 | |
| 10 | using std::set; |
| 11 | using std::vector; |
| 12 | |
| 13 | namespace chromeos_update_engine { |
| 14 | |
| 15 | namespace { |
| 16 | void TopologicalSortVisit(const Graph& graph, |
| 17 | set<Vertex::Index>* visited_nodes, |
| 18 | vector<Vertex::Index>* nodes, |
| 19 | Vertex::Index node) { |
| 20 | if (visited_nodes->find(node) != visited_nodes->end()) |
| 21 | return; |
| 22 | |
| 23 | visited_nodes->insert(node); |
| 24 | // Visit all children. |
| 25 | for (Vertex::EdgeMap::const_iterator it = graph[node].out_edges.begin(); |
| 26 | it != graph[node].out_edges.end(); ++it) { |
| 27 | TopologicalSortVisit(graph, visited_nodes, nodes, it->first); |
| 28 | } |
| 29 | // Visit this node. |
Andrew de los Reyes | 5815155 | 2010-03-10 20:07:08 -0800 | [diff] [blame] | 30 | nodes->push_back(node); |
| 31 | } |
| 32 | } // namespace {} |
| 33 | |
| 34 | void TopologicalSort(const Graph& graph, vector<Vertex::Index>* out) { |
| 35 | set<Vertex::Index> visited_nodes; |
| 36 | |
| 37 | for (Vertex::Index i = 0; i < graph.size(); i++) { |
| 38 | TopologicalSortVisit(graph, &visited_nodes, out, i); |
| 39 | } |
| 40 | } |
| 41 | |
| 42 | } // namespace chromeos_update_engine |