SERVER-34292 Add JavaScript class for representing a directed graph.

It implements cycle detection using a modified version of topology sort
via depth-first search.

1 files changed, 79 insertions, 0 deletions

diff --git a/jstests/noPassthrough/cycle_detection_test.js b/jstests/noPassthrough/cycle_detection_test.js
new file mode 100644
index 00000000000..516dcb00a0f
--- /dev/null
+++ b/jstests/noPassthrough/cycle_detection_test.js
@@ -0,0 +1,79 @@
+/**
+ * Tests for the Graph#findCycle() method.
+ */
+(function() {
+    'use strict';
+
+    load('jstests/libs/cycle_detection.js');  // for Graph
+
+    (function testLinearChainHasNoCycle() {
+        const graph = new Graph();
+        graph.addEdge('A', 'B');
+        graph.addEdge('B', 'C');
+        graph.addEdge('C', 'D');
+
+        assert.eq([], graph.findCycle());
+    })();
+
+    (function testGraphWithoutCycleButCommonAncestor() {
+        const graph = new Graph();
+        graph.addEdge('A', 'B');
+        graph.addEdge('A', 'C');
+        graph.addEdge('B', 'D');
+        graph.addEdge('C', 'D');
+
+        assert.eq([], graph.findCycle());
+    })();
+
+    (function testEmptyGraphHasNoCycle() {
+        const graph = new Graph();
+        assert.eq([], graph.findCycle());
+    })();
+
+    (function testGraphWithAllNodesInCycle() {
+        const graph = new Graph();
+        graph.addEdge(1, 2);
+        graph.addEdge(2, 3);
+        graph.addEdge(3, 4);
+        graph.addEdge(4, 5);
+        graph.addEdge(5, 1);
+
+        assert.eq([1, 2, 3, 4, 5, 1], graph.findCycle());
+    })();
+
+    (function testGraphWithSomeNodesNotInCycle() {
+        const graph = new Graph();
+        graph.addEdge(1, 2);
+        graph.addEdge(2, 3);
+        graph.addEdge(3, 4);
+        graph.addEdge(4, 5);
+        graph.addEdge(5, 3);
+
+        assert.eq([3, 4, 5, 3], graph.findCycle());
+    })();
+
+    (function testGraphWithSelfLoopConsideredCycle() {
+        const graph = new Graph();
+        graph.addEdge(0, 0);
+        assert.eq([0, 0], graph.findCycle());
+    })();
+
+    (function testGraphUsesNonReferentialEquality() {
+        const w = {a: new NumberInt(1)};
+        const x = {a: new NumberInt(1)};
+        const y = {a: new NumberLong(1)};
+        const z = {a: 1};
+
+        let graph = new Graph();
+        graph.addEdge(w, x);
+        assert.eq([w, x], graph.findCycle());
+
+        graph = new Graph();
+        graph.addEdge(w, y);
+        assert.eq([], graph.findCycle());
+
+        graph = new Graph();
+        graph.addEdge(w, z);
+        assert.eq([w, z], graph.findCycle());
+    })();
+})();