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 #include "update_engine/topological_sort.h" | |
6 #include <set> | |
7 #include <vector> | |
8 | |
9 using std::set; | |
10 using std::vector; | |
11 | |
12 namespace chromeos_update_engine { | |
13 | |
14 void TopologicalSortVisit(const Graph& graph, | |
Daniel Erat
2010/03/11 01:31:49
make this function static
adlr
2010/03/11 04:12:08
did namespace {}
| |
15 set<Vertex::Index>* visited_nodes, | |
16 vector<Vertex::Index>* nodes, | |
17 Vertex::Index node) { | |
18 if (visited_nodes->find(node) != visited_nodes->end()) | |
19 return; | |
20 | |
21 visited_nodes->insert(node); | |
22 // Visit all children. | |
23 for (Vertex::EdgeMap::const_iterator it = graph[node].out_edges.begin(); | |
24 it != graph[node].out_edges.end(); ++it) { | |
25 TopologicalSortVisit(graph, visited_nodes, nodes, it->first); | |
26 } | |
27 // Visit this node. | |
28 nodes->push_back(node); | |
29 } | |
30 | |
31 void TopologicalSort(const Graph& graph, vector<Vertex::Index>* out) { | |
32 set<Vertex::Index> visited_nodes; | |
33 | |
34 for (Vertex::Index i = 0; i < graph.size(); i++) { | |
35 TopologicalSortVisit(graph, &visited_nodes, out, i); | |
36 } | |
37 } | |
38 | |
39 } // namespace chromeos_update_engine | |
OLD | NEW |