1 /* Copyright 2017 The TensorFlow Authors. All Rights Reserved.
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 http://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 ==============================================================================*/
15
16 // A test for the GraphCycles interface.
17
18 #include "tensorflow/compiler/jit/graphcycles/graphcycles.h"
19
20 #include <random>
21 #include <unordered_set>
22 #include <vector>
23
24 #include "tensorflow/core/platform/logging.h"
25 #include "tensorflow/core/platform/test.h"
26 #include "tensorflow/core/platform/test_benchmark.h"
27 #include "tensorflow/core/platform/types.h"
28
29 using tensorflow::int32;
30 using tensorflow::string;
31
32 // We emulate a GraphCycles object with a node vector and an edge vector.
33 // We then compare the two implementations.
34
35 typedef std::vector<int> Nodes;
36 struct Edge {
37 int from;
38 int to;
39 };
40 typedef std::vector<Edge> Edges;
41
42 // Return whether "to" is reachable from "from".
IsReachable(Edges * edges,int from,int to,std::unordered_set<int> * seen)43 static bool IsReachable(Edges *edges, int from, int to,
44 std::unordered_set<int> *seen) {
45 seen->insert(from); // we are investigating "from"; don't do it again
46 if (from == to) return true;
47 for (int i = 0; i != edges->size(); i++) {
48 Edge *edge = &(*edges)[i];
49 if (edge->from == from) {
50 if (edge->to == to) { // success via edge directly
51 return true;
52 } else if (seen->find(edge->to) == seen->end() && // success via edge
53 IsReachable(edges, edge->to, to, seen)) {
54 return true;
55 }
56 }
57 }
58 return false;
59 }
60
PrintNodes(Nodes * nodes)61 static void PrintNodes(Nodes *nodes) {
62 LOG(INFO) << "NODES (" << nodes->size() << ")";
63 for (int i = 0; i != nodes->size(); i++) {
64 LOG(INFO) << (*nodes)[i];
65 }
66 }
67
PrintEdges(Edges * edges)68 static void PrintEdges(Edges *edges) {
69 LOG(INFO) << "EDGES (" << edges->size() << ")";
70 for (int i = 0; i != edges->size(); i++) {
71 int a = (*edges)[i].from;
72 int b = (*edges)[i].to;
73 LOG(INFO) << a << " " << b;
74 }
75 LOG(INFO) << "---";
76 }
77
PrintGCEdges(Nodes * nodes,tensorflow::GraphCycles * gc)78 static void PrintGCEdges(Nodes *nodes, tensorflow::GraphCycles *gc) {
79 LOG(INFO) << "GC EDGES";
80 for (int i = 0; i != nodes->size(); i++) {
81 for (int j = 0; j != nodes->size(); j++) {
82 int a = (*nodes)[i];
83 int b = (*nodes)[j];
84 if (gc->HasEdge(a, b)) {
85 LOG(INFO) << a << " " << b;
86 }
87 }
88 }
89 LOG(INFO) << "---";
90 }
91
PrintTransitiveClosure(Nodes * nodes,Edges * edges,tensorflow::GraphCycles * gc)92 static void PrintTransitiveClosure(Nodes *nodes, Edges *edges,
93 tensorflow::GraphCycles *gc) {
94 LOG(INFO) << "Transitive closure";
95 for (int i = 0; i != nodes->size(); i++) {
96 for (int j = 0; j != nodes->size(); j++) {
97 int a = (*nodes)[i];
98 int b = (*nodes)[j];
99 std::unordered_set<int> seen;
100 if (IsReachable(edges, a, b, &seen)) {
101 LOG(INFO) << a << " " << b;
102 }
103 }
104 }
105 LOG(INFO) << "---";
106 }
107
PrintGCTransitiveClosure(Nodes * nodes,tensorflow::GraphCycles * gc)108 static void PrintGCTransitiveClosure(Nodes *nodes,
109 tensorflow::GraphCycles *gc) {
110 LOG(INFO) << "GC Transitive closure";
111 for (int i = 0; i != nodes->size(); i++) {
112 for (int j = 0; j != nodes->size(); j++) {
113 int a = (*nodes)[i];
114 int b = (*nodes)[j];
115 if (gc->IsReachable(a, b)) {
116 LOG(INFO) << a << " " << b;
117 }
118 }
119 }
120 LOG(INFO) << "---";
121 }
122
CheckTransitiveClosure(Nodes * nodes,Edges * edges,tensorflow::GraphCycles * gc)123 static void CheckTransitiveClosure(Nodes *nodes, Edges *edges,
124 tensorflow::GraphCycles *gc) {
125 std::unordered_set<int> seen;
126 for (int i = 0; i != nodes->size(); i++) {
127 for (int j = 0; j != nodes->size(); j++) {
128 seen.clear();
129 int a = (*nodes)[i];
130 int b = (*nodes)[j];
131 bool gc_reachable = gc->IsReachable(a, b);
132 CHECK_EQ(gc_reachable, gc->IsReachableNonConst(a, b));
133 bool reachable = IsReachable(edges, a, b, &seen);
134 if (gc_reachable != reachable) {
135 PrintEdges(edges);
136 PrintGCEdges(nodes, gc);
137 PrintTransitiveClosure(nodes, edges, gc);
138 PrintGCTransitiveClosure(nodes, gc);
139 LOG(FATAL) << "gc_reachable " << gc_reachable << " reachable "
140 << reachable << " a " << a << " b " << b;
141 }
142 }
143 }
144 }
145
CheckEdges(Nodes * nodes,Edges * edges,tensorflow::GraphCycles * gc)146 static void CheckEdges(Nodes *nodes, Edges *edges,
147 tensorflow::GraphCycles *gc) {
148 int count = 0;
149 for (int i = 0; i != edges->size(); i++) {
150 int a = (*edges)[i].from;
151 int b = (*edges)[i].to;
152 if (!gc->HasEdge(a, b)) {
153 PrintEdges(edges);
154 PrintGCEdges(nodes, gc);
155 LOG(FATAL) << "!gc->HasEdge(" << a << ", " << b << ")";
156 }
157 }
158 for (int i = 0; i != nodes->size(); i++) {
159 for (int j = 0; j != nodes->size(); j++) {
160 int a = (*nodes)[i];
161 int b = (*nodes)[j];
162 if (gc->HasEdge(a, b)) {
163 count++;
164 }
165 }
166 }
167 if (count != edges->size()) {
168 PrintEdges(edges);
169 PrintGCEdges(nodes, gc);
170 LOG(FATAL) << "edges->size() " << edges->size() << " count " << count;
171 }
172 }
173
174 // Returns the index of a randomly chosen node in *nodes.
175 // Requires *nodes be non-empty.
RandomNode(std::mt19937 * rnd,Nodes * nodes)176 static int RandomNode(std::mt19937 *rnd, Nodes *nodes) {
177 std::uniform_int_distribution<int> distribution(0, nodes->size() - 1);
178 return distribution(*rnd);
179 }
180
181 // Returns the index of a randomly chosen edge in *edges.
182 // Requires *edges be non-empty.
RandomEdge(std::mt19937 * rnd,Edges * edges)183 static int RandomEdge(std::mt19937 *rnd, Edges *edges) {
184 std::uniform_int_distribution<int> distribution(0, edges->size() - 1);
185 return distribution(*rnd);
186 }
187
188 // Returns the index of edge (from, to) in *edges or -1 if it is not in *edges.
EdgeIndex(Edges * edges,int from,int to)189 static int EdgeIndex(Edges *edges, int from, int to) {
190 int i = 0;
191 while (i != edges->size() &&
192 ((*edges)[i].from != from || (*edges)[i].to != to)) {
193 i++;
194 }
195 return i == edges->size() ? -1 : i;
196 }
197
TEST(GraphCycles,RandomizedTest)198 TEST(GraphCycles, RandomizedTest) {
199 Nodes nodes;
200 Edges edges; // from, to
201 tensorflow::GraphCycles graph_cycles;
202 static const int kMaxNodes = 7; // use <= 7 nodes to keep test short
203 static const int kDataOffset = 17; // an offset to the node-specific data
204 int n = 100000;
205 int op = 0;
206 std::mt19937 rnd(tensorflow::testing::RandomSeed() + 1);
207
208 for (int iter = 0; iter != n; iter++) {
209 if ((iter % 10000) == 0) VLOG(0) << "Iter " << iter << " of " << n;
210
211 if (VLOG_IS_ON(3)) {
212 LOG(INFO) << "===============";
213 LOG(INFO) << "last op " << op;
214 PrintNodes(&nodes);
215 PrintEdges(&edges);
216 PrintGCEdges(&nodes, &graph_cycles);
217 }
218 for (int i = 0; i != nodes.size(); i++) {
219 ASSERT_EQ(reinterpret_cast<intptr_t>(graph_cycles.GetNodeData(i)),
220 i + kDataOffset)
221 << " node " << i;
222 }
223 CheckEdges(&nodes, &edges, &graph_cycles);
224 CheckTransitiveClosure(&nodes, &edges, &graph_cycles);
225 std::uniform_int_distribution<int> distribution(0, 5);
226 op = distribution(rnd);
227 switch (op) {
228 case 0: // Add a node
229 if (nodes.size() < kMaxNodes) {
230 int new_node = graph_cycles.NewNode();
231 ASSERT_NE(-1, new_node);
232 VLOG(1) << "adding node " << new_node;
233 ASSERT_EQ(nullptr, graph_cycles.GetNodeData(new_node));
234 graph_cycles.SetNodeData(
235 new_node, reinterpret_cast<void *>(
236 static_cast<intptr_t>(new_node + kDataOffset)));
237 ASSERT_GE(new_node, 0);
238 for (int i = 0; i != nodes.size(); i++) {
239 ASSERT_NE(nodes[i], new_node);
240 }
241 nodes.push_back(new_node);
242 }
243 break;
244
245 case 1: // Remove a node
246 if (!nodes.empty()) {
247 int node_index = RandomNode(&rnd, &nodes);
248 int node = nodes[node_index];
249 nodes[node_index] = nodes.back();
250 nodes.pop_back();
251 VLOG(1) << "removing node " << node;
252 graph_cycles.RemoveNode(node);
253 int i = 0;
254 while (i != edges.size()) {
255 if (edges[i].from == node || edges[i].to == node) {
256 edges[i] = edges.back();
257 edges.pop_back();
258 } else {
259 i++;
260 }
261 }
262 }
263 break;
264
265 case 2: // Add an edge
266 if (!nodes.empty()) {
267 int from = RandomNode(&rnd, &nodes);
268 int to = RandomNode(&rnd, &nodes);
269 if (EdgeIndex(&edges, nodes[from], nodes[to]) == -1) {
270 if (graph_cycles.InsertEdge(nodes[from], nodes[to])) {
271 Edge new_edge;
272 new_edge.from = nodes[from];
273 new_edge.to = nodes[to];
274 edges.push_back(new_edge);
275 } else {
276 std::unordered_set<int> seen;
277 ASSERT_TRUE(IsReachable(&edges, nodes[to], nodes[from], &seen))
278 << "Edge " << nodes[to] << "->" << nodes[from];
279 }
280 }
281 }
282 break;
283
284 case 3: // Remove an edge
285 if (!edges.empty()) {
286 int i = RandomEdge(&rnd, &edges);
287 int from = edges[i].from;
288 int to = edges[i].to;
289 ASSERT_EQ(i, EdgeIndex(&edges, from, to));
290 edges[i] = edges.back();
291 edges.pop_back();
292 ASSERT_EQ(-1, EdgeIndex(&edges, from, to));
293 VLOG(1) << "removing edge " << from << " " << to;
294 graph_cycles.RemoveEdge(from, to);
295 }
296 break;
297
298 case 4: // Check a path
299 if (!nodes.empty()) {
300 int from = RandomNode(&rnd, &nodes);
301 int to = RandomNode(&rnd, &nodes);
302 int32 path[2 * kMaxNodes];
303 int path_len = graph_cycles.FindPath(nodes[from], nodes[to],
304 2 * kMaxNodes, path);
305 std::unordered_set<int> seen;
306 bool reachable = IsReachable(&edges, nodes[from], nodes[to], &seen);
307 bool gc_reachable = graph_cycles.IsReachable(nodes[from], nodes[to]);
308 ASSERT_EQ(gc_reachable,
309 graph_cycles.IsReachableNonConst(nodes[from], nodes[to]));
310 ASSERT_EQ(path_len != 0, reachable);
311 ASSERT_EQ(path_len != 0, gc_reachable);
312 // In the following line, we add one because a node can appear
313 // twice, if the path is from that node to itself, perhaps via
314 // every other node.
315 ASSERT_LE(path_len, kMaxNodes + 1);
316 if (path_len != 0) {
317 ASSERT_EQ(nodes[from], path[0]);
318 ASSERT_EQ(nodes[to], path[path_len - 1]);
319 for (int i = 1; i < path_len; i++) {
320 ASSERT_NE(-1, EdgeIndex(&edges, path[i - 1], path[i]));
321 ASSERT_TRUE(graph_cycles.HasEdge(path[i - 1], path[i]));
322 }
323 }
324 }
325 break;
326
327 case 5: // Check invariants
328 CHECK(graph_cycles.CheckInvariants());
329 break;
330
331 default:
332 LOG(FATAL);
333 }
334
335 // Very rarely, test graph expansion by adding then removing many nodes.
336 std::bernoulli_distribution rarely(1.0 / 1024.0);
337 if (rarely(rnd)) {
338 VLOG(3) << "Graph expansion";
339 CheckEdges(&nodes, &edges, &graph_cycles);
340 CheckTransitiveClosure(&nodes, &edges, &graph_cycles);
341 for (int i = 0; i != 256; i++) {
342 int new_node = graph_cycles.NewNode();
343 ASSERT_NE(-1, new_node);
344 VLOG(1) << "adding node " << new_node;
345 ASSERT_GE(new_node, 0);
346 ASSERT_EQ(nullptr, graph_cycles.GetNodeData(new_node));
347 graph_cycles.SetNodeData(
348 new_node, reinterpret_cast<void *>(
349 static_cast<intptr_t>(new_node + kDataOffset)));
350 for (int j = 0; j != nodes.size(); j++) {
351 ASSERT_NE(nodes[j], new_node);
352 }
353 nodes.push_back(new_node);
354 }
355 for (int i = 0; i != 256; i++) {
356 ASSERT_GT(nodes.size(), 0);
357 int node_index = RandomNode(&rnd, &nodes);
358 int node = nodes[node_index];
359 nodes[node_index] = nodes.back();
360 nodes.pop_back();
361 VLOG(1) << "removing node " << node;
362 graph_cycles.RemoveNode(node);
363 int j = 0;
364 while (j != edges.size()) {
365 if (edges[j].from == node || edges[j].to == node) {
366 edges[j] = edges.back();
367 edges.pop_back();
368 } else {
369 j++;
370 }
371 }
372 }
373 CHECK(graph_cycles.CheckInvariants());
374 }
375 }
376 }
377
378 class GraphCyclesTest : public ::testing::Test {
379 public:
380 tensorflow::GraphCycles g_;
381
382 // Test relies on ith NewNode() call returning Node numbered i
GraphCyclesTest()383 GraphCyclesTest() {
384 for (int i = 0; i < 100; i++) {
385 CHECK_EQ(i, g_.NewNode());
386 }
387 CHECK(g_.CheckInvariants());
388 }
389
AddEdge(int x,int y)390 bool AddEdge(int x, int y) { return g_.InsertEdge(x, y); }
391
AddMultiples()392 void AddMultiples() {
393 // For every node x > 0: add edge to 2*x, 3*x
394 for (int x = 1; x < 25; x++) {
395 EXPECT_TRUE(AddEdge(x, 2 * x)) << x;
396 EXPECT_TRUE(AddEdge(x, 3 * x)) << x;
397 }
398 CHECK(g_.CheckInvariants());
399 }
400
Path(int x,int y)401 string Path(int x, int y) {
402 static const int kPathSize = 5;
403 int32 path[kPathSize];
404 int np = g_.FindPath(x, y, kPathSize, path);
405 string result;
406 for (int i = 0; i < np; i++) {
407 if (i >= kPathSize) {
408 result += " ...";
409 break;
410 }
411 if (!result.empty()) result.push_back(' ');
412 char buf[20];
413 snprintf(buf, sizeof(buf), "%d", path[i]);
414 result += buf;
415 }
416 return result;
417 }
418 };
419
TEST_F(GraphCyclesTest,NoCycle)420 TEST_F(GraphCyclesTest, NoCycle) {
421 AddMultiples();
422 CHECK(g_.CheckInvariants());
423 }
424
TEST_F(GraphCyclesTest,SimpleCycle)425 TEST_F(GraphCyclesTest, SimpleCycle) {
426 AddMultiples();
427 EXPECT_FALSE(AddEdge(8, 4));
428 EXPECT_EQ("4 8", Path(4, 8));
429 CHECK(g_.CheckInvariants());
430 }
431
TEST_F(GraphCyclesTest,IndirectCycle)432 TEST_F(GraphCyclesTest, IndirectCycle) {
433 AddMultiples();
434 EXPECT_TRUE(AddEdge(16, 9));
435 CHECK(g_.CheckInvariants());
436 EXPECT_FALSE(AddEdge(9, 2));
437 EXPECT_EQ("2 4 8 16 9", Path(2, 9));
438 CHECK(g_.CheckInvariants());
439 }
440
TEST_F(GraphCyclesTest,LongPath)441 TEST_F(GraphCyclesTest, LongPath) {
442 ASSERT_TRUE(AddEdge(2, 4));
443 ASSERT_TRUE(AddEdge(4, 6));
444 ASSERT_TRUE(AddEdge(6, 8));
445 ASSERT_TRUE(AddEdge(8, 10));
446 ASSERT_TRUE(AddEdge(10, 12));
447 ASSERT_FALSE(AddEdge(12, 2));
448 EXPECT_EQ("2 4 6 8 10 ...", Path(2, 12));
449 CHECK(g_.CheckInvariants());
450 }
451
TEST_F(GraphCyclesTest,RemoveNode)452 TEST_F(GraphCyclesTest, RemoveNode) {
453 ASSERT_TRUE(AddEdge(1, 2));
454 ASSERT_TRUE(AddEdge(2, 3));
455 ASSERT_TRUE(AddEdge(3, 4));
456 ASSERT_TRUE(AddEdge(4, 5));
457 g_.RemoveNode(3);
458 ASSERT_TRUE(AddEdge(5, 1));
459 }
460
TEST_F(GraphCyclesTest,ManyEdges)461 TEST_F(GraphCyclesTest, ManyEdges) {
462 const int N = 50;
463 for (int i = 0; i < N; i++) {
464 for (int j = 1; j < N; j++) {
465 ASSERT_TRUE(AddEdge(i, i + j));
466 }
467 }
468 CHECK(g_.CheckInvariants());
469 ASSERT_TRUE(AddEdge(2 * N - 1, 0));
470 CHECK(g_.CheckInvariants());
471 ASSERT_FALSE(AddEdge(10, 9));
472 CHECK(g_.CheckInvariants());
473 }
474
TEST_F(GraphCyclesTest,ContractEdge)475 TEST_F(GraphCyclesTest, ContractEdge) {
476 ASSERT_TRUE(AddEdge(1, 2));
477 ASSERT_TRUE(AddEdge(1, 3));
478 ASSERT_TRUE(AddEdge(2, 3));
479 ASSERT_TRUE(AddEdge(2, 4));
480 ASSERT_TRUE(AddEdge(3, 4));
481
482 EXPECT_FALSE(g_.ContractEdge(1, 3));
483 CHECK(g_.CheckInvariants());
484 EXPECT_TRUE(g_.HasEdge(1, 3));
485
486 EXPECT_TRUE(g_.ContractEdge(1, 2));
487 CHECK(g_.CheckInvariants());
488 EXPECT_TRUE(g_.HasEdge(1, 3));
489 EXPECT_TRUE(g_.HasEdge(1, 4));
490 EXPECT_TRUE(g_.HasEdge(3, 4));
491
492 EXPECT_TRUE(g_.ContractEdge(1, 3));
493 CHECK(g_.CheckInvariants());
494 EXPECT_TRUE(g_.HasEdge(1, 4));
495 }
496
TEST_F(GraphCyclesTest,CanContractEdge)497 TEST_F(GraphCyclesTest, CanContractEdge) {
498 ASSERT_TRUE(AddEdge(1, 2));
499 ASSERT_TRUE(AddEdge(1, 3));
500 ASSERT_TRUE(AddEdge(2, 3));
501 ASSERT_TRUE(AddEdge(2, 4));
502 ASSERT_TRUE(AddEdge(3, 4));
503
504 EXPECT_FALSE(g_.CanContractEdge(1, 3));
505 EXPECT_FALSE(g_.CanContractEdge(2, 4));
506 EXPECT_TRUE(g_.CanContractEdge(1, 2));
507 EXPECT_TRUE(g_.CanContractEdge(2, 3));
508 EXPECT_TRUE(g_.CanContractEdge(3, 4));
509 }
510
BM_StressTest(int iters,int num_nodes)511 static void BM_StressTest(int iters, int num_nodes) {
512 while (iters > 0) {
513 tensorflow::GraphCycles g;
514 int32 *nodes = new int32[num_nodes];
515 for (int i = 0; i < num_nodes; i++) {
516 nodes[i] = g.NewNode();
517 }
518 for (int i = 0; i < num_nodes && iters > 0; i++, iters--) {
519 int end = std::min(num_nodes, i + 5);
520 for (int j = i + 1; j < end; j++) {
521 if (nodes[i] >= 0 && nodes[j] >= 0) {
522 CHECK(g.InsertEdge(nodes[i], nodes[j]));
523 }
524 }
525 }
526 delete[] nodes;
527 }
528 }
529 BENCHMARK(BM_StressTest)->Range(2048, 1048576);
530