Alex Deymo | aea4c1c | 2015-08-19 20:24:43 -0700 | [diff] [blame] | 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 | // |
Andrew de los Reyes | 5815155 | 2010-03-10 20:07:08 -0800 | [diff] [blame] | 16 | |
Alex Deymo | 161c4a1 | 2014-05-16 15:56:21 -0700 | [diff] [blame] | 17 | #include "update_engine/payload_generator/topological_sort.h" |
| 18 | |
Andrew de los Reyes | 5815155 | 2010-03-10 20:07:08 -0800 | [diff] [blame] | 19 | #include <set> |
| 20 | #include <vector> |
Alex Deymo | 161c4a1 | 2014-05-16 15:56:21 -0700 | [diff] [blame] | 21 | |
| 22 | #include <base/logging.h> |
Andrew de los Reyes | 5815155 | 2010-03-10 20:07:08 -0800 | [diff] [blame] | 23 | |
| 24 | using std::set; |
| 25 | using std::vector; |
| 26 | |
| 27 | namespace chromeos_update_engine { |
| 28 | |
| 29 | namespace { |
| 30 | void TopologicalSortVisit(const Graph& graph, |
| 31 | set<Vertex::Index>* visited_nodes, |
| 32 | vector<Vertex::Index>* nodes, |
| 33 | Vertex::Index node) { |
| 34 | if (visited_nodes->find(node) != visited_nodes->end()) |
| 35 | return; |
| 36 | |
| 37 | visited_nodes->insert(node); |
| 38 | // Visit all children. |
| 39 | for (Vertex::EdgeMap::const_iterator it = graph[node].out_edges.begin(); |
| 40 | it != graph[node].out_edges.end(); ++it) { |
| 41 | TopologicalSortVisit(graph, visited_nodes, nodes, it->first); |
| 42 | } |
| 43 | // Visit this node. |
Andrew de los Reyes | 5815155 | 2010-03-10 20:07:08 -0800 | [diff] [blame] | 44 | nodes->push_back(node); |
| 45 | } |
Alex Vakulenko | d2779df | 2014-06-16 13:19:00 -0700 | [diff] [blame] | 46 | } // namespace |
Andrew de los Reyes | 5815155 | 2010-03-10 20:07:08 -0800 | [diff] [blame] | 47 | |
| 48 | void TopologicalSort(const Graph& graph, vector<Vertex::Index>* out) { |
| 49 | set<Vertex::Index> visited_nodes; |
| 50 | |
| 51 | for (Vertex::Index i = 0; i < graph.size(); i++) { |
| 52 | TopologicalSortVisit(graph, &visited_nodes, out, i); |
| 53 | } |
| 54 | } |
| 55 | |
| 56 | } // namespace chromeos_update_engine |