summaryrefslogtreecommitdiff
path: root/absl/synchronization/internal/graphcycles_test.cc
diff options
context:
space:
mode:
authorGravatar misterg <misterg@google.com>2017-09-19 16:54:40 -0400
committerGravatar misterg <misterg@google.com>2017-09-19 16:54:40 -0400
commitc2e754829628d1e9b7a16b3389cfdace76950fdf (patch)
tree5a7f056f44e27c30e10025113b644f0b3b5801fc /absl/synchronization/internal/graphcycles_test.cc
Initial Commit
Diffstat (limited to 'absl/synchronization/internal/graphcycles_test.cc')
-rw-r--r--absl/synchronization/internal/graphcycles_test.cc471
1 files changed, 471 insertions, 0 deletions
diff --git a/absl/synchronization/internal/graphcycles_test.cc b/absl/synchronization/internal/graphcycles_test.cc
new file mode 100644
index 00000000..734f2770
--- /dev/null
+++ b/absl/synchronization/internal/graphcycles_test.cc
@@ -0,0 +1,471 @@
+// Copyright 2017 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+// Copyright 2007 Google, Inc.
+// All rights reserved.
+
+// Author: Mike Burrows
+
+// A test for the GraphCycles interface.
+
+// This test is testing a component of //third_party/absl. As written it
+// heavily uses logging, including VLOG, so this test can't ship with Abseil.
+// We're leaving it here until Abseil gets base/logging.h in a future release.
+#include "absl/synchronization/internal/graphcycles.h"
+
+#include <map>
+#include <random>
+#include <vector>
+#include <unordered_set>
+
+#include "gtest/gtest.h"
+#include "absl/base/internal/raw_logging.h"
+#include "absl/base/macros.h"
+
+namespace absl {
+namespace synchronization_internal {
+
+// We emulate a GraphCycles object with a node vector and an edge vector.
+// We then compare the two implementations.
+
+using Nodes = std::vector<int>;
+struct Edge {
+ int from;
+ int to;
+};
+using Edges = std::vector<Edge>;
+using RandomEngine = std::mt19937_64;
+
+// Mapping from integer index to GraphId.
+typedef std::map<int, GraphId> IdMap;
+static GraphId Get(const IdMap& id, int num) {
+ auto iter = id.find(num);
+ return (iter == id.end()) ? InvalidGraphId() : iter->second;
+}
+
+// Return whether "to" is reachable from "from".
+static bool IsReachable(Edges *edges, int from, int to,
+ std::unordered_set<int> *seen) {
+ seen->insert(from); // we are investigating "from"; don't do it again
+ if (from == to) return true;
+ for (const auto &edge : *edges) {
+ if (edge.from == from) {
+ if (edge.to == to) { // success via edge directly
+ return true;
+ } else if (seen->find(edge.to) == seen->end() && // success via edge
+ IsReachable(edges, edge.to, to, seen)) {
+ return true;
+ }
+ }
+ }
+ return false;
+}
+
+static void PrintEdges(Edges *edges) {
+ ABSL_RAW_LOG(INFO, "EDGES (%zu)", edges->size());
+ for (const auto &edge : *edges) {
+ int a = edge.from;
+ int b = edge.to;
+ ABSL_RAW_LOG(INFO, "%d %d", a, b);
+ }
+ ABSL_RAW_LOG(INFO, "---");
+}
+
+static void PrintGCEdges(Nodes *nodes, const IdMap &id, GraphCycles *gc) {
+ ABSL_RAW_LOG(INFO, "GC EDGES");
+ for (int a : *nodes) {
+ for (int b : *nodes) {
+ if (gc->HasEdge(Get(id, a), Get(id, b))) {
+ ABSL_RAW_LOG(INFO, "%d %d", a, b);
+ }
+ }
+ }
+ ABSL_RAW_LOG(INFO, "---");
+}
+
+static void PrintTransitiveClosure(Nodes *nodes, Edges *edges) {
+ ABSL_RAW_LOG(INFO, "Transitive closure");
+ for (int a : *nodes) {
+ for (int b : *nodes) {
+ std::unordered_set<int> seen;
+ if (IsReachable(edges, a, b, &seen)) {
+ ABSL_RAW_LOG(INFO, "%d %d", a, b);
+ }
+ }
+ }
+ ABSL_RAW_LOG(INFO, "---");
+}
+
+static void PrintGCTransitiveClosure(Nodes *nodes, const IdMap &id,
+ GraphCycles *gc) {
+ ABSL_RAW_LOG(INFO, "GC Transitive closure");
+ for (int a : *nodes) {
+ for (int b : *nodes) {
+ if (gc->IsReachable(Get(id, a), Get(id, b))) {
+ ABSL_RAW_LOG(INFO, "%d %d", a, b);
+ }
+ }
+ }
+ ABSL_RAW_LOG(INFO, "---");
+}
+
+static void CheckTransitiveClosure(Nodes *nodes, Edges *edges, const IdMap &id,
+ GraphCycles *gc) {
+ std::unordered_set<int> seen;
+ for (const auto &a : *nodes) {
+ for (const auto &b : *nodes) {
+ seen.clear();
+ bool gc_reachable = gc->IsReachable(Get(id, a), Get(id, b));
+ bool reachable = IsReachable(edges, a, b, &seen);
+ if (gc_reachable != reachable) {
+ PrintEdges(edges);
+ PrintGCEdges(nodes, id, gc);
+ PrintTransitiveClosure(nodes, edges);
+ PrintGCTransitiveClosure(nodes, id, gc);
+ ABSL_RAW_LOG(FATAL, "gc_reachable %s reachable %s a %d b %d",
+ gc_reachable ? "true" : "false",
+ reachable ? "true" : "false", a, b);
+ }
+ }
+ }
+}
+
+static void CheckEdges(Nodes *nodes, Edges *edges, const IdMap &id,
+ GraphCycles *gc) {
+ int count = 0;
+ for (const auto &edge : *edges) {
+ int a = edge.from;
+ int b = edge.to;
+ if (!gc->HasEdge(Get(id, a), Get(id, b))) {
+ PrintEdges(edges);
+ PrintGCEdges(nodes, id, gc);
+ ABSL_RAW_LOG(FATAL, "!gc->HasEdge(%d, %d)", a, b);
+ }
+ }
+ for (const auto &a : *nodes) {
+ for (const auto &b : *nodes) {
+ if (gc->HasEdge(Get(id, a), Get(id, b))) {
+ count++;
+ }
+ }
+ }
+ if (count != edges->size()) {
+ PrintEdges(edges);
+ PrintGCEdges(nodes, id, gc);
+ ABSL_RAW_LOG(FATAL, "edges->size() %zu count %d", edges->size(), count);
+ }
+}
+
+static void CheckInvariants(const GraphCycles &gc) {
+ if (ABSL_PREDICT_FALSE(!gc.CheckInvariants()))
+ ABSL_RAW_LOG(FATAL, "CheckInvariants");
+}
+
+// Returns the index of a randomly chosen node in *nodes.
+// Requires *nodes be non-empty.
+static int RandomNode(RandomEngine* rng, Nodes *nodes) {
+ std::uniform_int_distribution<int> uniform(0, nodes->size()-1);
+ return uniform(*rng);
+}
+
+// Returns the index of a randomly chosen edge in *edges.
+// Requires *edges be non-empty.
+static int RandomEdge(RandomEngine* rng, Edges *edges) {
+ std::uniform_int_distribution<int> uniform(0, edges->size()-1);
+ return uniform(*rng);
+}
+
+// Returns the index of edge (from, to) in *edges or -1 if it is not in *edges.
+static int EdgeIndex(Edges *edges, int from, int to) {
+ int i = 0;
+ while (i != edges->size() &&
+ ((*edges)[i].from != from || (*edges)[i].to != to)) {
+ i++;
+ }
+ return i == edges->size()? -1 : i;
+}
+
+TEST(GraphCycles, RandomizedTest) {
+ int next_node = 0;
+ Nodes nodes;
+ Edges edges; // from, to
+ IdMap id;
+ GraphCycles graph_cycles;
+ static const int kMaxNodes = 7; // use <= 7 nodes to keep test short
+ static const int kDataOffset = 17; // an offset to the node-specific data
+ int n = 100000;
+ int op = 0;
+ RandomEngine rng(testing::UnitTest::GetInstance()->random_seed());
+ std::uniform_int_distribution<int> uniform(0, 5);
+
+ auto ptr = [](intptr_t i) {
+ return reinterpret_cast<void*>(i + kDataOffset);
+ };
+
+ for (int iter = 0; iter != n; iter++) {
+ for (const auto &node : nodes) {
+ ASSERT_EQ(graph_cycles.Ptr(Get(id, node)), ptr(node)) << " node " << node;
+ }
+ CheckEdges(&nodes, &edges, id, &graph_cycles);
+ CheckTransitiveClosure(&nodes, &edges, id, &graph_cycles);
+ op = uniform(rng);
+ switch (op) {
+ case 0: // Add a node
+ if (nodes.size() < kMaxNodes) {
+ int new_node = next_node++;
+ GraphId new_gnode = graph_cycles.GetId(ptr(new_node));
+ ASSERT_NE(new_gnode, InvalidGraphId());
+ id[new_node] = new_gnode;
+ ASSERT_EQ(ptr(new_node), graph_cycles.Ptr(new_gnode));
+ nodes.push_back(new_node);
+ }
+ break;
+
+ case 1: // Remove a node
+ if (nodes.size() > 0) {
+ int node_index = RandomNode(&rng, &nodes);
+ int node = nodes[node_index];
+ nodes[node_index] = nodes.back();
+ nodes.pop_back();
+ graph_cycles.RemoveNode(ptr(node));
+ ASSERT_EQ(graph_cycles.Ptr(Get(id, node)), nullptr);
+ id.erase(node);
+ int i = 0;
+ while (i != edges.size()) {
+ if (edges[i].from == node || edges[i].to == node) {
+ edges[i] = edges.back();
+ edges.pop_back();
+ } else {
+ i++;
+ }
+ }
+ }
+ break;
+
+ case 2: // Add an edge
+ if (nodes.size() > 0) {
+ int from = RandomNode(&rng, &nodes);
+ int to = RandomNode(&rng, &nodes);
+ if (EdgeIndex(&edges, nodes[from], nodes[to]) == -1) {
+ if (graph_cycles.InsertEdge(id[nodes[from]], id[nodes[to]])) {
+ Edge new_edge;
+ new_edge.from = nodes[from];
+ new_edge.to = nodes[to];
+ edges.push_back(new_edge);
+ } else {
+ std::unordered_set<int> seen;
+ ASSERT_TRUE(IsReachable(&edges, nodes[to], nodes[from], &seen))
+ << "Edge " << nodes[to] << "->" << nodes[from];
+ }
+ }
+ }
+ break;
+
+ case 3: // Remove an edge
+ if (edges.size() > 0) {
+ int i = RandomEdge(&rng, &edges);
+ int from = edges[i].from;
+ int to = edges[i].to;
+ ASSERT_EQ(i, EdgeIndex(&edges, from, to));
+ edges[i] = edges.back();
+ edges.pop_back();
+ ASSERT_EQ(-1, EdgeIndex(&edges, from, to));
+ graph_cycles.RemoveEdge(id[from], id[to]);
+ }
+ break;
+
+ case 4: // Check a path
+ if (nodes.size() > 0) {
+ int from = RandomNode(&rng, &nodes);
+ int to = RandomNode(&rng, &nodes);
+ GraphId path[2*kMaxNodes];
+ int path_len = graph_cycles.FindPath(id[nodes[from]], id[nodes[to]],
+ ABSL_ARRAYSIZE(path), path);
+ std::unordered_set<int> seen;
+ bool reachable = IsReachable(&edges, nodes[from], nodes[to], &seen);
+ bool gc_reachable =
+ graph_cycles.IsReachable(Get(id, nodes[from]), Get(id, nodes[to]));
+ ASSERT_EQ(path_len != 0, reachable);
+ ASSERT_EQ(path_len != 0, gc_reachable);
+ // In the following line, we add one because a node can appear
+ // twice, if the path is from that node to itself, perhaps via
+ // every other node.
+ ASSERT_LE(path_len, kMaxNodes + 1);
+ if (path_len != 0) {
+ ASSERT_EQ(id[nodes[from]], path[0]);
+ ASSERT_EQ(id[nodes[to]], path[path_len-1]);
+ for (int i = 1; i < path_len; i++) {
+ ASSERT_TRUE(graph_cycles.HasEdge(path[i-1], path[i]));
+ }
+ }
+ }
+ break;
+
+ case 5: // Check invariants
+ CheckInvariants(graph_cycles);
+ break;
+
+ default:
+ ABSL_RAW_LOG(FATAL, "op %d", op);
+ }
+
+ // Very rarely, test graph expansion by adding then removing many nodes.
+ std::bernoulli_distribution one_in_1024(1.0 / 1024);
+ if (one_in_1024(rng)) {
+ CheckEdges(&nodes, &edges, id, &graph_cycles);
+ CheckTransitiveClosure(&nodes, &edges, id, &graph_cycles);
+ for (int i = 0; i != 256; i++) {
+ int new_node = next_node++;
+ GraphId new_gnode = graph_cycles.GetId(ptr(new_node));
+ ASSERT_NE(InvalidGraphId(), new_gnode);
+ id[new_node] = new_gnode;
+ ASSERT_EQ(ptr(new_node), graph_cycles.Ptr(new_gnode));
+ for (const auto &node : nodes) {
+ ASSERT_NE(node, new_node);
+ }
+ nodes.push_back(new_node);
+ }
+ for (int i = 0; i != 256; i++) {
+ ASSERT_GT(nodes.size(), 0);
+ int node_index = RandomNode(&rng, &nodes);
+ int node = nodes[node_index];
+ nodes[node_index] = nodes.back();
+ nodes.pop_back();
+ graph_cycles.RemoveNode(ptr(node));
+ id.erase(node);
+ int j = 0;
+ while (j != edges.size()) {
+ if (edges[j].from == node || edges[j].to == node) {
+ edges[j] = edges.back();
+ edges.pop_back();
+ } else {
+ j++;
+ }
+ }
+ }
+ CheckInvariants(graph_cycles);
+ }
+ }
+}
+
+class GraphCyclesTest : public ::testing::Test {
+ public:
+ IdMap id_;
+ GraphCycles g_;
+
+ static void* Ptr(int i) {
+ return reinterpret_cast<void*>(static_cast<uintptr_t>(i));
+ }
+
+ static int Num(void* ptr) {
+ return static_cast<int>(reinterpret_cast<uintptr_t>(ptr));
+ }
+
+ // Test relies on ith NewNode() call returning Node numbered i
+ GraphCyclesTest() {
+ for (int i = 0; i < 100; i++) {
+ id_[i] = g_.GetId(Ptr(i));
+ }
+ CheckInvariants(g_);
+ }
+
+ bool AddEdge(int x, int y) {
+ return g_.InsertEdge(Get(id_, x), Get(id_, y));
+ }
+
+ void AddMultiples() {
+ // For every node x > 0: add edge to 2*x, 3*x
+ for (int x = 1; x < 25; x++) {
+ EXPECT_TRUE(AddEdge(x, 2*x)) << x;
+ EXPECT_TRUE(AddEdge(x, 3*x)) << x;
+ }
+ CheckInvariants(g_);
+ }
+
+ std::string Path(int x, int y) {
+ GraphId path[5];
+ int np = g_.FindPath(Get(id_, x), Get(id_, y), ABSL_ARRAYSIZE(path), path);
+ std::string result;
+ for (int i = 0; i < np; i++) {
+ if (i >= ABSL_ARRAYSIZE(path)) {
+ result += " ...";
+ break;
+ }
+ if (!result.empty()) result.push_back(' ');
+ char buf[20];
+ snprintf(buf, sizeof(buf), "%d", Num(g_.Ptr(path[i])));
+ result += buf;
+ }
+ return result;
+ }
+};
+
+TEST_F(GraphCyclesTest, NoCycle) {
+ AddMultiples();
+ CheckInvariants(g_);
+}
+
+TEST_F(GraphCyclesTest, SimpleCycle) {
+ AddMultiples();
+ EXPECT_FALSE(AddEdge(8, 4));
+ EXPECT_EQ("4 8", Path(4, 8));
+ CheckInvariants(g_);
+}
+
+TEST_F(GraphCyclesTest, IndirectCycle) {
+ AddMultiples();
+ EXPECT_TRUE(AddEdge(16, 9));
+ CheckInvariants(g_);
+ EXPECT_FALSE(AddEdge(9, 2));
+ EXPECT_EQ("2 4 8 16 9", Path(2, 9));
+ CheckInvariants(g_);
+}
+
+TEST_F(GraphCyclesTest, LongPath) {
+ ASSERT_TRUE(AddEdge(2, 4));
+ ASSERT_TRUE(AddEdge(4, 6));
+ ASSERT_TRUE(AddEdge(6, 8));
+ ASSERT_TRUE(AddEdge(8, 10));
+ ASSERT_TRUE(AddEdge(10, 12));
+ ASSERT_FALSE(AddEdge(12, 2));
+ EXPECT_EQ("2 4 6 8 10 ...", Path(2, 12));
+ CheckInvariants(g_);
+}
+
+TEST_F(GraphCyclesTest, RemoveNode) {
+ ASSERT_TRUE(AddEdge(1, 2));
+ ASSERT_TRUE(AddEdge(2, 3));
+ ASSERT_TRUE(AddEdge(3, 4));
+ ASSERT_TRUE(AddEdge(4, 5));
+ g_.RemoveNode(g_.Ptr(id_[3]));
+ id_.erase(3);
+ ASSERT_TRUE(AddEdge(5, 1));
+}
+
+TEST_F(GraphCyclesTest, ManyEdges) {
+ const int N = 50;
+ for (int i = 0; i < N; i++) {
+ for (int j = 1; j < N; j++) {
+ ASSERT_TRUE(AddEdge(i, i+j));
+ }
+ }
+ CheckInvariants(g_);
+ ASSERT_TRUE(AddEdge(2*N-1, 0));
+ CheckInvariants(g_);
+ ASSERT_FALSE(AddEdge(10, 9));
+ CheckInvariants(g_);
+}
+
+} // namespace synchronization_internal
+} // namespace absl