source: trip-planner-front/node_modules/dependency-graph/specs/dep_graph_spec.js

Last change on this file was 6a3a178, checked in by Ema <ema_spirova@…>, 3 years ago

initial commit
  • Property mode set to 100644
File size: 14.9 KB
Line 
1var dep_graph = require("../lib/dep_graph");
2var DepGraph = dep_graph.DepGraph;
3
4describe("DepGraph", function () {
5 it("should be able to add/remove nodes", function () {
6 var graph = new DepGraph();
7
8 graph.addNode("Foo");
9 graph.addNode("Bar");
10
11 expect(graph.hasNode("Foo")).toBeTrue();
12 expect(graph.hasNode("Bar")).toBeTrue();
13 expect(graph.hasNode("NotThere")).toBeFalse();
14
15 graph.removeNode("Bar");
16
17 expect(graph.hasNode("Bar")).toBeFalse();
18 });
19
20 it("should calculate its size", function () {
21 var graph = new DepGraph();
22
23 expect(graph.size()).toBe(0);
24
25 graph.addNode("Foo");
26 graph.addNode("Bar");
27
28 expect(graph.size()).toBe(2);
29
30 graph.removeNode("Bar");
31
32 expect(graph.size()).toBe(1);
33 });
34
35 it("should treat the node data parameter as optional and use the node name as data if node data was not given", function () {
36 var graph = new DepGraph();
37
38 graph.addNode("Foo");
39
40 expect(graph.getNodeData("Foo")).toBe("Foo");
41 });
42
43 it("should be able to associate a node name with data on node add", function () {
44 var graph = new DepGraph();
45
46 graph.addNode("Foo", "data");
47
48 expect(graph.getNodeData("Foo")).toBe("data");
49 });
50
51 it("should be able to add undefined as node data", function () {
52 var graph = new DepGraph();
53
54 graph.addNode("Foo", undefined);
55
56 expect(graph.getNodeData("Foo")).toBeUndefined();
57 });
58
59 it("should return true when using hasNode with a node which has falsy data", function () {
60 var graph = new DepGraph();
61
62 var falsyData = ["", 0, null, undefined, false];
63 graph.addNode("Foo");
64
65 falsyData.forEach(function (data) {
66 graph.setNodeData("Foo", data);
67
68 expect(graph.hasNode("Foo")).toBeTrue();
69
70 // Just an extra check to make sure that the saved data is correct
71 expect(graph.getNodeData("Foo")).toBe(data);
72 });
73 });
74
75 it("should be able to set data after a node was added", function () {
76 var graph = new DepGraph();
77
78 graph.addNode("Foo", "data");
79 graph.setNodeData("Foo", "data2");
80
81 expect(graph.getNodeData("Foo")).toBe("data2");
82 });
83
84 it("should throw an error if we try to set data for a non-existing node", function () {
85 var graph = new DepGraph();
86
87 expect(function () {
88 graph.setNodeData("Foo", "data");
89 }).toThrow(new Error("Node does not exist: Foo"));
90 });
91
92 it("should throw an error if the node does not exists and we try to get data", function () {
93 var graph = new DepGraph();
94
95 expect(function () {
96 graph.getNodeData("Foo");
97 }).toThrow(new Error("Node does not exist: Foo"));
98 });
99
100 it("should do nothing if creating a node that already exists", function () {
101 var graph = new DepGraph();
102
103 graph.addNode("a");
104 graph.addNode("b");
105
106 graph.addDependency("a", "b");
107
108 graph.addNode("a");
109
110 expect(graph.dependenciesOf("a")).toEqual(["b"]);
111 });
112
113 it("should do nothing if removing a node that does not exist", function () {
114 var graph = new DepGraph();
115
116 graph.addNode("a");
117 expect(graph.hasNode("a")).toBeTrue();
118
119 graph.removeNode("a");
120 expect(graph.hasNode("Foo")).toBeFalse();
121
122 graph.removeNode("a");
123 expect(graph.hasNode("Foo")).toBeFalse();
124 });
125
126 it("should be able to add dependencies between nodes", function () {
127 var graph = new DepGraph();
128
129 graph.addNode("a");
130 graph.addNode("b");
131 graph.addNode("c");
132
133 graph.addDependency("a", "b");
134 graph.addDependency("a", "c");
135
136 expect(graph.dependenciesOf("a")).toEqual(["b", "c"]);
137 });
138
139 it("should find entry nodes", function () {
140 var graph = new DepGraph();
141
142 graph.addNode("a");
143 graph.addNode("b");
144 graph.addNode("c");
145
146 graph.addDependency("a", "b");
147 graph.addDependency("a", "c");
148
149 expect(graph.entryNodes()).toEqual(["a"]);
150 });
151
152 it("should throw an error if a node does not exist and a dependency is added", function () {
153 var graph = new DepGraph();
154
155 graph.addNode("a");
156
157 expect(function () {
158 graph.addDependency("a", "b");
159 }).toThrow(new Error("Node does not exist: b"));
160 });
161
162 it("should detect cycles", function () {
163 var graph = new DepGraph();
164
165 graph.addNode("a");
166 graph.addNode("b");
167 graph.addNode("c");
168 graph.addNode("d");
169
170 graph.addDependency("a", "b");
171 graph.addDependency("b", "c");
172 graph.addDependency("c", "a");
173 graph.addDependency("d", "a");
174
175 expect(function () {
176 graph.dependenciesOf("b");
177 }).toThrow(new dep_graph.DepGraphCycleError(["b", "c", "a", "b"]));
178 });
179
180 it("should allow cycles when configured", function () {
181 var graph = new DepGraph({ circular: true });
182
183 graph.addNode("a");
184 graph.addNode("b");
185 graph.addNode("c");
186 graph.addNode("d");
187
188 graph.addDependency("a", "b");
189 graph.addDependency("b", "c");
190 graph.addDependency("c", "a");
191 graph.addDependency("d", "a");
192
193 expect(graph.dependenciesOf("b")).toEqual(["a", "c"]);
194 expect(graph.overallOrder()).toEqual(["c", "b", "a", "d"]);
195 });
196
197 it(
198 "should include all nodes in overall order even from " +
199 "cycles in disconnected subgraphs when circular is true",
200 function () {
201 var graph = new DepGraph({ circular: true });
202
203 graph.addNode("2a");
204 graph.addNode("2b");
205 graph.addNode("2c");
206 graph.addDependency("2a", "2b");
207 graph.addDependency("2b", "2c");
208 graph.addDependency("2c", "2a");
209
210 graph.addNode("1a");
211 graph.addNode("1b");
212 graph.addNode("1c");
213 graph.addNode("1d");
214 graph.addNode("1e");
215
216 graph.addDependency("1a", "1b");
217 graph.addDependency("1a", "1c");
218 graph.addDependency("1b", "1c");
219 graph.addDependency("1c", "1d");
220
221 expect(graph.overallOrder()).toEqual([
222 "1d",
223 "1c",
224 "1b",
225 "1a",
226 "1e",
227 "2c",
228 "2b",
229 "2a"
230 ]);
231 }
232 );
233
234 it("should detect cycles in overall order", function () {
235 var graph = new DepGraph();
236
237 graph.addNode("a");
238 graph.addNode("b");
239 graph.addNode("c");
240 graph.addNode("d");
241
242 graph.addDependency("a", "b");
243 graph.addDependency("b", "c");
244 graph.addDependency("c", "a");
245 graph.addDependency("d", "a");
246
247 expect(function () {
248 graph.overallOrder();
249 }).toThrow(new dep_graph.DepGraphCycleError(["a", "b", "c", "a"]));
250 });
251
252 it("should detect cycles in overall order when all nodes have dependants (incoming edges)", function () {
253 var graph = new DepGraph();
254
255 graph.addNode("a");
256 graph.addNode("b");
257 graph.addNode("c");
258
259 graph.addDependency("a", "b");
260 graph.addDependency("b", "c");
261 graph.addDependency("c", "a");
262
263 expect(function () {
264 graph.overallOrder();
265 }).toThrow(new dep_graph.DepGraphCycleError(["a", "b", "c", "a"]));
266 });
267
268 it(
269 "should detect cycles in overall order when there are several " +
270 "disconnected subgraphs (with one that does not have a cycle",
271 function () {
272 var graph = new DepGraph();
273
274 graph.addNode("a_1");
275 graph.addNode("a_2");
276 graph.addNode("b_1");
277 graph.addNode("b_2");
278 graph.addNode("b_3");
279
280 graph.addDependency("a_1", "a_2");
281 graph.addDependency("b_1", "b_2");
282 graph.addDependency("b_2", "b_3");
283 graph.addDependency("b_3", "b_1");
284
285 expect(function () {
286 graph.overallOrder();
287 }).toThrow(
288 new dep_graph.DepGraphCycleError(["b_1", "b_2", "b_3", "b_1"])
289 );
290 }
291 );
292
293 it("should retrieve dependencies and dependants in the correct order", function () {
294 var graph = new DepGraph();
295
296 graph.addNode("a");
297 graph.addNode("b");
298 graph.addNode("c");
299 graph.addNode("d");
300
301 graph.addDependency("a", "d");
302 graph.addDependency("a", "b");
303 graph.addDependency("b", "c");
304 graph.addDependency("d", "b");
305
306 expect(graph.dependenciesOf("a")).toEqual(["c", "b", "d"]);
307 expect(graph.dependenciesOf("b")).toEqual(["c"]);
308 expect(graph.dependenciesOf("c")).toEqual([]);
309 expect(graph.dependenciesOf("d")).toEqual(["c", "b"]);
310
311 expect(graph.dependantsOf("a")).toEqual([]);
312 expect(graph.dependantsOf("b")).toEqual(["a", "d"]);
313 expect(graph.dependantsOf("c")).toEqual(["a", "d", "b"]);
314 expect(graph.dependantsOf("d")).toEqual(["a"]);
315
316 // check the alias "dependentsOf"
317 expect(graph.dependentsOf("a")).toEqual([]);
318 expect(graph.dependentsOf("b")).toEqual(["a", "d"]);
319 expect(graph.dependentsOf("c")).toEqual(["a", "d", "b"]);
320 expect(graph.dependentsOf("d")).toEqual(["a"]);
321 });
322
323 it("should be able to retrieve direct dependencies/dependants", function () {
324 var graph = new DepGraph();
325
326 graph.addNode("a");
327 graph.addNode("b");
328 graph.addNode("c");
329 graph.addNode("d");
330
331 graph.addDependency("a", "d");
332 graph.addDependency("a", "b");
333 graph.addDependency("b", "c");
334 graph.addDependency("d", "b");
335
336 expect(graph.directDependenciesOf("a")).toEqual(["d", "b"]);
337 expect(graph.directDependenciesOf("b")).toEqual(["c"]);
338 expect(graph.directDependenciesOf("c")).toEqual([]);
339 expect(graph.directDependenciesOf("d")).toEqual(["b"]);
340
341 expect(graph.directDependantsOf("a")).toEqual([]);
342 expect(graph.directDependantsOf("b")).toEqual(["a", "d"]);
343 expect(graph.directDependantsOf("c")).toEqual(["b"]);
344 expect(graph.directDependantsOf("d")).toEqual(["a"]);
345
346 // check the alias "directDependentsOf"
347 expect(graph.directDependentsOf("a")).toEqual([]);
348 expect(graph.directDependentsOf("b")).toEqual(["a", "d"]);
349 expect(graph.directDependentsOf("c")).toEqual(["b"]);
350 expect(graph.directDependentsOf("d")).toEqual(["a"]);
351 });
352
353 it("should be able to resolve the overall order of things", function () {
354 var graph = new DepGraph();
355
356 graph.addNode("a");
357 graph.addNode("b");
358 graph.addNode("c");
359 graph.addNode("d");
360 graph.addNode("e");
361
362 graph.addDependency("a", "b");
363 graph.addDependency("a", "c");
364 graph.addDependency("b", "c");
365 graph.addDependency("c", "d");
366
367 expect(graph.overallOrder()).toEqual(["d", "c", "b", "a", "e"]);
368 });
369
370 it('should be able to only retrieve the "leaves" in the overall order', function () {
371 var graph = new DepGraph();
372
373 graph.addNode("a");
374 graph.addNode("b");
375 graph.addNode("c");
376 graph.addNode("d");
377 graph.addNode("e");
378
379 graph.addDependency("a", "b");
380 graph.addDependency("a", "c");
381 graph.addDependency("b", "c");
382 graph.addDependency("c", "d");
383
384 expect(graph.overallOrder(true)).toEqual(["d", "e"]);
385 });
386
387 it("should be able to give the overall order for a graph with several disconnected subgraphs", function () {
388 var graph = new DepGraph();
389
390 graph.addNode("a_1");
391 graph.addNode("a_2");
392 graph.addNode("b_1");
393 graph.addNode("b_2");
394 graph.addNode("b_3");
395
396 graph.addDependency("a_1", "a_2");
397 graph.addDependency("b_1", "b_2");
398 graph.addDependency("b_2", "b_3");
399
400 expect(graph.overallOrder()).toEqual(["a_2", "a_1", "b_3", "b_2", "b_1"]);
401 });
402
403 it("should give an empty overall order for an empty graph", function () {
404 var graph = new DepGraph();
405
406 expect(graph.overallOrder()).toEqual([]);
407 });
408
409 it("should still work after nodes are removed", function () {
410 var graph = new DepGraph();
411
412 graph.addNode("a");
413 graph.addNode("b");
414 graph.addNode("c");
415 graph.addDependency("a", "b");
416 graph.addDependency("b", "c");
417
418 expect(graph.dependenciesOf("a")).toEqual(["c", "b"]);
419
420 graph.removeNode("c");
421
422 expect(graph.dependenciesOf("a")).toEqual(["b"]);
423 });
424
425 it("should clone an empty graph", function () {
426 var graph = new DepGraph();
427 expect(graph.size()).toEqual(0);
428 var cloned = graph.clone();
429 expect(cloned.size()).toEqual(0);
430
431 expect(graph === cloned).toBeFalse();
432 });
433
434 it("should clone a non-empty graph", function () {
435 var graph = new DepGraph();
436
437 graph.addNode("a");
438 graph.addNode("b");
439 graph.addNode("c");
440 graph.addDependency("a", "b");
441 graph.addDependency("b", "c");
442
443 var cloned = graph.clone();
444
445 expect(graph === cloned).toBeFalse();
446 expect(cloned.hasNode("a")).toBeTrue();
447 expect(cloned.hasNode("b")).toBeTrue();
448 expect(cloned.hasNode("c")).toBeTrue();
449 expect(cloned.dependenciesOf("a")).toEqual(["c", "b"]);
450 expect(cloned.dependantsOf("c")).toEqual(["a", "b"]);
451
452 // Changes to the original graph shouldn't affect the clone
453 graph.removeNode("c");
454 expect(graph.dependenciesOf("a")).toEqual(["b"]);
455 expect(cloned.dependenciesOf("a")).toEqual(["c", "b"]);
456
457 graph.addNode("d");
458 graph.addDependency("b", "d");
459 expect(graph.dependenciesOf("a")).toEqual(["d", "b"]);
460 expect(cloned.dependenciesOf("a")).toEqual(["c", "b"]);
461 });
462
463 it("should only be a shallow clone", function () {
464 var graph = new DepGraph();
465
466 var data = { a: 42 };
467 graph.addNode("a", data);
468
469 var cloned = graph.clone();
470 expect(graph === cloned).toBeFalse();
471 expect(graph.getNodeData("a") === cloned.getNodeData("a")).toBeTrue();
472
473 graph.getNodeData("a").a = 43;
474 expect(cloned.getNodeData("a").a).toBe(43);
475
476 cloned.setNodeData("a", { a: 42 });
477 expect(cloned.getNodeData("a").a).toBe(42);
478 expect(graph.getNodeData("a") === cloned.getNodeData("a")).toBeFalse();
479 });
480});
481
482describe("DepGraph Performance", function () {
483 it("should not exceed max call stack with a very deep graph", function () {
484 var g = new DepGraph();
485 var expected = [];
486 for (var i = 0; i < 100000; i++) {
487 var istr = i.toString();
488 g.addNode(istr);
489 expected.push(istr);
490 if (i > 0) {
491 g.addDependency(istr, (i - 1).toString());
492 }
493 }
494 var order = g.overallOrder();
495 expect(order).toEqual(expected);
496 });
497
498 it("should run an a reasonable amount of time for a very large graph", function () {
499 var randInt = function (min, max) {
500 return Math.floor(Math.random() * (max - min + 1)) + min;
501 };
502 var g = new DepGraph();
503 var nodes = [];
504 // Create a graph with 100000 nodes in it with 10 random connections to
505 // lower numbered nodes
506 for (var i = 0; i < 100000; i++) {
507 nodes.push(i.toString());
508 g.addNode(i.toString());
509 for (var j = 0; j < 10; j++) {
510 var dep = randInt(0, i);
511 if (i !== dep) {
512 g.addDependency(i.toString(), dep.toString());
513 }
514 }
515 }
516 var start = new Date().getTime();
517 g.overallOrder();
518 var end = new Date().getTime();
519 expect(start - end).toBeLessThan(1000);
520 });
521});
522
523describe("DepGraphCycleError", function () {
524 var DepGraphCycleError = dep_graph.DepGraphCycleError;
525
526 it("should have a message", function () {
527 var err = new DepGraphCycleError(["a", "b", "c", "a"]);
528 expect(err.message).toEqual("Dependency Cycle Found: a -> b -> c -> a");
529 });
530
531 it("should be an instanceof DepGraphCycleError", function () {
532 var err = new DepGraphCycleError(["a", "b", "c", "a"]);
533 expect(err instanceof DepGraphCycleError).toBeTrue();
534 expect(err instanceof Error).toBeTrue();
535 });
536
537 it("should have a cyclePath", function () {
538 var cyclePath = ["a", "b", "c", "a"];
539 var err = new DepGraphCycleError(cyclePath);
540 expect(err.cyclePath).toEqual(cyclePath);
541 });
542});
Note: See TracBrowser for help on using the repository browser.