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 #include "update_engine/payload_generator/topological_sort.h"
18
19 #include <set>
20 #include <vector>
21
22 #include <base/logging.h>
23
24 using std::set;
25 using std::vector;
26
27 namespace chromeos_update_engine {
28
29 namespace {
TopologicalSortVisit(const Graph & graph,set<Vertex::Index> * visited_nodes,vector<Vertex::Index> * nodes,Vertex::Index node)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.
44 nodes->push_back(node);
45 }
46 } // namespace
47
TopologicalSort(const Graph & graph,vector<Vertex::Index> * out)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
57