[6a3a178] | 1 | var dep_graph = require("../lib/dep_graph");
|
---|
| 2 | var DepGraph = dep_graph.DepGraph;
|
---|
| 3 |
|
---|
| 4 | describe("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 |
|
---|
| 482 | describe("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 |
|
---|
| 523 | describe("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 | });
|
---|