AU: Tarjan's algorithm.
Add an implementation of Tarjan's algorith for finding Strongly
Connected Components in a graph. This version is slightly modified: it
takes in a vertex in addition to the graph and returns only the SCC
containing that vertex.
Review URL: http://codereview.chromium.org/657055
diff --git a/SConstruct b/SConstruct
index e92a895..5bfbec7 100644
--- a/SConstruct
+++ b/SConstruct
@@ -103,6 +103,7 @@
postinstall_runner_action.cc
set_bootable_flag_action.cc
subprocess.cc
+ tarjan.cc
update_check_action.cc
update_metadata.pb.cc
utils.cc""")
@@ -130,6 +131,7 @@
postinstall_runner_action_unittest.cc
set_bootable_flag_action_unittest.cc
subprocess_unittest.cc
+ tarjan_unittest.cc
test_utils.cc
update_check_action_unittest.cc
utils_unittest.cc""")
diff --git a/tarjan.cc b/tarjan.cc
new file mode 100644
index 0000000..aaca7d0
--- /dev/null
+++ b/tarjan.cc
@@ -0,0 +1,70 @@
+// 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 <algorithm>
+#include <vector>
+#include "chromeos/obsolete_logging.h"
+#include "update_engine/tarjan.h"
+#include "update_engine/utils.h"
+
+using std::min;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace {
+const vector<Vertex>::size_type kInvalidIndex = -1;
+}
+
+void TarjanAlgorithm::Execute(Vertex::Index vertex,
+ Graph* graph,
+ vector<Vertex::Index>* out) {
+ stack_.clear();
+ components_.clear();
+ index_ = 0;
+ for (Graph::iterator it = graph->begin(); it != graph->end(); ++it)
+ it->index = it->lowlink = kInvalidIndex;
+ required_vertex_ = vertex;
+
+ Tarjan(vertex, graph);
+ if (!components_.empty())
+ out->swap(components_[0]);
+}
+
+void TarjanAlgorithm::Tarjan(Vertex::Index vertex, Graph* graph) {
+ CHECK_EQ((*graph)[vertex].index, kInvalidIndex);
+ (*graph)[vertex].index = index_;
+ (*graph)[vertex].lowlink = index_;
+ index_++;
+ stack_.push_back(vertex);
+ for (Vertex::EdgeMap::iterator it = (*graph)[vertex].out_edges.begin();
+ it != (*graph)[vertex].out_edges.end(); ++it) {
+ Vertex::Index vertex_next = it->first;
+ if ((*graph)[vertex_next].index == kInvalidIndex) {
+ Tarjan(vertex_next, graph);
+ (*graph)[vertex].lowlink = min((*graph)[vertex].lowlink,
+ (*graph)[vertex_next].lowlink);
+ } else if (utils::VectorContainsValue(stack_, vertex_next)) {
+ (*graph)[vertex].lowlink = min((*graph)[vertex].lowlink,
+ (*graph)[vertex_next].index);
+ }
+ }
+ if ((*graph)[vertex].lowlink == (*graph)[vertex].index) {
+ vector<Vertex::Index> component;
+ Vertex::Index other_vertex;
+ do {
+ other_vertex = stack_.back();
+ stack_.pop_back();
+ component.push_back(other_vertex);
+ } while (other_vertex != vertex && !stack_.empty());
+
+ if (utils::VectorContainsValue(component, required_vertex_)) {
+ components_.resize(components_.size() + 1);
+ component.swap(components_.back());
+ }
+ }
+}
+
+} // namespace chromeos_update_engine
+
diff --git a/tarjan.h b/tarjan.h
new file mode 100644
index 0000000..1a80a95
--- /dev/null
+++ b/tarjan.h
@@ -0,0 +1,39 @@
+// 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_TARJAN_H__
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_TARJAN_H__
+
+// This is an implemenation of Tarjan's algorithm which finds all
+// Strongly Connected Components in a graph.
+
+// Note: a true Tarjan algorithm would find all strongly connected components
+// in the graph. This implementation will only find the strongly connected
+// component containing the vertex passed in.
+
+#include <vector>
+#include "update_engine/graph_types.h"
+
+namespace chromeos_update_engine {
+
+class TarjanAlgorithm {
+ public:
+ TarjanAlgorithm() : index_(0), required_vertex_(0) {}
+
+ // 'out' is set to the result if there is one, otherwise it's untouched.
+ void Execute(Vertex::Index vertex,
+ Graph* graph,
+ std::vector<Vertex::Index>* out);
+ private:
+ void Tarjan(Vertex::Index vertex, Graph* graph);
+
+ Vertex::Index index_;
+ Vertex::Index required_vertex_;
+ std::vector<Vertex::Index> stack_;
+ std::vector<std::vector<Vertex::Index> > components_;
+};
+
+} // namespace chromeos_update_engine
+
+#endif // CHROMEOS_PLATFORM_UPDATE_ENGINE_TARJAN_H__
diff --git a/tarjan_unittest.cc b/tarjan_unittest.cc
new file mode 100644
index 0000000..9c4d7a8
--- /dev/null
+++ b/tarjan_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 <gtest/gtest.h>
+#include "chromeos/obsolete_logging.h"
+#include "update_engine/graph_types.h"
+#include "update_engine/tarjan.h"
+#include "update_engine/utils.h"
+
+using std::make_pair;
+using std::pair;
+using std::set;
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+class TarjanAlgorithmTest : public ::testing::Test {};
+
+TEST(TarjanAlgorithmTest, SimpleTest) {
+ const Vertex::Index n_a = 0;
+ const Vertex::Index n_b = 1;
+ const Vertex::Index n_c = 2;
+ const Vertex::Index n_d = 3;
+ const Vertex::Index n_e = 4;
+ const Vertex::Index n_f = 5;
+ const Vertex::Index n_g = 6;
+ const Vertex::Index n_h = 7;
+ const Graph::size_type kNodeCount = 8;
+
+ Graph graph(kNodeCount);
+
+ graph[n_a].out_edges.insert(make_pair(n_e, EdgeProperties()));
+ graph[n_a].out_edges.insert(make_pair(n_f, EdgeProperties()));
+ graph[n_b].out_edges.insert(make_pair(n_a, EdgeProperties()));
+ graph[n_c].out_edges.insert(make_pair(n_d, EdgeProperties()));
+ graph[n_d].out_edges.insert(make_pair(n_e, EdgeProperties()));
+ graph[n_d].out_edges.insert(make_pair(n_f, EdgeProperties()));
+ graph[n_e].out_edges.insert(make_pair(n_b, EdgeProperties()));
+ graph[n_e].out_edges.insert(make_pair(n_c, EdgeProperties()));
+ graph[n_e].out_edges.insert(make_pair(n_f, EdgeProperties()));
+ graph[n_f].out_edges.insert(make_pair(n_g, EdgeProperties()));
+ graph[n_g].out_edges.insert(make_pair(n_h, EdgeProperties()));
+ graph[n_h].out_edges.insert(make_pair(n_g, EdgeProperties()));
+
+ TarjanAlgorithm tarjan;
+
+ for (Vertex::Index i = n_a; i <= n_e; i++) {
+ vector<Vertex::Index> vertex_indexes;
+ tarjan.Execute(i, &graph, &vertex_indexes);
+
+ EXPECT_EQ(5, vertex_indexes.size());
+ EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_a));
+ EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_b));
+ EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_c));
+ EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_d));
+ EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_e));
+ }
+
+ {
+ vector<Vertex::Index> vertex_indexes;
+ tarjan.Execute(n_f, &graph, &vertex_indexes);
+
+ EXPECT_EQ(1, vertex_indexes.size());
+ EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_f));
+ }
+
+ for (Vertex::Index i = n_g; i <= n_h; i++) {
+ vector<Vertex::Index> vertex_indexes;
+ tarjan.Execute(i, &graph, &vertex_indexes);
+
+ EXPECT_EQ(2, vertex_indexes.size());
+ EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_g));
+ EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_h));
+ }
+}
+
+} // namespace chromeos_update_engine
diff --git a/utils.h b/utils.h
index 9354ba5..22a1ce8 100644
--- a/utils.h
+++ b/utils.h
@@ -5,6 +5,7 @@
#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_UTILS_H__
#define CHROMEOS_PLATFORM_UPDATE_ENGINE_UTILS_H__
+#include <algorithm>
#include <set>
#include <string>
#include <vector>