AU: Topological Sort.
Review URL: http://codereview.chromium.org/794003
diff --git a/SConstruct b/SConstruct
index f43c68f..e27871a 100644
--- a/SConstruct
+++ b/SConstruct
@@ -105,6 +105,7 @@
set_bootable_flag_action.cc
subprocess.cc
tarjan.cc
+ topological_sort.cc
update_check_action.cc
update_metadata.pb.cc
utils.cc""")
@@ -135,6 +136,7 @@
subprocess_unittest.cc
tarjan_unittest.cc
test_utils.cc
+ topological_sort_unittest.cc
update_check_action_unittest.cc
utils_unittest.cc""")
unittest_main = ['testrunner.cc']
diff --git a/topological_sort.cc b/topological_sort.cc
new file mode 100644
index 0000000..2e34144
--- /dev/null
+++ b/topological_sort.cc
@@ -0,0 +1,41 @@
+// Copyright (c) 2010 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "update_engine/topological_sort.h"
+#include <set>
+#include <vector>
+
+using std::set;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace {
+void TopologicalSortVisit(const Graph& graph,
+ set<Vertex::Index>* visited_nodes,
+ vector<Vertex::Index>* nodes,
+ Vertex::Index node) {
+ if (visited_nodes->find(node) != visited_nodes->end())
+ return;
+
+ visited_nodes->insert(node);
+ // Visit all children.
+ for (Vertex::EdgeMap::const_iterator it = graph[node].out_edges.begin();
+ it != graph[node].out_edges.end(); ++it) {
+ TopologicalSortVisit(graph, visited_nodes, nodes, it->first);
+ }
+ // Visit this node.
+ nodes->push_back(node);
+}
+} // namespace {}
+
+void TopologicalSort(const Graph& graph, vector<Vertex::Index>* out) {
+ set<Vertex::Index> visited_nodes;
+
+ for (Vertex::Index i = 0; i < graph.size(); i++) {
+ TopologicalSortVisit(graph, &visited_nodes, out, i);
+ }
+}
+
+} // namespace chromeos_update_engine
diff --git a/topological_sort.h b/topological_sort.h
new file mode 100644
index 0000000..d4a5446
--- /dev/null
+++ b/topological_sort.h
@@ -0,0 +1,30 @@
+// Copyright (c) 2010 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_TOPOLOGICAL_SORT_H__
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_TOPOLOGICAL_SORT_H__
+
+
+#include <vector>
+#include "update_engine/graph_types.h"
+
+namespace chromeos_update_engine {
+
+// Performs a topological sort on the directed graph 'graph' and stores
+// the nodes, in order visited, in 'out'.
+// For example, this graph:
+// A ---> C ----.
+// \ v
+// `--> B --> D
+// Might result in this in 'out':
+// out[0] = D
+// out[1] = B
+// out[2] = C
+// out[3] = A
+// Note: results are undefined if there is a cycle in the graph.
+void TopologicalSort(const Graph& graph, std::vector<Vertex::Index>* out);
+
+} // namespace chromeos_update_engine
+
+#endif // CHROMEOS_PLATFORM_UPDATE_ENGINE_TOPOLOGICAL_SORT_H__
diff --git a/topological_sort_unittest.cc b/topological_sort_unittest.cc
new file mode 100644
index 0000000..bddb0f0
--- /dev/null
+++ b/topological_sort_unittest.cc
@@ -0,0 +1,80 @@
+// Copyright (c) 2010 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <utility>
+#include <vector>
+#include <gtest/gtest.h>
+#include "update_engine/graph_types.h"
+#include "update_engine/topological_sort.h"
+
+using std::make_pair;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+class TopologicalSortTest : public ::testing::Test {};
+
+namespace {
+// Returns true if the value is found in vect. If found, the index is stored
+// in out_index if out_index is not null.
+template<typename T>
+bool IndexOf(const vector<T>& vect,
+ const T& value,
+ typename vector<T>::size_type* out_index) {
+ for (typename vector<T>::size_type i = 0; i < vect.size(); i++) {
+ if (vect[i] == value) {
+ if (out_index) {
+ *out_index = i;
+ }
+ return true;
+ }
+ }
+ return false;
+}
+} // namespace {}
+
+TEST(TopologicalSortTest, SimpleTest) {
+ int counter = 0;
+ const Vertex::Index n_a = counter++;
+ const Vertex::Index n_b = counter++;
+ const Vertex::Index n_c = counter++;
+ const Vertex::Index n_d = counter++;
+ const Vertex::Index n_e = counter++;
+ const Vertex::Index n_f = counter++;
+ const Vertex::Index n_g = counter++;
+ const Vertex::Index n_h = counter++;
+ const Vertex::Index n_i = counter++;
+ const Vertex::Index n_j = counter++;
+ const Graph::size_type kNodeCount = counter++;
+
+ Graph graph(kNodeCount);
+
+ graph[n_i].out_edges.insert(make_pair(n_j, EdgeProperties()));
+ graph[n_i].out_edges.insert(make_pair(n_c, EdgeProperties()));
+ graph[n_i].out_edges.insert(make_pair(n_e, EdgeProperties()));
+ graph[n_i].out_edges.insert(make_pair(n_h, EdgeProperties()));
+ graph[n_c].out_edges.insert(make_pair(n_b, EdgeProperties()));
+ graph[n_b].out_edges.insert(make_pair(n_a, EdgeProperties()));
+ graph[n_e].out_edges.insert(make_pair(n_d, EdgeProperties()));
+ graph[n_e].out_edges.insert(make_pair(n_g, EdgeProperties()));
+ graph[n_g].out_edges.insert(make_pair(n_d, EdgeProperties()));
+ graph[n_g].out_edges.insert(make_pair(n_f, EdgeProperties()));
+ graph[n_d].out_edges.insert(make_pair(n_a, EdgeProperties()));
+
+ vector<Vertex::Index> sorted;
+ TopologicalSort(graph, &sorted);
+
+ for (Vertex::Index i = 0; i < graph.size(); i++) {
+ vector<Vertex::Index>::size_type src_index = 0;
+ EXPECT_TRUE(IndexOf(sorted, i, &src_index));
+ for (Vertex::EdgeMap::const_iterator it = graph[i].out_edges.begin();
+ it != graph[i].out_edges.end(); ++it) {
+ vector<Vertex::Index>::size_type dst_index = 0;
+ EXPECT_TRUE(IndexOf(sorted, it->first, &dst_index));
+ EXPECT_LT(dst_index, src_index);
+ }
+ }
+}
+
+} // namespace chromeos_update_engine