graphcycles_test.cc
Go to the documentation of this file.
1 // Copyright 2017 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 
16 
17 #include <map>
18 #include <random>
19 #include <unordered_set>
20 #include <utility>
21 #include <vector>
22 
23 #include "gtest/gtest.h"
25 #include "absl/base/macros.h"
26 
27 namespace absl {
28 namespace synchronization_internal {
29 
30 // We emulate a GraphCycles object with a node vector and an edge vector.
31 // We then compare the two implementations.
32 
33 using Nodes = std::vector<int>;
34 struct Edge {
35  int from;
36  int to;
37 };
38 using Edges = std::vector<Edge>;
39 using RandomEngine = std::mt19937_64;
40 
41 // Mapping from integer index to GraphId.
42 typedef std::map<int, GraphId> IdMap;
43 static GraphId Get(const IdMap& id, int num) {
44  auto iter = id.find(num);
45  return (iter == id.end()) ? InvalidGraphId() : iter->second;
46 }
47 
48 // Return whether "to" is reachable from "from".
49 static bool IsReachable(Edges *edges, int from, int to,
50  std::unordered_set<int> *seen) {
51  seen->insert(from); // we are investigating "from"; don't do it again
52  if (from == to) return true;
53  for (const auto &edge : *edges) {
54  if (edge.from == from) {
55  if (edge.to == to) { // success via edge directly
56  return true;
57  } else if (seen->find(edge.to) == seen->end() && // success via edge
58  IsReachable(edges, edge.to, to, seen)) {
59  return true;
60  }
61  }
62  }
63  return false;
64 }
65 
66 static void PrintEdges(Edges *edges) {
67  ABSL_RAW_LOG(INFO, "EDGES (%zu)", edges->size());
68  for (const auto &edge : *edges) {
69  int a = edge.from;
70  int b = edge.to;
71  ABSL_RAW_LOG(INFO, "%d %d", a, b);
72  }
73  ABSL_RAW_LOG(INFO, "---");
74 }
75 
76 static void PrintGCEdges(Nodes *nodes, const IdMap &id, GraphCycles *gc) {
77  ABSL_RAW_LOG(INFO, "GC EDGES");
78  for (int a : *nodes) {
79  for (int b : *nodes) {
80  if (gc->HasEdge(Get(id, a), Get(id, b))) {
81  ABSL_RAW_LOG(INFO, "%d %d", a, b);
82  }
83  }
84  }
85  ABSL_RAW_LOG(INFO, "---");
86 }
87 
88 static void PrintTransitiveClosure(Nodes *nodes, Edges *edges) {
89  ABSL_RAW_LOG(INFO, "Transitive closure");
90  for (int a : *nodes) {
91  for (int b : *nodes) {
92  std::unordered_set<int> seen;
93  if (IsReachable(edges, a, b, &seen)) {
94  ABSL_RAW_LOG(INFO, "%d %d", a, b);
95  }
96  }
97  }
98  ABSL_RAW_LOG(INFO, "---");
99 }
100 
101 static void PrintGCTransitiveClosure(Nodes *nodes, const IdMap &id,
102  GraphCycles *gc) {
103  ABSL_RAW_LOG(INFO, "GC Transitive closure");
104  for (int a : *nodes) {
105  for (int b : *nodes) {
106  if (gc->IsReachable(Get(id, a), Get(id, b))) {
107  ABSL_RAW_LOG(INFO, "%d %d", a, b);
108  }
109  }
110  }
111  ABSL_RAW_LOG(INFO, "---");
112 }
113 
114 static void CheckTransitiveClosure(Nodes *nodes, Edges *edges, const IdMap &id,
115  GraphCycles *gc) {
116  std::unordered_set<int> seen;
117  for (const auto &a : *nodes) {
118  for (const auto &b : *nodes) {
119  seen.clear();
120  bool gc_reachable = gc->IsReachable(Get(id, a), Get(id, b));
121  bool reachable = IsReachable(edges, a, b, &seen);
122  if (gc_reachable != reachable) {
123  PrintEdges(edges);
124  PrintGCEdges(nodes, id, gc);
125  PrintTransitiveClosure(nodes, edges);
126  PrintGCTransitiveClosure(nodes, id, gc);
127  ABSL_RAW_LOG(FATAL, "gc_reachable %s reachable %s a %d b %d",
128  gc_reachable ? "true" : "false",
129  reachable ? "true" : "false", a, b);
130  }
131  }
132  }
133 }
134 
135 static void CheckEdges(Nodes *nodes, Edges *edges, const IdMap &id,
136  GraphCycles *gc) {
137  int count = 0;
138  for (const auto &edge : *edges) {
139  int a = edge.from;
140  int b = edge.to;
141  if (!gc->HasEdge(Get(id, a), Get(id, b))) {
142  PrintEdges(edges);
143  PrintGCEdges(nodes, id, gc);
144  ABSL_RAW_LOG(FATAL, "!gc->HasEdge(%d, %d)", a, b);
145  }
146  }
147  for (const auto &a : *nodes) {
148  for (const auto &b : *nodes) {
149  if (gc->HasEdge(Get(id, a), Get(id, b))) {
150  count++;
151  }
152  }
153  }
154  if (count != edges->size()) {
155  PrintEdges(edges);
156  PrintGCEdges(nodes, id, gc);
157  ABSL_RAW_LOG(FATAL, "edges->size() %zu count %d", edges->size(), count);
158  }
159 }
160 
161 static void CheckInvariants(const GraphCycles &gc) {
163  ABSL_RAW_LOG(FATAL, "CheckInvariants");
164 }
165 
166 // Returns the index of a randomly chosen node in *nodes.
167 // Requires *nodes be non-empty.
168 static int RandomNode(RandomEngine* rng, Nodes *nodes) {
169  std::uniform_int_distribution<int> uniform(0, nodes->size()-1);
170  return uniform(*rng);
171 }
172 
173 // Returns the index of a randomly chosen edge in *edges.
174 // Requires *edges be non-empty.
175 static int RandomEdge(RandomEngine* rng, Edges *edges) {
176  std::uniform_int_distribution<int> uniform(0, edges->size()-1);
177  return uniform(*rng);
178 }
179 
180 // Returns the index of edge (from, to) in *edges or -1 if it is not in *edges.
181 static int EdgeIndex(Edges *edges, int from, int to) {
182  int i = 0;
183  while (i != edges->size() &&
184  ((*edges)[i].from != from || (*edges)[i].to != to)) {
185  i++;
186  }
187  return i == edges->size()? -1 : i;
188 }
189 
190 TEST(GraphCycles, RandomizedTest) {
191  int next_node = 0;
192  Nodes nodes;
193  Edges edges; // from, to
194  IdMap id;
195  GraphCycles graph_cycles;
196  static const int kMaxNodes = 7; // use <= 7 nodes to keep test short
197  static const int kDataOffset = 17; // an offset to the node-specific data
198  int n = 100000;
199  int op = 0;
200  RandomEngine rng(testing::UnitTest::GetInstance()->random_seed());
201  std::uniform_int_distribution<int> uniform(0, 5);
202 
203  auto ptr = [](intptr_t i) {
204  return reinterpret_cast<void*>(i + kDataOffset);
205  };
206 
207  for (int iter = 0; iter != n; iter++) {
208  for (const auto &node : nodes) {
209  ASSERT_EQ(graph_cycles.Ptr(Get(id, node)), ptr(node)) << " node " << node;
210  }
211  CheckEdges(&nodes, &edges, id, &graph_cycles);
212  CheckTransitiveClosure(&nodes, &edges, id, &graph_cycles);
213  op = uniform(rng);
214  switch (op) {
215  case 0: // Add a node
216  if (nodes.size() < kMaxNodes) {
217  int new_node = next_node++;
218  GraphId new_gnode = graph_cycles.GetId(ptr(new_node));
219  ASSERT_NE(new_gnode, InvalidGraphId());
220  id[new_node] = new_gnode;
221  ASSERT_EQ(ptr(new_node), graph_cycles.Ptr(new_gnode));
222  nodes.push_back(new_node);
223  }
224  break;
225 
226  case 1: // Remove a node
227  if (nodes.size() > 0) {
228  int node_index = RandomNode(&rng, &nodes);
229  int node = nodes[node_index];
230  nodes[node_index] = nodes.back();
231  nodes.pop_back();
232  graph_cycles.RemoveNode(ptr(node));
233  ASSERT_EQ(graph_cycles.Ptr(Get(id, node)), nullptr);
234  id.erase(node);
235  int i = 0;
236  while (i != edges.size()) {
237  if (edges[i].from == node || edges[i].to == node) {
238  edges[i] = edges.back();
239  edges.pop_back();
240  } else {
241  i++;
242  }
243  }
244  }
245  break;
246 
247  case 2: // Add an edge
248  if (nodes.size() > 0) {
249  int from = RandomNode(&rng, &nodes);
250  int to = RandomNode(&rng, &nodes);
251  if (EdgeIndex(&edges, nodes[from], nodes[to]) == -1) {
252  if (graph_cycles.InsertEdge(id[nodes[from]], id[nodes[to]])) {
253  Edge new_edge;
254  new_edge.from = nodes[from];
255  new_edge.to = nodes[to];
256  edges.push_back(new_edge);
257  } else {
258  std::unordered_set<int> seen;
259  ASSERT_TRUE(IsReachable(&edges, nodes[to], nodes[from], &seen))
260  << "Edge " << nodes[to] << "->" << nodes[from];
261  }
262  }
263  }
264  break;
265 
266  case 3: // Remove an edge
267  if (edges.size() > 0) {
268  int i = RandomEdge(&rng, &edges);
269  int from = edges[i].from;
270  int to = edges[i].to;
271  ASSERT_EQ(i, EdgeIndex(&edges, from, to));
272  edges[i] = edges.back();
273  edges.pop_back();
274  ASSERT_EQ(-1, EdgeIndex(&edges, from, to));
275  graph_cycles.RemoveEdge(id[from], id[to]);
276  }
277  break;
278 
279  case 4: // Check a path
280  if (nodes.size() > 0) {
281  int from = RandomNode(&rng, &nodes);
282  int to = RandomNode(&rng, &nodes);
283  GraphId path[2*kMaxNodes];
284  int path_len = graph_cycles.FindPath(id[nodes[from]], id[nodes[to]],
285  ABSL_ARRAYSIZE(path), path);
286  std::unordered_set<int> seen;
287  bool reachable = IsReachable(&edges, nodes[from], nodes[to], &seen);
288  bool gc_reachable =
289  graph_cycles.IsReachable(Get(id, nodes[from]), Get(id, nodes[to]));
290  ASSERT_EQ(path_len != 0, reachable);
291  ASSERT_EQ(path_len != 0, gc_reachable);
292  // In the following line, we add one because a node can appear
293  // twice, if the path is from that node to itself, perhaps via
294  // every other node.
295  ASSERT_LE(path_len, kMaxNodes + 1);
296  if (path_len != 0) {
297  ASSERT_EQ(id[nodes[from]], path[0]);
298  ASSERT_EQ(id[nodes[to]], path[path_len-1]);
299  for (int i = 1; i < path_len; i++) {
300  ASSERT_TRUE(graph_cycles.HasEdge(path[i-1], path[i]));
301  }
302  }
303  }
304  break;
305 
306  case 5: // Check invariants
307  CheckInvariants(graph_cycles);
308  break;
309 
310  default:
311  ABSL_RAW_LOG(FATAL, "op %d", op);
312  }
313 
314  // Very rarely, test graph expansion by adding then removing many nodes.
315  std::bernoulli_distribution one_in_1024(1.0 / 1024);
316  if (one_in_1024(rng)) {
317  CheckEdges(&nodes, &edges, id, &graph_cycles);
318  CheckTransitiveClosure(&nodes, &edges, id, &graph_cycles);
319  for (int i = 0; i != 256; i++) {
320  int new_node = next_node++;
321  GraphId new_gnode = graph_cycles.GetId(ptr(new_node));
322  ASSERT_NE(InvalidGraphId(), new_gnode);
323  id[new_node] = new_gnode;
324  ASSERT_EQ(ptr(new_node), graph_cycles.Ptr(new_gnode));
325  for (const auto &node : nodes) {
326  ASSERT_NE(node, new_node);
327  }
328  nodes.push_back(new_node);
329  }
330  for (int i = 0; i != 256; i++) {
331  ASSERT_GT(nodes.size(), 0);
332  int node_index = RandomNode(&rng, &nodes);
333  int node = nodes[node_index];
334  nodes[node_index] = nodes.back();
335  nodes.pop_back();
336  graph_cycles.RemoveNode(ptr(node));
337  id.erase(node);
338  int j = 0;
339  while (j != edges.size()) {
340  if (edges[j].from == node || edges[j].to == node) {
341  edges[j] = edges.back();
342  edges.pop_back();
343  } else {
344  j++;
345  }
346  }
347  }
348  CheckInvariants(graph_cycles);
349  }
350  }
351 }
352 
353 class GraphCyclesTest : public ::testing::Test {
354  public:
355  IdMap id_;
357 
358  static void* Ptr(int i) {
359  return reinterpret_cast<void*>(static_cast<uintptr_t>(i));
360  }
361 
362  static int Num(void* ptr) {
363  return static_cast<int>(reinterpret_cast<uintptr_t>(ptr));
364  }
365 
366  // Test relies on ith NewNode() call returning Node numbered i
368  for (int i = 0; i < 100; i++) {
369  id_[i] = g_.GetId(Ptr(i));
370  }
371  CheckInvariants(g_);
372  }
373 
374  bool AddEdge(int x, int y) {
375  return g_.InsertEdge(Get(id_, x), Get(id_, y));
376  }
377 
378  void AddMultiples() {
379  // For every node x > 0: add edge to 2*x, 3*x
380  for (int x = 1; x < 25; x++) {
381  EXPECT_TRUE(AddEdge(x, 2*x)) << x;
382  EXPECT_TRUE(AddEdge(x, 3*x)) << x;
383  }
384  CheckInvariants(g_);
385  }
386 
387  std::string Path(int x, int y) {
388  GraphId path[5];
389  int np = g_.FindPath(Get(id_, x), Get(id_, y), ABSL_ARRAYSIZE(path), path);
390  std::string result;
391  for (int i = 0; i < np; i++) {
392  if (i >= ABSL_ARRAYSIZE(path)) {
393  result += " ...";
394  break;
395  }
396  if (!result.empty()) result.push_back(' ');
397  char buf[20];
398  snprintf(buf, sizeof(buf), "%d", Num(g_.Ptr(path[i])));
399  result += buf;
400  }
401  return result;
402  }
403 };
404 
406  AddMultiples();
407  CheckInvariants(g_);
408 }
409 
410 TEST_F(GraphCyclesTest, SimpleCycle) {
411  AddMultiples();
412  EXPECT_FALSE(AddEdge(8, 4));
413  EXPECT_EQ("4 8", Path(4, 8));
414  CheckInvariants(g_);
415 }
416 
417 TEST_F(GraphCyclesTest, IndirectCycle) {
418  AddMultiples();
419  EXPECT_TRUE(AddEdge(16, 9));
420  CheckInvariants(g_);
421  EXPECT_FALSE(AddEdge(9, 2));
422  EXPECT_EQ("2 4 8 16 9", Path(2, 9));
423  CheckInvariants(g_);
424 }
425 
427  ASSERT_TRUE(AddEdge(2, 4));
428  ASSERT_TRUE(AddEdge(4, 6));
429  ASSERT_TRUE(AddEdge(6, 8));
430  ASSERT_TRUE(AddEdge(8, 10));
431  ASSERT_TRUE(AddEdge(10, 12));
432  ASSERT_FALSE(AddEdge(12, 2));
433  EXPECT_EQ("2 4 6 8 10 ...", Path(2, 12));
434  CheckInvariants(g_);
435 }
436 
437 TEST_F(GraphCyclesTest, RemoveNode) {
438  ASSERT_TRUE(AddEdge(1, 2));
439  ASSERT_TRUE(AddEdge(2, 3));
440  ASSERT_TRUE(AddEdge(3, 4));
441  ASSERT_TRUE(AddEdge(4, 5));
442  g_.RemoveNode(g_.Ptr(id_[3]));
443  id_.erase(3);
444  ASSERT_TRUE(AddEdge(5, 1));
445 }
446 
447 TEST_F(GraphCyclesTest, ManyEdges) {
448  const int N = 50;
449  for (int i = 0; i < N; i++) {
450  for (int j = 1; j < N; j++) {
451  ASSERT_TRUE(AddEdge(i, i+j));
452  }
453  }
454  CheckInvariants(g_);
455  ASSERT_TRUE(AddEdge(2*N-1, 0));
456  CheckInvariants(g_);
457  ASSERT_FALSE(AddEdge(10, 9));
458  CheckInvariants(g_);
459 }
460 
461 } // namespace synchronization_internal
462 } // namespace absl
static GraphId Get(const IdMap &id, int num)
TEST(GraphCycles, RandomizedTest)
int FindPath(GraphId source, GraphId dest, int max_path_len, GraphId path[]) const
Definition: graphcycles.cc:623
#define ABSL_RAW_LOG(severity,...)
Definition: raw_logging.h:42
static int EdgeIndex(Edges *edges, int from, int to)
static void PrintGCTransitiveClosure(Nodes *nodes, const IdMap &id, GraphCycles *gc)
#define ABSL_PREDICT_FALSE(x)
Definition: optimization.h:177
bool IsReachable(GraphId source_node, GraphId dest_node) const
Definition: graphcycles.cc:667
bool InsertEdge(GraphId source_node, GraphId dest_node)
Definition: graphcycles.cc:491
char * end
char buf[N]
void RemoveEdge(GraphId source_node, GraphId dest_node)
Definition: graphcycles.cc:473
Definition: algorithm.h:29
GraphId path[kMaxDeadlockPathLen]
Definition: mutex.cc:1288
char * ptr
TEST_F(GraphCyclesTest, NoCycle)
static void CheckTransitiveClosure(Nodes *nodes, Edges *edges, const IdMap &id, GraphCycles *gc)
static int RandomNode(RandomEngine *rng, Nodes *nodes)
bool HasEdge(GraphId source_node, GraphId dest_node) const
Definition: graphcycles.cc:468
static void PrintGCEdges(Nodes *nodes, const IdMap &id, GraphCycles *gc)
static void PrintEdges(Edges *edges)
#define ABSL_ARRAYSIZE(array)
Definition: macros.h:42
uint64_t b
Definition: layout_test.cc:50
static void PrintTransitiveClosure(Nodes *nodes, Edges *edges)
static void CheckEdges(Nodes *nodes, Edges *edges, const IdMap &id, GraphCycles *gc)
static void CheckInvariants(const GraphCycles &gc)
static bool IsReachable(Edges *edges, int from, int to, std::unordered_set< int > *seen)
static int RandomEdge(RandomEngine *rng, Edges *edges)
std::map< int, GraphId > IdMap


abseil_cpp
Author(s):
autogenerated on Tue Jun 18 2019 19:44:36