| 1 | import { assert, describe, it } from "@effect/vitest" |
| 2 | import { Equal, Graph, Hash, Option } from "effect" |
| 3 | |
| 4 | const directed = <N, E>( |
| 5 | nodes: ReadonlyArray<N>, |
| 6 | edges: ReadonlyArray<readonly [Graph.NodeIndex, Graph.NodeIndex, E]> |
| 7 | ) => |
| 8 | Graph.directed<N, E>((mutable) => { |
| 9 | for (const node of nodes) Graph.addNode(mutable, node) |
| 10 | for (const [source, target, data] of edges) Graph.addEdge(mutable, source, target, data) |
| 11 | }) |
| 12 | |
| 13 | const undirected = <N, E>( |
| 14 | nodes: ReadonlyArray<N>, |
| 15 | edges: ReadonlyArray<readonly [Graph.NodeIndex, Graph.NodeIndex, E]> |
| 16 | ) => |
| 17 | Graph.undirected<N, E>((mutable) => { |
| 18 | for (const node of nodes) Graph.addNode(mutable, node) |
| 19 | for (const [source, target, data] of edges) Graph.addEdge(mutable, source, target, data) |
| 20 | }) |
| 21 | |
| 22 | const assertGraphError = (thunk: () => unknown, message: string): void => { |
| 23 | let error: unknown |
| 24 | try { |
| 25 | thunk() |
| 26 | } catch (cause) { |
| 27 | error = cause |
| 28 | } |
| 29 | assert.ok(error instanceof Graph.GraphError) |
| 30 | assert.strictEqual(error.message, message) |
| 31 | } |
| 32 | |
| 33 | const assertSnapshot = <N, E, T extends Graph.Kind>( |
| 34 | graph: Graph.Graph<N, E, T> | Graph.MutableGraph<N, E, T>, |
| 35 | expected: Graph.Snapshot<N, E, T> |
| 36 | ): void => { |
| 37 | assert.deepStrictEqual(Graph.toSnapshot(graph), expected) |
| 38 | } |
| 39 | |
| 40 | const assertPath = <E>(actual: Option.Option<Graph.PathResult<E>>, expected: Graph.PathResult<E>): void => { |
| 41 | assert.deepStrictEqual(actual, Option.some(expected)) |
| 42 | } |
| 43 | |
| 44 | const assertComponents = ( |
| 45 | actual: ReadonlyArray<ReadonlyArray<number>>, |
| 46 | expected: ReadonlyArray<ReadonlyArray<number>> |
| 47 | ) => { |
| 48 | const canonicalize = (components: ReadonlyArray<ReadonlyArray<number>>) => |
| 49 | components.map((component) => Array.from(component).sort((a, b) => a - b)).sort((a, b) => a[0] - b[0]) |
| 50 | assert.deepStrictEqual(canonicalize(actual), canonicalize(expected)) |
| 51 | } |
| 52 | |
| 53 | const assertIndices = <N>(walker: Graph.NodeWalker<N>, expected: ReadonlyArray<number>): void => { |
| 54 | assert.deepStrictEqual(Array.from(Graph.indices(walker)), expected) |
| 55 | } |
| 56 | |
| 57 | describe("Graph", () => { |
| 58 | describe("construction and protocols", () => { |
| 59 | it("constructs directed and undirected graphs", () => { |
| 60 | const directedGraph = Graph.make("directed")<string, number>() |
| 61 | const undirectedGraph = Graph.undirected<string, number>() |
| 62 | |
| 63 | assert.strictEqual(directedGraph.type, "directed") |
| 64 | assert.strictEqual(undirectedGraph.type, "undirected") |
| 65 | assert.strictEqual(directedGraph.mutable, false) |
| 66 | assert.strictEqual(Graph.nodeCount(directedGraph), 0) |
| 67 | assert.strictEqual(Graph.edgeCount(undirectedGraph), 0) |
| 68 | }) |
| 69 | |
| 70 | it("rejects invalid runtime graph kinds", () => { |
| 71 | assertGraphError( |
| 72 | () => Graph.make("invalid" as Graph.Kind)<never, never>(), |
| 73 | "Graph type must be directed or undirected" |
| 74 | ) |
| 75 | }) |
| 76 | |
| 77 | it("recognizes immutable and mutable graphs only", () => { |
| 78 | assert.strictEqual(Graph.isGraph(Graph.directed()), true) |
| 79 | assert.strictEqual(Graph.isGraph(Graph.beginMutation(Graph.undirected())), true) |
| 80 | for (const value of [{}, null, undefined, "graph", 1, []]) { |
| 81 | assert.strictEqual(Graph.isGraph(value), false) |
| 82 | } |
| 83 | }) |
| 84 | |
| 85 | it("supports stringification, piping, and node iteration in graph order", () => { |
| 86 | const graph = directed(["A", "B"], [[0, 1, 1]]) |
| 87 | |
| 88 | assert.strictEqual(String(graph), "Graph(directed, 2, 1)") |
| 89 | assert.strictEqual(graph.pipe(Graph.nodeCount), 2) |
| 90 | assert.deepStrictEqual(Array.from(graph), [[0, "A"], [1, "B"]]) |
| 91 | const iterator = graph[Symbol.iterator]() |
| 92 | assert.deepStrictEqual(iterator.next(), { done: false, value: [0, "A"] }) |
| 93 | assert.deepStrictEqual(iterator.next(), { done: false, value: [1, "B"] }) |
| 94 | assert.deepStrictEqual(iterator.next(), { done: true, value: undefined }) |
| 95 | }) |
| 96 | }) |
| 97 | |
| 98 | describe("snapshots", () => { |
| 99 | it("round-trips sparse indexes, parallel edges, self-loops, and stored orientation", () => { |
| 100 | const snapshot = { |
| 101 | type: "undirected", |
| 102 | nodes: [{ index: 2, data: "A" }, { index: 5, data: "B" }], |
| 103 | edges: [ |
| 104 | { index: 3, source: 5, target: 2, data: "first" }, |
| 105 | { index: 7, source: 5, target: 2, data: "parallel" }, |
| 106 | { index: 11, source: 5, target: 5, data: "loop" } |
| 107 | ] |
| 108 | } as const |
| 109 | const graph = Graph.fromSnapshot(snapshot) |
| 110 | |
| 111 | assertSnapshot(graph, snapshot) |
| 112 | assert.deepStrictEqual(Graph.neighbors(graph, 2), [5]) |
| 113 | assert.deepStrictEqual(Graph.neighbors(graph, 5), [2, 5]) |
| 114 | assert.strictEqual(Equal.equals(Graph.fromSnapshot(Graph.toSnapshot(graph)), graph), true) |
| 115 | }) |
| 116 | |
| 117 | it("snapshots mutable state without exposing stored records", () => { |
| 118 | const graph = directed(["A", "B"], [[0, 1, 1]]) |
| 119 | const mutable = Graph.beginMutation(graph) |
| 120 | Graph.updateNode(mutable, 0, () => "updated") |
| 121 | const snapshot = Graph.toSnapshot(mutable) |
| 122 | ;(snapshot.nodes[0] as { index: number; data: string }).index = 1 |
| 123 | ;(snapshot.nodes[0] as { index: number; data: string }).data = "exposed" |
| 124 | ;(snapshot.edges[0] as { source: number; data: number }).source = 1 |
| 125 | ;(snapshot.edges[0] as { source: number; data: number }).data = 2 |
| 126 | |
| 127 | assertSnapshot(mutable, { |
| 128 | type: "directed", |
| 129 | nodes: [{ index: 0, data: "updated" }, { index: 1, data: "B" }], |
| 130 | edges: [{ index: 0, source: 0, target: 1, data: 1 }] |
| 131 | }) |
| 132 | }) |
| 133 | |
| 134 | it("continues allocation after the highest active snapshot indexes", () => { |
| 135 | const mutable = Graph.beginMutation(Graph.fromSnapshot({ |
| 136 | type: "directed", |
| 137 | nodes: [{ index: 2, data: "A" }, { index: 5, data: "B" }], |
| 138 | edges: [{ index: 4, source: 2, target: 5, data: 1 }] |
| 139 | })) |
| 140 | |
| 141 | assert.strictEqual(Graph.addNode(mutable, "C"), 6) |
| 142 | assert.strictEqual(Graph.addEdge(mutable, 2, 5, 2), 5) |
| 143 | }) |
| 144 | |
| 145 | it("rejects malformed snapshot records and indexes", () => { |
| 146 | const cases: ReadonlyArray<readonly [() => unknown, string]> = [ |
| 147 | [ |
| 148 | () => |
| 149 | Graph.fromSnapshot( |
| 150 | { type: "invalid", nodes: [], edges: [] } as unknown as Graph.Snapshot<never, never, Graph.Kind> |
| 151 | ), |
| 152 | "Snapshot type must be directed or undirected" |
| 153 | ], |
| 154 | [ |
| 155 | () => Graph.fromSnapshot({ type: "directed", nodes: new Array(1), edges: [] }), |
| 156 | "Node at position 0 must be defined" |
| 157 | ], |
| 158 | [ |
| 159 | () => |
| 160 | Graph.fromSnapshot( |
| 161 | { type: "directed", nodes: [null], edges: [] } as unknown as Graph.Snapshot<never, never, "directed"> |
| 162 | ), |
| 163 | "Node at position 0 must be defined" |
| 164 | ], |
| 165 | [ |
| 166 | () => Graph.fromSnapshot({ type: "directed", nodes: [{ index: -1, data: "A" }], edges: [] }), |
| 167 | "Node index at position 0 must be a non-negative safe integer" |
| 168 | ], |
| 169 | [ |
| 170 | () => |
| 171 | Graph.fromSnapshot({ |
| 172 | type: "directed", |
| 173 | nodes: [{ index: Number.MAX_SAFE_INTEGER + 1, data: "A" }], |
| 174 | edges: [] |
| 175 | }), |
| 176 | "Node index at position 0 must be a non-negative safe integer" |
| 177 | ], |
| 178 | [ |
| 179 | () => |
| 180 | Graph.fromSnapshot({ |
| 181 | type: "directed", |
| 182 | nodes: [{ index: 1, data: "A" }, { index: 1, data: "B" }], |
| 183 | edges: [] |
| 184 | }), |
| 185 | "Node indexes must be strictly increasing" |
| 186 | ], |
| 187 | [ |
| 188 | () => Graph.fromSnapshot({ type: "directed", nodes: [{ index: 0, data: "A" }], edges: new Array(1) }), |
| 189 | "Edge at position 0 must be defined" |
| 190 | ], |
| 191 | [ |
| 192 | () => |
| 193 | Graph.fromSnapshot({ |
| 194 | type: "directed", |
| 195 | nodes: [{ index: 0, data: "A" }], |
| 196 | edges: [{ index: 0.5, source: 0, target: 0, data: 1 }] |
| 197 | }), |
| 198 | "Edge index at position 0 must be a non-negative safe integer" |
| 199 | ], |
| 200 | [ |
| 201 | () => |
| 202 | Graph.fromSnapshot({ |
| 203 | type: "directed", |
| 204 | nodes: [{ index: 0, data: "A" }], |
| 205 | edges: [{ index: 1, source: 0, target: 0, data: 1 }, { index: 1, source: 0, target: 0, data: 2 }] |
| 206 | }), |
| 207 | "Edge indexes must be strictly increasing" |
| 208 | ], |
| 209 | [ |
| 210 | () => |
| 211 | Graph.fromSnapshot({ |
| 212 | type: "directed", |
| 213 | nodes: [{ index: 0, data: "A" }], |
| 214 | edges: [{ index: 0, source: -1, target: 0, data: 1 }] |
| 215 | }), |
| 216 | "Edge source at position 0 must be a non-negative safe integer" |
| 217 | ], |
| 218 | [ |
| 219 | () => |
| 220 | Graph.fromSnapshot({ |
| 221 | type: "directed", |
| 222 | nodes: [{ index: 0, data: "A" }], |
| 223 | edges: [{ index: 0, source: 0, target: 0.5, data: 1 }] |
| 224 | }), |
| 225 | "Edge target at position 0 must be a non-negative safe integer" |
| 226 | ], |
| 227 | [ |
| 228 | () => |
| 229 | Graph.fromSnapshot({ |
| 230 | type: "directed", |
| 231 | nodes: [{ index: 1, data: "A" }], |
| 232 | edges: [{ index: 0, source: 0, target: 1, data: 1 }] |
| 233 | }), |
| 234 | "Edge source 0 does not reference a node" |
| 235 | ], |
| 236 | [ |
| 237 | () => |
| 238 | Graph.fromSnapshot({ |
| 239 | type: "directed", |
| 240 | nodes: [{ index: 1, data: "A" }], |
| 241 | edges: [{ index: 0, source: 1, target: 2, data: 1 }] |
| 242 | }), |
| 243 | "Edge target 2 does not reference a node" |
| 244 | ] |
| 245 | ] |
| 246 | |
| 247 | for (const [run, message] of cases) assertGraphError(run, message) |
| 248 | }) |
| 249 | |
| 250 | it("rejects allocation after safe indexes are exhausted", () => { |
| 251 | const nodes = Graph.beginMutation(Graph.fromSnapshot({ |
| 252 | type: "directed", |
| 253 | nodes: [{ index: Number.MAX_SAFE_INTEGER, data: "A" }], |
| 254 | edges: [] |
| 255 | })) |
| 256 | const edges = Graph.beginMutation(Graph.fromSnapshot({ |
| 257 | type: "directed", |
| 258 | nodes: [{ index: 0, data: "A" }], |
| 259 | edges: [{ index: Number.MAX_SAFE_INTEGER, source: 0, target: 0, data: 1 }] |
| 260 | })) |
| 261 | |
| 262 | assertGraphError(() => Graph.addNode(nodes, "B"), "Graph has exhausted safe node indexes") |
| 263 | assertGraphError(() => Graph.addEdge(edges, 0, 0, 2), "Graph has exhausted safe edge indexes") |
| 264 | }) |
| 265 | }) |
| 266 | |
| 267 | describe("equality and hashing", () => { |
| 268 | it("gives equal immutable graphs equal hashes", () => { |
| 269 | const left = undirected(["A", "B"], [[0, 1, "first"], [0, 1, "second"], [0, 0, "loop"]]) |
| 270 | const right = undirected(["A", "B"], [[1, 0, "first"], [1, 0, "second"], [0, 0, "loop"]]) |
| 271 | |
| 272 | assert.strictEqual(Equal.equals(left, right), true) |
| 273 | assert.strictEqual(Hash.hash(left), Hash.hash(right)) |
| 274 | }) |
| 275 | |
| 276 | it("distinguishes undirected self-loops on different nodes", () => { |
| 277 | const onA = undirected(["A", "B"], [[0, 0, "loop"]]) |
| 278 | const onB = undirected(["A", "B"], [[1, 1, "loop"]]) |
| 279 | |
| 280 | assert.strictEqual(Equal.equals(onA, onB), false) |
| 281 | assert.notStrictEqual(Hash.hash(onA), Hash.hash(onB)) |
| 282 | }) |
| 283 | |
| 284 | it("distinguishes node payload, edge payload, missing edge, kind, and sparse indexes", () => { |
| 285 | const base = directed(["A", "B"], [[0, 1, "edge"]]) |
| 286 | const cases: ReadonlyArray<Graph.Graph<unknown, unknown, Graph.Kind>> = [ |
| 287 | directed(["changed", "B"], [[0, 1, "edge"]]), |
| 288 | directed(["A", "B"], [[0, 1, "changed"]]), |
| 289 | directed(["A", "B"], []), |
| 290 | undirected(["A", "B"], [[0, 1, "edge"]]), |
| 291 | Graph.fromSnapshot({ |
| 292 | type: "directed", |
| 293 | nodes: [{ index: 2, data: "A" }, { index: 5, data: "B" }], |
| 294 | edges: [{ index: 3, source: 2, target: 5, data: "edge" }] |
| 295 | }) |
| 296 | ] |
| 297 | |
| 298 | for (const candidate of cases) { |
| 299 | assert.strictEqual(Equal.equals(base, candidate), false) |
| 300 | assert.strictEqual(Equal.equals(candidate, base), false) |
| 301 | } |
| 302 | }) |
| 303 | |
| 304 | it("keeps directed endpoints and parallel-edge index pairing ordered", () => { |
| 305 | const directedLeft = directed(["A", "B"], [[0, 1, "edge"]]) |
| 306 | const directedRight = directed(["A", "B"], [[1, 0, "edge"]]) |
| 307 | const parallel = undirected(["A", "B"], [[0, 1, "first"], [0, 1, "second"]]) |
| 308 | const reordered = undirected(["A", "B"], [[1, 0, "second"], [1, 0, "first"]]) |
| 309 | |
| 310 | assert.strictEqual(Equal.equals(directedLeft, directedRight), false) |
| 311 | assert.strictEqual(Equal.equals(parallel, reordered), false) |
| 312 | }) |
| 313 | |
| 314 | it("ignores removed trailing allocator history while preserving future allocation", () => { |
| 315 | const left = directed(["A", "B"], [[0, 1, "edge"]]) |
| 316 | const right = Graph.directed<string, string>((mutable) => { |
| 317 | Graph.addNode(mutable, "A") |
| 318 | Graph.addNode(mutable, "B") |
| 319 | Graph.addEdge(mutable, 0, 1, "edge") |
| 320 | const node = Graph.addNode(mutable, "removed") |
| 321 | const edge = Graph.addEdge(mutable, 0, 1, "removed") |
| 322 | Graph.removeNode(mutable, node) |
| 323 | Graph.removeEdge(mutable, edge) |
| 324 | }) |
| 325 | |
| 326 | assert.strictEqual(Equal.equals(left, right), true) |
| 327 | assert.strictEqual(Hash.hash(left), Hash.hash(right)) |
| 328 | Graph.mutate(left, (mutable) => { |
| 329 | assert.strictEqual(Graph.addNode(mutable, "next"), 2) |
| 330 | }) |
| 331 | Graph.mutate(right, (mutable) => { |
| 332 | assert.strictEqual(Graph.addNode(mutable, "next"), 3) |
| 333 | }) |
| 334 | Graph.mutate(left, (mutable) => { |
| 335 | assert.strictEqual(Graph.addEdge(mutable, 0, 1, "next"), 1) |
| 336 | }) |
| 337 | Graph.mutate(right, (mutable) => { |
| 338 | assert.strictEqual(Graph.addEdge(mutable, 0, 1, "next"), 2) |
| 339 | }) |
| 340 | }) |
| 341 | |
| 342 | it("uses reference equality for mutable graphs and structural equality after finalization", () => { |
| 343 | const graph = directed(["A", "B"], [[0, 1, "edge"]]) |
| 344 | const left = Graph.beginMutation(graph) |
| 345 | const right = Graph.beginMutation(graph) |
| 346 | const hash = Hash.hash(left) |
| 347 | |
| 348 | assert.strictEqual(Equal.equals(left, right), false) |
| 349 | Graph.addNode(left, "C") |
| 350 | assert.strictEqual(Hash.hash(left), hash) |
| 351 | const finalized = Graph.endMutation(left) |
| 352 | assert.strictEqual(Equal.equals(finalized, directed(["A", "B", "C"], [[0, 1, "edge"]])), true) |
| 353 | }) |
| 354 | |
| 355 | it("supports undefined node and edge payloads structurally", () => { |
| 356 | const make = () => directed<undefined, undefined>([undefined, undefined], [[0, 1, undefined]]) |
| 357 | assert.strictEqual(Equal.equals(make(), make()), true) |
| 358 | assert.strictEqual(Hash.hash(make()), Hash.hash(make())) |
| 359 | }) |
| 360 | }) |
| 361 | |
| 362 | describe("mutation lifecycle", () => { |
| 363 | it("isolates mutable changes from the source and finalizes to a new immutable graph", () => { |
| 364 | const source = directed(["A", "B"], [[0, 1, 1]]) |
| 365 | const mutable = Graph.beginMutation(source) |
| 366 | Graph.addNode(mutable, "C") |
| 367 | const result = Graph.endMutation(mutable) |
| 368 | |
| 369 | assert.strictEqual(Graph.nodeCount(source), 2) |
| 370 | assert.strictEqual(Graph.nodeCount(result), 3) |
| 371 | assert.notStrictEqual(result, source) |
| 372 | assert.strictEqual(result.mutable, false) |
| 373 | }) |
| 374 | |
| 375 | it("supports data-first and data-last scoped mutation", () => { |
| 376 | const graph = Graph.directed<string, number>() |
| 377 | const first = Graph.mutate(graph, (mutable) => { |
| 378 | Graph.addNode(mutable, "A") |
| 379 | }) |
| 380 | const last = graph.pipe(Graph.mutate((mutable) => { |
| 381 | Graph.addNode(mutable, "A") |
| 382 | })) |
| 383 | |
| 384 | assertSnapshot(first, { type: "directed", nodes: [{ index: 0, data: "A" }], edges: [] }) |
| 385 | assertSnapshot(last, { type: "directed", nodes: [{ index: 0, data: "A" }], edges: [] }) |
| 386 | }) |
| 387 | |
| 388 | it("finalizes retained handles when callbacks return or throw", () => { |
| 389 | let returned: Graph.MutableDirectedGraph<string, number> | undefined |
| 390 | Graph.directed<string, number>((mutable) => { |
| 391 | returned = mutable |
| 392 | }) |
| 393 | assertGraphError(() => Graph.addNode(returned!, "late"), "Graph is not mutable") |
| 394 | |
| 395 | let thrown: Graph.MutableDirectedGraph<string, number> | undefined |
| 396 | const cause = new Error("boom") |
| 397 | let actual: unknown |
| 398 | try { |
| 399 | Graph.mutate(Graph.directed<string, number>(), (mutable) => { |
| 400 | thrown = mutable |
| 401 | throw cause |
| 402 | }) |
| 403 | } catch (error) { |
| 404 | actual = error |
| 405 | } |
| 406 | assert.strictEqual(actual, cause) |
| 407 | assertGraphError(() => Graph.addNode(thrown!, "late"), "Graph is not mutable") |
| 408 | }) |
| 409 | |
| 410 | it("rejects normal callback return after manual finalization", () => { |
| 411 | assertGraphError(() => { |
| 412 | Graph.directed<string, number>((mutable) => { |
| 413 | Graph.endMutation(mutable) |
| 414 | }) |
| 415 | }, "Graph is not mutable") |
| 416 | assertGraphError(() => { |
| 417 | Graph.mutate(Graph.directed<string, number>(), (mutable) => { |
| 418 | Graph.endMutation(mutable) |
| 419 | }) |
| 420 | }, "Graph is not mutable") |
| 421 | }) |
| 422 | |
| 423 | it("preserves callback errors after manual finalization", () => { |
| 424 | const cause = new Error("callback failure") |
| 425 | for ( |
| 426 | const run of [ |
| 427 | () => |
| 428 | Graph.directed<string, number>((mutable) => { |
| 429 | Graph.endMutation(mutable) |
| 430 | throw cause |
| 431 | }), |
| 432 | () => |
| 433 | Graph.mutate(Graph.directed<string, number>(), (mutable) => { |
| 434 | Graph.endMutation(mutable) |
| 435 | throw cause |
| 436 | }) |
| 437 | ] |
| 438 | ) { |
| 439 | let actual: unknown |
| 440 | try { |
| 441 | run() |
| 442 | } catch (error) { |
| 443 | actual = error |
| 444 | } |
| 445 | assert.strictEqual(actual, cause) |
| 446 | } |
| 447 | }) |
| 448 | |
| 449 | it("rejects every mutation entry point on a finalized handle", () => { |
| 450 | const mutable = Graph.beginMutation(directed(["A", "B"], [[0, 1, 1]])) |
| 451 | Graph.endMutation(mutable) |
| 452 | const mutations: ReadonlyArray<() => unknown> = [ |
| 453 | () => Graph.addNode(mutable, "C"), |
| 454 | () => Graph.addEdge(mutable, 1, 0, 2), |
| 455 | () => Graph.updateNode(mutable, 0, () => "updated"), |
| 456 | () => Graph.updateEdge(mutable, 0, () => 2), |
| 457 | () => Graph.removeNode(mutable, 0), |
| 458 | () => Graph.removeNodes(mutable, [0]), |
| 459 | () => Graph.removeEdge(mutable, 0), |
| 460 | () => Graph.removeEdges(mutable, [0]), |
| 461 | () => Graph.mapNodes(mutable, () => "mapped"), |
| 462 | () => Graph.mapEdges(mutable, () => 3), |
| 463 | () => Graph.filterMapNodes(mutable, () => Option.none()), |
| 464 | () => Graph.filterMapEdges(mutable, () => Option.none()), |
| 465 | () => Graph.filterNodes(mutable, () => true), |
| 466 | () => Graph.filterEdges(mutable, () => true), |
| 467 | () => Graph.reverse(mutable), |
| 468 | () => Graph.endMutation(mutable) |
| 469 | ] |
| 470 | for (const mutation of mutations) assertGraphError(mutation, "Graph is not mutable") |
| 471 | }) |
| 472 | |
| 473 | it("rejects nested mutation or finalization from transformation callbacks", () => { |
| 474 | const mutable = Graph.beginMutation(directed(["A", "B"], [[0, 1, 1]])) |
| 475 | const mutations: ReadonlyArray<() => unknown> = [ |
| 476 | () => Graph.addNode(mutable, "C"), |
| 477 | () => Graph.addEdge(mutable, 1, 0, 2), |
| 478 | () => Graph.updateNode(mutable, 0, () => "updated"), |
| 479 | () => Graph.updateEdge(mutable, 0, () => 2), |
| 480 | () => Graph.removeNode(mutable, 0), |
| 481 | () => Graph.removeNodes(mutable, [0]), |
| 482 | () => Graph.removeEdge(mutable, 0), |
| 483 | () => Graph.removeEdges(mutable, [0]), |
| 484 | () => Graph.mapNodes(mutable, (node) => node), |
| 485 | () => Graph.mapEdges(mutable, (edge) => edge), |
| 486 | () => Graph.filterMapNodes(mutable, (node) => Option.some(node)), |
| 487 | () => Graph.filterMapEdges(mutable, (edge) => Option.some(edge)), |
| 488 | () => Graph.filterNodes(mutable, () => true), |
| 489 | () => Graph.filterEdges(mutable, () => true), |
| 490 | () => Graph.reverse(mutable), |
| 491 | () => Graph.endMutation(mutable) |
| 492 | ] |
| 493 | |
| 494 | for (const mutation of mutations) { |
| 495 | assertGraphError(() => |
| 496 | Graph.updateNode(mutable, 0, (node) => { |
| 497 | mutation() |
| 498 | return node |
| 499 | }), "Cannot mutate graph during a transformation") |
| 500 | } |
| 501 | assertSnapshot(mutable, { |
| 502 | type: "directed", |
| 503 | nodes: [{ index: 0, data: "A" }, { index: 1, data: "B" }], |
| 504 | edges: [{ index: 0, source: 0, target: 1, data: 1 }] |
| 505 | }) |
| 506 | }) |
| 507 | |
| 508 | it("guards every transformation callback against nested mutation", () => { |
| 509 | const mutable = Graph.beginMutation(directed(["A", "B"], [[0, 1, 1]])) |
| 510 | const mutate = () => Graph.addNode(mutable, "C") |
| 511 | const transformations: ReadonlyArray<() => unknown> = [ |
| 512 | () => |
| 513 | Graph.updateNode(mutable, 0, (node) => { |
| 514 | mutate() |
| 515 | return node |
| 516 | }), |
| 517 | () => |
| 518 | Graph.updateEdge(mutable, 0, (edge) => { |
| 519 | mutate() |
| 520 | return edge |
| 521 | }), |
| 522 | () => |
| 523 | Graph.mapNodes(mutable, (node) => { |
| 524 | mutate() |
| 525 | return node |
| 526 | }), |
| 527 | () => |
| 528 | Graph.mapEdges(mutable, (edge) => { |
| 529 | mutate() |
| 530 | return edge |
| 531 | }), |
| 532 | () => |
| 533 | Graph.filterMapNodes(mutable, (node) => { |
| 534 | mutate() |
| 535 | return Option.some(node) |
| 536 | }), |
| 537 | () => |
| 538 | Graph.filterMapEdges(mutable, (edge) => { |
| 539 | mutate() |
| 540 | return Option.some(edge) |
| 541 | }), |
| 542 | () => |
| 543 | Graph.filterNodes(mutable, () => { |
| 544 | mutate() |
| 545 | return true |
| 546 | }), |
| 547 | () => |
| 548 | Graph.filterEdges(mutable, () => { |
| 549 | mutate() |
| 550 | return true |
| 551 | }) |
| 552 | ] |
| 553 | |
| 554 | for (const transformation of transformations) { |
| 555 | assertGraphError(transformation, "Cannot mutate graph during a transformation") |
| 556 | } |
| 557 | }) |
| 558 | |
| 559 | it("guards read callbacks against nested mutation", () => { |
| 560 | const mutable = Graph.beginMutation(directed(["A", "B"], [[0, 1, 1]])) |
| 561 | const mutate = () => Graph.addNode(mutable, "C") |
| 562 | const operations: ReadonlyArray<() => unknown> = [ |
| 563 | () => |
| 564 | Graph.findNode(mutable, () => { |
| 565 | Graph.findNode(mutable, () => false) |
| 566 | mutate() |
| 567 | return false |
| 568 | }), |
| 569 | () => Graph.findNodes(mutable, () => (mutate(), false)), |
| 570 | () => Graph.findEdge(mutable, () => (mutate(), false)), |
| 571 | () => Graph.findEdges(mutable, () => (mutate(), false)), |
| 572 | () => Graph.toGraphViz(mutable, { edgeLabel: (edge) => (mutate(), String(edge)) }), |
| 573 | () => Graph.toMermaid(mutable, { nodeShape: () => (mutate(), "rectangle") }), |
| 574 | () => Graph.maximumFlow(mutable, { source: 0, target: 1, capacity: (edge) => (mutate(), edge) }), |
| 575 | () => Graph.minimumCut(mutable, { source: 0, target: 1, capacity: (edge) => (mutate(), edge) }), |
| 576 | () => Graph.dijkstra(mutable, { source: 0, target: 1, cost: (edge) => (mutate(), edge) }), |
| 577 | () => Graph.floydWarshall(mutable, (edge) => (mutate(), edge)), |
| 578 | () => Graph.astar(mutable, { source: 0, target: 1, cost: (edge) => (mutate(), edge), heuristic: () => 0 }), |
| 579 | () => Graph.astar(mutable, { source: 0, target: 1, cost: (edge) => edge, heuristic: () => (mutate(), 0) }), |
| 580 | () => Graph.bellmanFord(mutable, { source: 0, target: 1, cost: (edge) => (mutate(), edge) }), |
| 581 | () => |
| 582 | Array.from(Graph.allShortestPaths(mutable, { |
| 583 | source: 0, |
| 584 | target: 1, |
| 585 | cost: (edge) => (mutate(), edge) |
| 586 | })), |
| 587 | () => Array.from(Graph.dfs(mutable, { start: [0] }).visit(() => mutate())), |
| 588 | () => Array.from(Graph.nodes(mutable).visit(() => mutate())), |
| 589 | () => Array.from(Graph.edges(mutable).visit(() => mutate())), |
| 590 | () => Array.from(Graph.externals(mutable).visit(() => mutate())) |
| 591 | ] |
| 592 | |
| 593 | for (const operation of operations) { |
| 594 | assertGraphError(operation, "Cannot mutate graph during a transformation") |
| 595 | } |
| 596 | |
| 597 | const undirectedMutable = Graph.beginMutation(undirected(["A", "B"], [[0, 1, 1]])) |
| 598 | assertGraphError(() => |
| 599 | Graph.minimumSpanningForest(undirectedMutable, (edge) => { |
| 600 | Graph.addNode(undirectedMutable, "C") |
| 601 | return edge |
| 602 | }), "Cannot mutate graph during a transformation") |
| 603 | }) |
| 604 | }) |
| 605 | |
| 606 | describe("node operations", () => { |
| 607 | it("allocates stable indexes and supports lookup, membership, and count", () => { |
| 608 | const mutable = Graph.beginMutation(Graph.directed<string | undefined, never>()) |
| 609 | assert.strictEqual(Graph.addNode(mutable, undefined), 0) |
| 610 | assert.strictEqual(Graph.addNode(mutable, "B"), 1) |
| 611 | |
| 612 | assert.strictEqual(Graph.nodeCount(mutable), 2) |
| 613 | assert.strictEqual(Graph.hasNode(mutable, 0), true) |
| 614 | assert.strictEqual(Graph.hasNode(mutable, 2), false) |
| 615 | assert.deepStrictEqual(Graph.getNode(mutable, 0), Option.some(undefined)) |
| 616 | assert.deepStrictEqual(Graph.getNode(0)(mutable), Option.some(undefined)) |
| 617 | assert.deepStrictEqual(Graph.getNode(mutable, 2), Option.none()) |
| 618 | }) |
| 619 | |
| 620 | it("updates existing payloads and ignores missing indexes", () => { |
| 621 | const mutable = Graph.beginMutation(directed<string | undefined, never>([undefined, "B"], [])) |
| 622 | Graph.updateNode(mutable, 0, () => "A") |
| 623 | Graph.updateNode(mutable, 1, () => undefined) |
| 624 | Graph.updateNode(mutable, 99, () => "missing") |
| 625 | |
| 626 | assert.deepStrictEqual(Array.from(mutable), [[0, "A"], [1, undefined]]) |
| 627 | }) |
| 628 | |
| 629 | it("finds the first and all matching nodes in graph order", () => { |
| 630 | const graph = directed<string | undefined, never>([undefined, "B", undefined], []) |
| 631 | |
| 632 | assert.deepStrictEqual(Graph.findNode(graph, (node) => node === undefined), Option.some(0)) |
| 633 | assert.deepStrictEqual(Graph.findNode((node: string | undefined) => node === "missing")(graph), Option.none()) |
| 634 | assert.deepStrictEqual(Graph.findNodes(graph, (node) => node === undefined), [0, 2]) |
| 635 | }) |
| 636 | }) |
| 637 | |
| 638 | describe("edge operations", () => { |
| 639 | it("allocates parallel edges and self-loops with exact stored orientation", () => { |
| 640 | const graph = Graph.undirected<string, string>((mutable) => { |
| 641 | Graph.addNode(mutable, "A") |
| 642 | Graph.addNode(mutable, "B") |
| 643 | assert.strictEqual(Graph.addEdge(mutable, 1, 0, "first"), 0) |
| 644 | assert.strictEqual(Graph.addEdge(mutable, 1, 0, "parallel"), 1) |
| 645 | assert.strictEqual(Graph.addEdge(mutable, 0, 0, "loop"), 2) |
| 646 | }) |
| 647 | |
| 648 | assertSnapshot(graph, { |
| 649 | type: "undirected", |
| 650 | nodes: [{ index: 0, data: "A" }, { index: 1, data: "B" }], |
| 651 | edges: [ |
| 652 | { index: 0, source: 1, target: 0, data: "first" }, |
| 653 | { index: 1, source: 1, target: 0, data: "parallel" }, |
| 654 | { index: 2, source: 0, target: 0, data: "loop" } |
| 655 | ] |
| 656 | }) |
| 657 | }) |
| 658 | |
| 659 | it("rejects missing edge endpoints", () => { |
| 660 | const mutable = Graph.beginMutation(directed<string, number>(["A"], [])) |
| 661 | assertGraphError(() => Graph.addEdge(mutable, 1, 0, 1), "Node 1 does not exist") |
| 662 | assertGraphError(() => Graph.addEdge(mutable, 0, 1, 1), "Node 1 does not exist") |
| 663 | }) |
| 664 | |
| 665 | it("gets and updates undefined edge data without exposing stored records", () => { |
| 666 | const mutable = Graph.beginMutation(directed<string, number | undefined>(["A", "B"], [[0, 1, undefined]])) |
| 667 | const fromGetter = Option.getOrThrow(Graph.getEdge(mutable, 0)) |
| 668 | const fromWalker = Array.from(Graph.values(Graph.edges(mutable)))[0] |
| 669 | ;(fromGetter as { source: number; data: number | undefined }).source = 1 |
| 670 | ;(fromGetter as { source: number; data: number | undefined }).data = 1 |
| 671 | ;(fromWalker as { target: number; data: number | undefined }).target = 0 |
| 672 | ;(fromWalker as { target: number; data: number | undefined }).data = 1 |
| 673 | |
| 674 | assert.deepStrictEqual(Graph.getEdge(mutable, 0), Option.some({ source: 0, target: 1, data: undefined })) |
| 675 | assertSnapshot(mutable, { |
| 676 | type: "directed", |
| 677 | nodes: [{ index: 0, data: "A" }, { index: 1, data: "B" }], |
| 678 | edges: [{ index: 0, source: 0, target: 1, data: undefined }] |
| 679 | }) |
| 680 | assert.deepStrictEqual(Graph.neighbors(mutable, 0), [1]) |
| 681 | assert.deepStrictEqual(Graph.neighbors(mutable, 1), []) |
| 682 | |
| 683 | Graph.updateEdge(mutable, 0, () => 2) |
| 684 | Graph.updateEdge(mutable, 99, () => 3) |
| 685 | |
| 686 | assert.deepStrictEqual(Graph.getEdge(mutable, 0), Option.some({ source: 0, target: 1, data: 2 })) |
| 687 | assert.deepStrictEqual(Graph.getEdge(99)(mutable), Option.none()) |
| 688 | assertSnapshot(mutable, { |
| 689 | type: "directed", |
| 690 | nodes: [{ index: 0, data: "A" }, { index: 1, data: "B" }], |
| 691 | edges: [{ index: 0, source: 0, target: 1, data: 2 }] |
| 692 | }) |
| 693 | assert.deepStrictEqual(Graph.neighbors(mutable, 0), [1]) |
| 694 | }) |
| 695 | |
| 696 | it("removes parallel undirected edges and self-loops independently", () => { |
| 697 | const mutable = Graph.beginMutation(undirected(["A", "B"], [[1, 0, "first"], [0, 1, "second"], [1, 1, "loop"]])) |
| 698 | Graph.removeEdge(mutable, 0) |
| 699 | Graph.removeEdge(mutable, 2) |
| 700 | Graph.removeEdge(mutable, 99) |
| 701 | |
| 702 | assertSnapshot(mutable, { |
| 703 | type: "undirected", |
| 704 | nodes: [{ index: 0, data: "A" }, { index: 1, data: "B" }], |
| 705 | edges: [{ index: 1, source: 0, target: 1, data: "second" }] |
| 706 | }) |
| 707 | assert.deepStrictEqual(Graph.neighbors(mutable, 0), [1]) |
| 708 | assert.deepStrictEqual(Graph.neighbors(mutable, 1), [0]) |
| 709 | }) |
| 710 | |
| 711 | it("removes undirected nodes with reversed edges, parallel edges, and self-loops", () => { |
| 712 | const mutable = Graph.beginMutation(undirected(["A", "B", "C"], [ |
| 713 | [1, 0, "reverse"], |
| 714 | [0, 1, "parallel"], |
| 715 | [1, 1, "loop"], |
| 716 | [2, 0, "keep"] |
| 717 | ])) |
| 718 | Graph.removeNode(mutable, 1) |
| 719 | |
| 720 | assertSnapshot(mutable, { |
| 721 | type: "undirected", |
| 722 | nodes: [{ index: 0, data: "A" }, { index: 2, data: "C" }], |
| 723 | edges: [{ index: 3, source: 2, target: 0, data: "keep" }] |
| 724 | }) |
| 725 | }) |
| 726 | |
| 727 | it("collects graph-backed iterables before bulk removal", () => { |
| 728 | const edges = Graph.beginMutation(directed(["A", "B"], [[0, 1, 1], [1, 0, 2]])) |
| 729 | Graph.removeEdges(edges, Graph.indices(Graph.edges(edges))) |
| 730 | assert.strictEqual(Graph.edgeCount(edges), 0) |
| 731 | |
| 732 | const nodes = Graph.beginMutation(directed<string, never>(["A", "B"], [])) |
| 733 | Graph.removeNodes(nodes, Graph.indices(Graph.nodes(nodes))) |
| 734 | assert.strictEqual(Graph.nodeCount(nodes), 0) |
| 735 | }) |
| 736 | |
| 737 | it("keeps caches fresh when bulk-removal iterables query the graph", () => { |
| 738 | const edges = Graph.beginMutation(directed(["A", "B"], [[0, 1, 1]])) |
| 739 | Graph.removeEdges(edges, { |
| 740 | *[Symbol.iterator]() { |
| 741 | assert.strictEqual(Graph.hasPath(edges, 0, 1), true) |
| 742 | yield 0 |
| 743 | } |
| 744 | }) |
| 745 | assert.strictEqual(Graph.hasPath(edges, 0, 1), false) |
| 746 | |
| 747 | const nodes = Graph.beginMutation(directed(["A", "B"], [[0, 1, 1], [1, 0, 2]])) |
| 748 | Graph.removeNodes(nodes, { |
| 749 | *[Symbol.iterator]() { |
| 750 | assert.strictEqual(Graph.isAcyclic(nodes), false) |
| 751 | yield 1 |
| 752 | } |
| 753 | }) |
| 754 | assert.strictEqual(Graph.isAcyclic(nodes), true) |
| 755 | }) |
| 756 | |
| 757 | it("rejects finalization from bulk-removal iterables", () => { |
| 758 | const mutable = Graph.beginMutation(directed(["A", "B"], [[0, 1, 1]])) |
| 759 | assertGraphError(() => |
| 760 | Graph.removeEdges(mutable, { |
| 761 | *[Symbol.iterator]() { |
| 762 | Graph.endMutation(mutable) |
| 763 | yield 0 |
| 764 | } |
| 765 | }), "Cannot mutate graph during a transformation") |
| 766 | assert.strictEqual(mutable.mutable, true) |
| 767 | assert.strictEqual(Graph.edgeCount(mutable), 1) |
| 768 | }) |
| 769 | }) |
| 770 | |
| 771 | describe("transformations", () => { |
| 772 | it("maps nodes and edges while preserving indexes and structure", () => { |
| 773 | const mutable = Graph.beginMutation(directed(["a", "b"], [[0, 1, 2]])) |
| 774 | Graph.mapNodes(mutable, (node) => node.toUpperCase()) |
| 775 | Graph.mapEdges(mutable, (edge) => edge * 3) |
| 776 | |
| 777 | assertSnapshot(mutable, { |
| 778 | type: "directed", |
| 779 | nodes: [{ index: 0, data: "A" }, { index: 1, data: "B" }], |
| 780 | edges: [{ index: 0, source: 0, target: 1, data: 6 }] |
| 781 | }) |
| 782 | }) |
| 783 | |
| 784 | it("filter-maps nodes and removes incident edges", () => { |
| 785 | const mutable = Graph.beginMutation(directed([1, 2, 3], [[0, 1, "remove"], [1, 2, "remove"], [0, 2, "keep"]])) |
| 786 | Graph.filterMapNodes(mutable, (node) => node === 2 ? Option.none() : Option.some(node * 10)) |
| 787 | |
| 788 | assertSnapshot(mutable, { |
| 789 | type: "directed", |
| 790 | nodes: [{ index: 0, data: 10 }, { index: 2, data: 30 }], |
| 791 | edges: [{ index: 2, source: 0, target: 2, data: "keep" }] |
| 792 | }) |
| 793 | }) |
| 794 | |
| 795 | it("filter-maps edges without removing nodes", () => { |
| 796 | const mutable = Graph.beginMutation(directed(["A", "B", "C"], [[0, 1, 1], [1, 2, 2], [2, 0, 3]])) |
| 797 | Graph.filterMapEdges(mutable, (edge) => edge % 2 === 0 ? Option.none() : Option.some(edge * 10)) |
| 798 | |
| 799 | assertSnapshot(mutable, { |
| 800 | type: "directed", |
| 801 | nodes: [{ index: 0, data: "A" }, { index: 1, data: "B" }, { index: 2, data: "C" }], |
| 802 | edges: [{ index: 0, source: 0, target: 1, data: 10 }, { index: 2, source: 2, target: 0, data: 30 }] |
| 803 | }) |
| 804 | }) |
| 805 | |
| 806 | it("filters nodes and removes their incident edges", () => { |
| 807 | const nodes = Graph.beginMutation(directed(["A", "B", "C"], [[0, 1, 1], [1, 2, 2], [0, 2, 3]])) |
| 808 | Graph.filterNodes(nodes, (node) => node !== "B") |
| 809 | assertSnapshot(nodes, { |
| 810 | type: "directed", |
| 811 | nodes: [{ index: 0, data: "A" }, { index: 2, data: "C" }], |
| 812 | edges: [{ index: 2, source: 0, target: 2, data: 3 }] |
| 813 | }) |
| 814 | }) |
| 815 | |
| 816 | it("filters edges without removing nodes", () => { |
| 817 | const edges = Graph.beginMutation(directed(["A", "B", "C"], [[0, 1, 1], [1, 2, 2], [0, 2, 3]])) |
| 818 | Graph.filterEdges(edges, (edge) => edge % 2 === 1) |
| 819 | assertSnapshot(edges, { |
| 820 | type: "directed", |
| 821 | nodes: [{ index: 0, data: "A" }, { index: 1, data: "B" }, { index: 2, data: "C" }], |
| 822 | edges: [{ index: 0, source: 0, target: 1, data: 1 }, { index: 2, source: 0, target: 2, data: 3 }] |
| 823 | }) |
| 824 | }) |
| 825 | |
| 826 | it("exposes earlier bulk writes to later callbacks", () => { |
| 827 | const nodes = Graph.beginMutation(directed<string, never>(["a", "b"], [])) |
| 828 | const nodeStates: Array<Array<string>> = [] |
| 829 | Graph.mapNodes(nodes, (node) => { |
| 830 | nodeStates.push(Array.from(Graph.values(Graph.nodes(nodes)))) |
| 831 | return node.toUpperCase() |
| 832 | }) |
| 833 | assert.deepStrictEqual(nodeStates, [["a", "b"], ["A", "b"]]) |
| 834 | |
| 835 | const edges = Graph.beginMutation(directed(["A", "B", "C"], [[0, 1, 1], [1, 2, 2]])) |
| 836 | const edgeStates: Array<Array<number>> = [] |
| 837 | Graph.mapEdges(edges, (edge) => { |
| 838 | edgeStates.push(Array.from(Graph.values(Graph.edges(edges)), (value) => value.data)) |
| 839 | return edge * 2 |
| 840 | }) |
| 841 | assert.deepStrictEqual(edgeStates, [[1, 2], [2, 2]]) |
| 842 | }) |
| 843 | |
| 844 | it("publishes updated callback values to subsequent graph reads", () => { |
| 845 | const nodes = Graph.beginMutation(directed<string, never>(["old"], [])) |
| 846 | Graph.updateNode(nodes, 0, () => { |
| 847 | assert.deepStrictEqual(Array.from(Graph.values(Graph.bfs(nodes, { start: [0] }))), ["old"]) |
| 848 | return "new" |
| 849 | }) |
| 850 | assert.deepStrictEqual(Array.from(Graph.values(Graph.bfs(nodes, { start: [0] }))), ["new"]) |
| 851 | |
| 852 | const edges = Graph.beginMutation(directed(["source", "target"], [[0, 1, 1]])) |
| 853 | Graph.updateEdge(edges, 0, () => { |
| 854 | assert.deepStrictEqual(Array.from(Graph.simplePaths(edges, { source: 0, target: 1 }))[0].costs, [1]) |
| 855 | return 2 |
| 856 | }) |
| 857 | assert.deepStrictEqual(Array.from(Graph.simplePaths(edges, { source: 0, target: 1 }))[0].costs, [2]) |
| 858 | }) |
| 859 | |
| 860 | it("reverses directed edges and leaves undirected stored orientation unchanged", () => { |
| 861 | const directedMutable = Graph.beginMutation(directed(["A", "B", "C"], [[0, 1, 1], [1, 2, 2]])) |
| 862 | Graph.reverse(directedMutable) |
| 863 | Graph.addEdge(directedMutable, 0, 1, 3) |
| 864 | assert.deepStrictEqual(Graph.toSnapshot(directedMutable).edges, [ |
| 865 | { index: 0, source: 1, target: 0, data: 1 }, |
| 866 | { index: 1, source: 2, target: 1, data: 2 }, |
| 867 | { index: 2, source: 0, target: 1, data: 3 } |
| 868 | ]) |
| 869 | assert.deepStrictEqual(Graph.neighbors(directedMutable, 2), [1]) |
| 870 | assert.strictEqual(Graph.hasEdge(directedMutable, 1, 0), true) |
| 871 | assert.strictEqual(Graph.hasEdge(directedMutable, 0, 1), true) |
| 872 | |
| 873 | const undirectedMutable = Graph.beginMutation(undirected(["A", "B"], [[1, 0, 1]])) |
| 874 | Graph.reverse(undirectedMutable) |
| 875 | assert.deepStrictEqual(Graph.toSnapshot(undirectedMutable).edges, [{ index: 0, source: 1, target: 0, data: 1 }]) |
| 876 | }) |
| 877 | }) |
| 878 | |
| 879 | describe("set operations", () => { |
| 880 | type Node = { readonly id: string; readonly label: string } |
| 881 | const left = () => |
| 882 | directed<Node, string>( |
| 883 | [{ id: "a", label: "A1" }, { id: "b", label: "B1" }, { id: "c", label: "C1" }], |
| 884 | [[0, 1, "left"], [1, 2, "shared"]] |
| 885 | ) |
| 886 | const right = () => |
| 887 | directed<Node, string>( |
| 888 | [{ id: "b", label: "B2" }, { id: "c", label: "C2" }, { id: "d", label: "D2" }], |
| 889 | [[0, 1, "shared"], [1, 2, "right"]] |
| 890 | ) |
| 891 | const identity = { nodeIdentity: (node: Node) => node.id } |
| 892 | const semantic = (graph: Graph.Graph<Node, string>) => { |
| 893 | const nodes = new Map(Array.from(graph, ([index, node]) => [index, node])) |
| 894 | return { |
| 895 | nodes: Array.from(nodes.values(), (node) => `${node.id}:${node.label}`).sort(), |
| 896 | edges: Array.from( |
| 897 | Graph.values(Graph.edges(graph)), |
| 898 | (edge) => `${nodes.get(edge.source)!.id}->${nodes.get(edge.target)!.id}:${edge.data}` |
| 899 | ).sort() |
| 900 | } |
| 901 | } |
| 902 | |
| 903 | it("composes, intersects, differs, and symmetrically differs by projected identity", () => { |
| 904 | const composed = { |
| 905 | nodes: ["a:A1", "b:B2", "c:C2", "d:D2"], |
| 906 | edges: ["a->b:left", "b->c:shared", "c->d:right"] |
| 907 | } |
| 908 | const intersected = { |
| 909 | nodes: ["b:B1", "c:C1"], |
| 910 | edges: ["b->c:shared"] |
| 911 | } |
| 912 | const differed = { |
| 913 | nodes: ["a:A1", "b:B1", "c:C1"], |
| 914 | edges: ["a->b:left"] |
| 915 | } |
| 916 | const symmetric = { |
| 917 | nodes: ["a:A1", "b:B2", "c:C2", "d:D2"], |
| 918 | edges: ["a->b:left", "c->d:right"] |
| 919 | } |
| 920 | assert.deepStrictEqual(semantic(Graph.compose(left(), right(), identity)), composed) |
| 921 | assert.deepStrictEqual(semantic(Graph.compose(right(), identity)(left())), composed) |
| 922 | assert.deepStrictEqual(semantic(Graph.intersection(left(), right(), identity)), intersected) |
| 923 | assert.deepStrictEqual(semantic(Graph.intersection(right(), identity)(left())), intersected) |
| 924 | assert.deepStrictEqual(semantic(Graph.difference(left(), right(), identity)), differed) |
| 925 | assert.deepStrictEqual(semantic(Graph.difference(right(), identity)(left())), differed) |
| 926 | assert.deepStrictEqual(semantic(Graph.symmetricDifference(left(), right(), identity)), symmetric) |
| 927 | assert.deepStrictEqual(semantic(Graph.symmetricDifference(right(), identity)(left())), symmetric) |
| 928 | }) |
| 929 | |
| 930 | it("supports Effect Equal and Hash node identities", () => { |
| 931 | class NodeKey implements Equal.Equal { |
| 932 | constructor(readonly id: string) {} |
| 933 | [Equal.symbol](that: Equal.Equal): boolean { |
| 934 | return that instanceof NodeKey && this.id === that.id |
| 935 | } |
| 936 | [Hash.symbol](): number { |
| 937 | return Hash.string(this.id) |
| 938 | } |
| 939 | } |
| 940 | |
| 941 | const result = Graph.compose(left(), right(), { nodeIdentity: (node) => new NodeKey(node.id) }) |
| 942 | assert.deepStrictEqual(semantic(result), { |
| 943 | nodes: ["a:A1", "b:B2", "c:C2", "d:D2"], |
| 944 | edges: ["a->b:left", "b->c:shared", "c->d:right"] |
| 945 | }) |
| 946 | }) |
| 947 | |
| 948 | it("coalesces duplicate identities to the last payload and redirects edges", () => { |
| 949 | const graph = directed<Node, string>([{ id: "a", label: "first" }, { id: "a", label: "last" }], [[ |
| 950 | 0, |
| 951 | 1, |
| 952 | "edge" |
| 953 | ]]) |
| 954 | const result = Graph.compose(graph, Graph.directed<Node, string>(), identity) |
| 955 | const edge = Array.from(Graph.values(Graph.edges(result)))[0] |
| 956 | |
| 957 | assert.deepStrictEqual(Array.from(Graph.values(Graph.nodes(result))), [{ id: "a", label: "last" }]) |
| 958 | assert.strictEqual(edge.source, edge.target) |
| 959 | }) |
| 960 | |
| 961 | it("uses right edge payloads for custom-identity compose and intersection", () => { |
| 962 | type Edge = { readonly id: string; readonly label: string } |
| 963 | const left = directed<string, Edge>(["A", "B"], [[0, 1, { id: "shared", label: "left" }]]) |
| 964 | const right = directed<string, Edge>(["A", "B"], [[0, 1, { id: "shared", label: "right" }]]) |
| 965 | const options = { edgeIdentity: (edge: Edge) => edge.id } |
| 966 | |
| 967 | assert.strictEqual( |
| 968 | Array.from(Graph.values(Graph.edges(Graph.compose(left, right, options))))[0].data.label, |
| 969 | "right" |
| 970 | ) |
| 971 | assert.strictEqual( |
| 972 | Array.from(Graph.values(Graph.edges(Graph.intersection(left, right, options))))[0].data.label, |
| 973 | "right" |
| 974 | ) |
| 975 | }) |
| 976 | |
| 977 | it("includes edge data in the default edge identity", () => { |
| 978 | const first = directed(["A", "B"], [[0, 1, "left"]]) |
| 979 | const second = directed(["A", "B"], [[0, 1, "right"]]) |
| 980 | |
| 981 | assert.strictEqual(Graph.edgeCount(Graph.compose(first, second)), 2) |
| 982 | assert.strictEqual(Graph.edgeCount(Graph.intersection(first, second)), 0) |
| 983 | assert.strictEqual(Graph.edgeCount(Graph.difference(first, second)), 1) |
| 984 | assert.strictEqual(Graph.edgeCount(Graph.symmetricDifference(first, second)), 2) |
| 985 | }) |
| 986 | |
| 987 | it("uses undefined node data as the default node identity", () => { |
| 988 | assert.strictEqual( |
| 989 | Graph.nodeCount(Graph.compose(directed<undefined, never>([undefined], []), directed([undefined], []))), |
| 990 | 1 |
| 991 | ) |
| 992 | }) |
| 993 | |
| 994 | it("treats equal parallel edges as set members while difference preserves unmatched occurrences", () => { |
| 995 | const parallel = directed(["A", "B"], [[0, 1, "same"], [0, 1, "same"]]) |
| 996 | const one = directed(["A", "B"], [[0, 1, "same"]]) |
| 997 | const empty = Graph.directed<string, string>() |
| 998 | |
| 999 | assert.strictEqual(Graph.edgeCount(Graph.compose(parallel, empty)), 1) |
| 1000 | assert.strictEqual(Graph.edgeCount(Graph.intersection(parallel, one)), 1) |
| 1001 | assert.strictEqual(Graph.edgeCount(Graph.difference(parallel, empty)), 2) |
| 1002 | assert.strictEqual(Graph.edgeCount(Graph.difference(parallel, one)), 0) |
| 1003 | assert.strictEqual(Graph.edgeCount(Graph.symmetricDifference(parallel, empty)), 1) |
| 1004 | }) |
| 1005 | |
| 1006 | it("matches undirected identities independent of stored orientation", () => { |
| 1007 | const first = undirected(["A", "B"], [[0, 1, "same"]]) |
| 1008 | const second = undirected(["B", "A"], [[0, 1, "same"]]) |
| 1009 | assert.strictEqual(Graph.edgeCount(Graph.intersection(first, second)), 1) |
| 1010 | assert.strictEqual(Graph.edgeCount(Graph.difference(first, second)), 0) |
| 1011 | }) |
| 1012 | |
| 1013 | it("rejects runtime kind mismatches for every binary set operation", () => { |
| 1014 | const first = Graph.directed<string, string>() as Graph.Graph<string, string, Graph.Kind> |
| 1015 | const second = Graph.undirected<string, string>() as Graph.Graph<string, string, Graph.Kind> |
| 1016 | const operations: ReadonlyArray<() => unknown> = [ |
| 1017 | () => Graph.compose(first, second), |
| 1018 | () => Graph.intersection(first, second), |
| 1019 | () => Graph.difference(first, second), |
| 1020 | () => Graph.symmetricDifference(first, second), |
| 1021 | () => Graph.sum(first, second) |
| 1022 | ] |
| 1023 | for (const operation of operations) { |
| 1024 | assertGraphError(operation, "Cannot combine directed and undirected graphs") |
| 1025 | } |
| 1026 | }) |
| 1027 | |
| 1028 | it("builds directed and undirected complements without self-loops", () => { |
| 1029 | assertSnapshot(Graph.complement(directed(["A", "B"], [[0, 1, "existing"]]), (a, b) => `${a}-${b}`), { |
| 1030 | type: "directed", |
| 1031 | nodes: [{ index: 0, data: "A" }, { index: 1, data: "B" }], |
| 1032 | edges: [{ index: 0, source: 1, target: 0, data: "B-A" }] |
| 1033 | }) |
| 1034 | assertSnapshot(Graph.complement(undirected(["A", "B", "C"], [[0, 1, "existing"]]), (a, b) => `${a}-${b}`), { |
| 1035 | type: "undirected", |
| 1036 | nodes: [{ index: 0, data: "A" }, { index: 1, data: "B" }, { index: 2, data: "C" }], |
| 1037 | edges: [{ index: 0, source: 0, target: 2, data: "A-C" }, { index: 1, source: 1, target: 2, data: "B-C" }] |
| 1038 | }) |
| 1039 | }) |
| 1040 | |
| 1041 | it("returns induced neighborhoods and validates radius", () => { |
| 1042 | const graph = directed(["A", "B", "C", "D"], [[0, 1, "AB"], [1, 2, "BC"], [2, 1, "CB"], [2, 3, "CD"]]) |
| 1043 | assertSnapshot(Graph.neighborhood(graph, 1, { radius: 1 }), { |
| 1044 | type: "directed", |
| 1045 | nodes: [{ index: 0, data: "B" }, { index: 1, data: "C" }], |
| 1046 | edges: [{ index: 0, source: 0, target: 1, data: "BC" }, { index: 1, source: 1, target: 0, data: "CB" }] |
| 1047 | }) |
| 1048 | assertSnapshot(Graph.neighborhood(1, { radius: Infinity })(graph), { |
| 1049 | type: "directed", |
| 1050 | nodes: [{ index: 0, data: "B" }, { index: 1, data: "C" }, { index: 2, data: "D" }], |
| 1051 | edges: [ |
| 1052 | { index: 0, source: 0, target: 1, data: "BC" }, |
| 1053 | { index: 1, source: 1, target: 0, data: "CB" }, |
| 1054 | { index: 2, source: 1, target: 2, data: "CD" } |
| 1055 | ] |
| 1056 | }) |
| 1057 | for (const radius of [NaN, -1, 0.5]) { |
| 1058 | assertGraphError( |
| 1059 | () => Graph.neighborhood(graph, 1, { radius }), |
| 1060 | "Traversal radius must be a non-negative integer or Infinity" |
| 1061 | ) |
| 1062 | } |
| 1063 | }) |
| 1064 | |
| 1065 | it("can ignore edge direction when selecting a neighborhood", () => { |
| 1066 | const graph = directed(["A", "B", "C"], [[0, 1, "AB"], [0, 2, "AC"]]) |
| 1067 | assertSnapshot(Graph.neighborhood(graph, 1, { radius: 2, direction: "undirected" }), { |
| 1068 | type: "directed", |
| 1069 | nodes: [{ index: 0, data: "B" }, { index: 1, data: "A" }, { index: 2, data: "C" }], |
| 1070 | edges: [{ index: 0, source: 1, target: 0, data: "AB" }, { index: 1, source: 1, target: 2, data: "AC" }] |
| 1071 | }) |
| 1072 | }) |
| 1073 | |
| 1074 | it("preserves sparse indexes in induced subgraphs and rejects missing nodes", () => { |
| 1075 | const graph = Graph.fromSnapshot({ |
| 1076 | type: "directed", |
| 1077 | nodes: [{ index: 2, data: "A" }, { index: 5, data: "B" }, { index: 9, data: "C" }], |
| 1078 | edges: [ |
| 1079 | { index: 3, source: 2, target: 5, data: "AB" }, |
| 1080 | { index: 7, source: 5, target: 9, data: "BC" }, |
| 1081 | { index: 11, source: 5, target: 5, data: "loop" } |
| 1082 | ] |
| 1083 | }) |
| 1084 | assertSnapshot(Graph.inducedSubgraph([9, 5, 5])(graph), { |
| 1085 | type: "directed", |
| 1086 | nodes: [{ index: 5, data: "B" }, { index: 9, data: "C" }], |
| 1087 | edges: [{ index: 7, source: 5, target: 9, data: "BC" }, { index: 11, source: 5, target: 5, data: "loop" }] |
| 1088 | }) |
| 1089 | assertGraphError(() => Graph.inducedSubgraph(graph, [2, 4]), "Node 4 does not exist") |
| 1090 | }) |
| 1091 | |
| 1092 | it("preserves graph kind for empty induced subgraphs", () => { |
| 1093 | assertSnapshot(Graph.inducedSubgraph(Graph.undirected<string, never>(), []), { |
| 1094 | type: "undirected", |
| 1095 | nodes: [], |
| 1096 | edges: [] |
| 1097 | }) |
| 1098 | }) |
| 1099 | |
| 1100 | it("keeps equal nodes and their edges disjoint in sums", () => { |
| 1101 | const expected = { |
| 1102 | type: "directed", |
| 1103 | nodes: [ |
| 1104 | { index: 0, data: "A" }, |
| 1105 | { index: 1, data: "B" }, |
| 1106 | { index: 2, data: "A" }, |
| 1107 | { index: 3, data: "B" } |
| 1108 | ], |
| 1109 | edges: [ |
| 1110 | { index: 0, source: 0, target: 1, data: "left" }, |
| 1111 | { index: 1, source: 2, target: 3, data: "right" } |
| 1112 | ] |
| 1113 | } as const |
| 1114 | const first = directed(["A", "B"], [[0, 1, "left"]]) |
| 1115 | const second = directed(["A", "B"], [[0, 1, "right"]]) |
| 1116 | assertSnapshot(Graph.sum(first, second), expected) |
| 1117 | assertSnapshot(Graph.sum(second)(first), expected) |
| 1118 | }) |
| 1119 | }) |
| 1120 | |
| 1121 | describe("queries", () => { |
| 1122 | const graph = directed(["A", "B", "C"], [ |
| 1123 | [0, 1, "first"], |
| 1124 | [0, 1, "parallel"], |
| 1125 | [2, 0, "incoming"], |
| 1126 | [0, 0, "loop"], |
| 1127 | [0, 2, "last"] |
| 1128 | ]) |
| 1129 | |
| 1130 | it("reports exact edge order, multiplicity, and directed degrees", () => { |
| 1131 | assert.deepStrictEqual(Graph.incidentEdges(graph, 0), [0, 1, 2, 3, 4]) |
| 1132 | assert.deepStrictEqual(Graph.outgoingEdges(graph, 0), [0, 1, 3, 4]) |
| 1133 | assert.deepStrictEqual(Graph.incomingEdges(graph, 0), [2, 3]) |
| 1134 | assert.deepStrictEqual(Graph.edgesBetween(graph, 0, 1), [0, 1]) |
| 1135 | assert.deepStrictEqual(Graph.edgesBetween(graph, 1, 0), []) |
| 1136 | assert.strictEqual(Graph.outDegree(graph, 0), 4) |
| 1137 | assert.strictEqual(Graph.inDegree(graph, 0), 2) |
| 1138 | }) |
| 1139 | |
| 1140 | it("deduplicates neighbors in first-edge occurrence order", () => { |
| 1141 | assert.deepStrictEqual(Graph.neighbors(graph, 0), [1, 0, 2]) |
| 1142 | assert.deepStrictEqual(Graph.successors(0)(graph), [1, 0, 2]) |
| 1143 | assert.deepStrictEqual(Graph.predecessors(graph, 0), [2, 0]) |
| 1144 | assert.deepStrictEqual(Graph.neighborsDirected(graph, 0, "outgoing"), [1, 0, 2]) |
| 1145 | assert.deepStrictEqual(Graph.successors(graph, 0.5), []) |
| 1146 | }) |
| 1147 | |
| 1148 | it("deduplicates high-degree neighbors in first-edge occurrence order", () => { |
| 1149 | const targets = Array.from({ length: 34 }, (_, i) => i + 1) |
| 1150 | const graph = directed([0, ...targets], [2, 1, ...targets, 1].map((target) => [0, target, null] as const)) |
| 1151 | assert.deepStrictEqual(Graph.neighbors(graph, 0), [2, 1, ...targets.slice(2)]) |
| 1152 | }) |
| 1153 | |
| 1154 | it("handles undirected orientation, self-loops, parallel edges, and degree", () => { |
| 1155 | const graph = undirected(["A", "B"], [[1, 0, 1], [0, 1, 2], [0, 0, 3]]) |
| 1156 | assert.deepStrictEqual(Graph.neighbors(graph, 0), [1, 0]) |
| 1157 | assert.deepStrictEqual(Graph.neighbors(graph, 1), [0]) |
| 1158 | assert.deepStrictEqual(Graph.incidentEdges(graph, 0), [0, 1, 2]) |
| 1159 | assert.deepStrictEqual(Graph.edgesBetween(graph, 0, 1), [0, 1]) |
| 1160 | assert.strictEqual(Graph.degree(graph, 0), 4) |
| 1161 | assert.strictEqual(Graph.hasEdge(graph, 0, 1), true) |
| 1162 | assert.strictEqual(Graph.hasEdge(graph, 1, 0), true) |
| 1163 | }) |
| 1164 | |
| 1165 | it("preserves edge order when merging directed incidence and scanning undirected adjacency", () => { |
| 1166 | const directedGraph = directed([0, 1, 2], [ |
| 1167 | [0, 1, "out-first"], |
| 1168 | [2, 0, "in-first"], |
| 1169 | [0, 0, "loop"], |
| 1170 | [0, 2, "out-last"], |
| 1171 | [1, 0, "in-last"] |
| 1172 | ]) |
| 1173 | assert.deepStrictEqual(Graph.incidentEdges(directedGraph, 0), [0, 1, 2, 3, 4]) |
| 1174 | assert.deepStrictEqual(Graph.edgesBetween(directedGraph, 0, 0), [2]) |
| 1175 | |
| 1176 | const undirectedGraph = undirected([0, 1, 2], [ |
| 1177 | [1, 0, "reverse"], |
| 1178 | [0, 0, "loop"], |
| 1179 | [0, 2, "forward"], |
| 1180 | [2, 0, "reverse-last"] |
| 1181 | ]) |
| 1182 | assert.deepStrictEqual(Graph.incidentEdges(undirectedGraph, 0), [0, 1, 2, 3]) |
| 1183 | assert.deepStrictEqual(Graph.edgesBetween(undirectedGraph, 0, 2), [2, 3]) |
| 1184 | assert.deepStrictEqual(Graph.edgesBetween(undirectedGraph, 2, 0), [2, 3]) |
| 1185 | }) |
| 1186 | |
| 1187 | it("reports directed edge membership without assuming symmetry", () => { |
| 1188 | const graph = directed(["A", "B", "C"], [[0, 1, 1]]) |
| 1189 | assert.strictEqual(Graph.hasEdge(graph, 0, 1), true) |
| 1190 | assert.strictEqual(Graph.hasEdge(graph, 1, 0), false) |
| 1191 | assert.strictEqual(Graph.hasEdge(graph, 0, 2), false) |
| 1192 | assert.strictEqual(Graph.hasEdge(graph, 99, 0), false) |
| 1193 | }) |
| 1194 | |
| 1195 | it("passes stored endpoints to edge finder predicates", () => { |
| 1196 | const graph = undirected(["A", "B", "C"], [[2, 0, "match"], [0, 1, "match"]]) |
| 1197 | const calls: Array<readonly [string, number, number]> = [] |
| 1198 | assert.deepStrictEqual( |
| 1199 | Graph.findEdge(graph, (data, source, target) => { |
| 1200 | calls.push([data, source, target]) |
| 1201 | return source === 0 |
| 1202 | }), |
| 1203 | Option.some(1) |
| 1204 | ) |
| 1205 | assert.deepStrictEqual(calls, [["match", 2, 0], ["match", 0, 1]]) |
| 1206 | assert.deepStrictEqual(Graph.findEdges(graph, (_, source, target) => source > target), [0]) |
| 1207 | }) |
| 1208 | |
| 1209 | it("finds undefined edge payloads", () => { |
| 1210 | const graph = directed<string, number | undefined>(["A", "B", "C"], [ |
| 1211 | [0, 1, undefined], |
| 1212 | [1, 2, 42], |
| 1213 | [2, 0, undefined] |
| 1214 | ]) |
| 1215 | assert.deepStrictEqual(Graph.findEdge(graph, (edge) => edge === undefined), Option.some(0)) |
| 1216 | assert.deepStrictEqual(Graph.findEdges(graph, (edge) => edge === undefined), [0, 2]) |
| 1217 | }) |
| 1218 | |
| 1219 | it("reports kind and missing-node errors consistently", () => { |
| 1220 | const one = directed<string, number>(["A"], []) |
| 1221 | const undirectedOne = undirected<string, number>(["A"], []) |
| 1222 | assertGraphError( |
| 1223 | () => Graph.degree(one as unknown as Graph.UndirectedGraph<string, number>, 0), |
| 1224 | "Cannot get degree of directed graph" |
| 1225 | ) |
| 1226 | assertGraphError( |
| 1227 | () => Graph.outgoingEdges(undirectedOne as unknown as Graph.DirectedGraph<string, number>, 0), |
| 1228 | "Cannot get outgoing edges of undirected graph" |
| 1229 | ) |
| 1230 | assertGraphError( |
| 1231 | () => Graph.incomingEdges(undirectedOne as unknown as Graph.DirectedGraph<string, number>, 0), |
| 1232 | "Cannot get incoming edges of undirected graph" |
| 1233 | ) |
| 1234 | assertGraphError( |
| 1235 | () => Graph.successors(undirectedOne as unknown as Graph.DirectedGraph<string, number>, 0), |
| 1236 | "Cannot get successors of undirected graph" |
| 1237 | ) |
| 1238 | assertGraphError(() => Graph.incidentEdges(one, 1), "Node 1 does not exist") |
| 1239 | assertGraphError(() => Graph.edgesBetween(one, 0, 1), "Node 1 does not exist") |
| 1240 | }) |
| 1241 | }) |
| 1242 | |
| 1243 | describe("serialization", () => { |
| 1244 | it("serializes representative directed and undirected GraphViz graphs exactly", () => { |
| 1245 | const directedGraph = directed(["A", "B"], [[0, 1, 1]]) |
| 1246 | const directedExpected = [ |
| 1247 | "digraph \"G\" {", |
| 1248 | " \"0\" [label=\"A\"];", |
| 1249 | " \"1\" [label=\"B\"];", |
| 1250 | " \"0\" -> \"1\" [label=\"1\"];", |
| 1251 | "}" |
| 1252 | ].join("\n") |
| 1253 | assert.strictEqual(Graph.toGraphViz(directedGraph), directedExpected) |
| 1254 | assert.strictEqual(Graph.toGraphViz()(directedGraph), directedExpected) |
| 1255 | assert.strictEqual( |
| 1256 | Graph.toGraphViz(undirected(["A", "B"], [[1, 0, "edge"]])), |
| 1257 | [ |
| 1258 | "graph \"G\" {", |
| 1259 | " \"0\" [label=\"A\"];", |
| 1260 | " \"1\" [label=\"B\"];", |
| 1261 | " \"1\" -- \"0\" [label=\"edge\"];", |
| 1262 | "}" |
| 1263 | ].join("\n") |
| 1264 | ) |
| 1265 | }) |
| 1266 | |
| 1267 | it("escapes GraphViz graph names and labels exactly", () => { |
| 1268 | const graph = directed([{ label: "C:\\new\n\"line\"" }, { label: "end" }], [[ |
| 1269 | 0, |
| 1270 | 1, |
| 1271 | { label: "edge\\path\n\"quoted\"" } |
| 1272 | ]]) |
| 1273 | assert.strictEqual( |
| 1274 | Graph.toGraphViz(graph, { |
| 1275 | graphName: "My \"Graph\"", |
| 1276 | nodeLabel: (node) => `node:${node.label}`, |
| 1277 | edgeLabel: (edge) => edge.label |
| 1278 | }), |
| 1279 | [ |
| 1280 | "digraph \"My \\\"Graph\\\"\" {", |
| 1281 | " \"0\" [label=\"node:C:\\\\new\\n\\\"line\\\"\"];", |
| 1282 | " \"1\" [label=\"node:end\"];", |
| 1283 | " \"0\" -> \"1\" [label=\"edge\\\\path\\n\\\"quoted\\\"\"];", |
| 1284 | "}" |
| 1285 | ].join("\n") |
| 1286 | ) |
| 1287 | }) |
| 1288 | |
| 1289 | it("serializes representative directed and undirected Mermaid graphs exactly", () => { |
| 1290 | const directedGraph = directed(["A", "B"], [[0, 1, "edge"]]) |
| 1291 | const directedExpected = [ |
| 1292 | "flowchart TD", |
| 1293 | " 0[\"A\"]", |
| 1294 | " 1[\"B\"]", |
| 1295 | " 0 -->|\"edge\"| 1" |
| 1296 | ].join("\n") |
| 1297 | assert.strictEqual(Graph.toMermaid(directedGraph), directedExpected) |
| 1298 | assert.strictEqual(Graph.toMermaid()(directedGraph), directedExpected) |
| 1299 | assert.strictEqual( |
| 1300 | Graph.toMermaid(undirected(["A", "B"], [[1, 0, ""]])), |
| 1301 | [ |
| 1302 | "graph TD", |
| 1303 | " 0[\"A\"]", |
| 1304 | " 1[\"B\"]", |
| 1305 | " 1 --- 0" |
| 1306 | ].join("\n") |
| 1307 | ) |
| 1308 | }) |
| 1309 | |
| 1310 | it("escapes Mermaid labels and applies direction, type, and custom labels", () => { |
| 1311 | const graph = directed([{ id: "#\"<>&[]{}()|\\" }, { id: "B\r\n2\r3\n4" }], [[0, 1, { weight: 2 }]]) |
| 1312 | const serialized = Graph.toMermaid(graph, { |
| 1313 | direction: "LR", |
| 1314 | diagramType: "graph", |
| 1315 | nodeLabel: (node) => node.id, |
| 1316 | edgeLabel: (edge) => `w(${edge.weight})` |
| 1317 | }) |
| 1318 | assert.strictEqual( |
| 1319 | serialized, |
| 1320 | [ |
| 1321 | "graph LR", |
| 1322 | " 0[\"#35;#quot;#lt;#gt;#amp;#91;#93;#123;#125;#40;#41;#124;#92;\"]", |
| 1323 | " 1[\"B<br/>2<br/>3<br/>4\"]", |
| 1324 | " 0 ---|\"w#40;2#41;\"| 1" |
| 1325 | ].join("\n") |
| 1326 | ) |
| 1327 | assert.strictEqual(serialized.includes("\r"), false) |
| 1328 | }) |
| 1329 | |
| 1330 | it("supports every Mermaid node shape", () => { |
| 1331 | const expected: ReadonlyArray<readonly [Graph.MermaidNodeShape, string]> = [ |
| 1332 | ["rectangle", "0[\"A\"]"], |
| 1333 | ["rounded", "0(\"A\")"], |
| 1334 | ["circle", "0((\"A\"))"], |
| 1335 | ["diamond", "0{\"A\"}"], |
| 1336 | ["hexagon", "0{{\"A\"}}"], |
| 1337 | ["stadium", "0([\"A\"])"], |
| 1338 | ["subroutine", "0[[\"A\"]]"], |
| 1339 | ["cylindrical", "0[(\"A\")]"] |
| 1340 | ] |
| 1341 | for (const [shape, node] of expected) { |
| 1342 | assert.strictEqual( |
| 1343 | Graph.toMermaid(directed<string, never>(["A"], []), { nodeShape: () => shape }), |
| 1344 | `flowchart TD\n ${node}` |
| 1345 | ) |
| 1346 | } |
| 1347 | }) |
| 1348 | }) |
| 1349 | |
| 1350 | describe("cycles and connectivity", () => { |
| 1351 | it("returns exact sparse cycle witnesses including self-loops and parallel edges", () => { |
| 1352 | const directedCycle = Graph.fromSnapshot({ |
| 1353 | type: "directed", |
| 1354 | nodes: [{ index: 2, data: "A" }, { index: 5, data: "B" }, { index: 9, data: "C" }], |
| 1355 | edges: [ |
| 1356 | { index: 3, source: 2, target: 5, data: 1 }, |
| 1357 | { index: 7, source: 5, target: 9, data: 1 }, |
| 1358 | { index: 11, source: 9, target: 2, data: 1 } |
| 1359 | ] |
| 1360 | }) |
| 1361 | assert.deepStrictEqual(Graph.findCycle(directedCycle), Option.some({ path: [2, 5, 9, 2], edges: [3, 7, 11] })) |
| 1362 | assert.deepStrictEqual(Graph.findCycle(undirected(["A"], [[0, 0, 1]])), Option.some({ path: [0, 0], edges: [0] })) |
| 1363 | assert.deepStrictEqual( |
| 1364 | Graph.findCycle(undirected(["A", "B"], [[0, 1, 1], [1, 0, 2]])), |
| 1365 | Option.some({ |
| 1366 | path: [0, 1, 0], |
| 1367 | edges: [0, 1] |
| 1368 | }) |
| 1369 | ) |
| 1370 | }) |
| 1371 | |
| 1372 | it("returns None for acyclic directed and reversed-storage undirected graphs", () => { |
| 1373 | assert.deepStrictEqual(Graph.findCycle(directed([0, 1, 2], [[0, 1, 1], [1, 2, 1]])), Option.none()) |
| 1374 | assert.deepStrictEqual(Graph.findCycle(undirected([0, 1, 2], [[0, 1, 1], [2, 1, 1]])), Option.none()) |
| 1375 | }) |
| 1376 | |
| 1377 | it("invalidates acyclic results after adding and removing a cycle edge", () => { |
| 1378 | const mutable = Graph.beginMutation(directed(["A", "B", "C"], [[0, 1, 1], [1, 2, 1]])) |
| 1379 | assert.strictEqual(Graph.isAcyclic(mutable), true) |
| 1380 | const cycle = Graph.addEdge(mutable, 2, 0, 1) |
| 1381 | assert.strictEqual(Graph.isAcyclic(mutable), false) |
| 1382 | Graph.removeEdge(mutable, cycle) |
| 1383 | assert.strictEqual(Graph.isAcyclic(mutable), true) |
| 1384 | }) |
| 1385 | |
| 1386 | it("handles undirected reversed orientation, self-loops, and parallel cycles", () => { |
| 1387 | assert.strictEqual(Graph.isAcyclic(undirected(["A", "B", "C"], [[0, 1, 1], [2, 1, 1]])), true) |
| 1388 | assert.strictEqual(Graph.isAcyclic(undirected(["A"], [[0, 0, 1]])), false) |
| 1389 | assert.strictEqual(Graph.isAcyclic(undirected(["A", "B"], [[0, 1, 1], [0, 1, 2]])), false) |
| 1390 | }) |
| 1391 | |
| 1392 | it("returns complete connected, weak, and strong component partitions", () => { |
| 1393 | const connected = undirected(["A", "B", "C", "D", "E"], [[0, 1, 1], [2, 3, 1]]) |
| 1394 | const directedGraph = directed(["A", "B", "C", "D", "E"], [[0, 1, 1], [1, 0, 1], [2, 1, 1], [3, 4, 1]]) |
| 1395 | |
| 1396 | assertComponents(Graph.connectedComponents(connected), [[0, 1], [2, 3], [4]]) |
| 1397 | assertComponents(Graph.weaklyConnectedComponents(directedGraph), [[0, 1, 2], [3, 4]]) |
| 1398 | assertComponents(Graph.stronglyConnectedComponents(directedGraph), [[0, 1], [2], [3], [4]]) |
| 1399 | assertComponents(Graph.connectedComponents(Graph.beginMutation(connected)), [[0, 1], [2, 3], [4]]) |
| 1400 | assertComponents(Graph.stronglyConnectedComponents(Graph.beginMutation(directedGraph)), [[0, 1], [2], [3], [4]]) |
| 1401 | }) |
| 1402 | |
| 1403 | it("computes reachability in outgoing, incoming, and undirected modes", () => { |
| 1404 | const graph = directed(["A", "B", "C", "D"], [[0, 1, 1], [1, 2, 1], [3, 1, 1]]) |
| 1405 | assert.deepStrictEqual(Array.from(Graph.unweightedDistances(graph, 0)), [[0, 0], [1, 1], [2, 2]]) |
| 1406 | assert.deepStrictEqual(Array.from(Graph.unweightedDistances(graph, 2, { direction: "incoming" })), [ |
| 1407 | [0, 2], |
| 1408 | [1, 1], |
| 1409 | [2, 0], |
| 1410 | [3, 2] |
| 1411 | ]) |
| 1412 | assert.deepStrictEqual(Array.from(Graph.unweightedDistances(graph, 0, { direction: "undirected" })), [ |
| 1413 | [0, 0], |
| 1414 | [1, 1], |
| 1415 | [2, 2], |
| 1416 | [3, 2] |
| 1417 | ]) |
| 1418 | assert.strictEqual(Graph.hasPath(graph, 0, 2), true) |
| 1419 | assert.strictEqual(Graph.hasPath(graph, 2, 0), false) |
| 1420 | assert.strictEqual(Graph.hasPath(2, 0, { direction: "incoming" })(graph), true) |
| 1421 | assert.strictEqual(Graph.hasPath(graph, 2, 3), false) |
| 1422 | assert.strictEqual(Graph.hasPath(graph, 2, 3, { direction: "undirected" }), true) |
| 1423 | }) |
| 1424 | |
| 1425 | it("updates connectivity results after mutable changes", () => { |
| 1426 | const mutable = Graph.beginMutation(directed(["A", "B", "C"], [[0, 1, 1]])) |
| 1427 | assertComponents(Graph.weaklyConnectedComponents(mutable), [[0, 1], [2]]) |
| 1428 | assert.strictEqual(Graph.hasPath(mutable, 0, 2), false) |
| 1429 | Graph.addEdge(mutable, 1, 2, 1) |
| 1430 | assertComponents(Graph.weaklyConnectedComponents(mutable), [[0, 1, 2]]) |
| 1431 | assert.strictEqual(Graph.hasPath(mutable, 0, 2), true) |
| 1432 | }) |
| 1433 | |
| 1434 | it("checks connected, weak, strong, and tree predicates including empty graphs", () => { |
| 1435 | const tree = undirected(["A", "B", "C"], [[0, 1, 1], [1, 2, 1]]) |
| 1436 | const disconnected = undirected<string, number>(["A", "B"], []) |
| 1437 | const weak = directed(["A", "B", "C"], [[0, 1, 1], [1, 2, 1]]) |
| 1438 | const weaklyDisconnected = directed<string, number>(["A", "B"], []) |
| 1439 | const strong = Graph.mutate(weak, (mutable) => { |
| 1440 | Graph.addEdge(mutable, 2, 0, 1) |
| 1441 | }) |
| 1442 | assert.strictEqual(Graph.isConnected(tree), true) |
| 1443 | assert.strictEqual(Graph.isConnected(disconnected), false) |
| 1444 | assert.strictEqual(Graph.isTree(tree), true) |
| 1445 | assert.strictEqual(Graph.isWeaklyConnected(weak), true) |
| 1446 | assert.strictEqual(Graph.isWeaklyConnected(weaklyDisconnected), false) |
| 1447 | assert.strictEqual(Graph.isStronglyConnected(weak), false) |
| 1448 | assert.strictEqual(Graph.isStronglyConnected(strong), true) |
| 1449 | assert.strictEqual(Graph.isConnected(Graph.undirected()), true) |
| 1450 | assert.strictEqual(Graph.isTree(Graph.undirected()), false) |
| 1451 | }) |
| 1452 | |
| 1453 | it("rejects runtime connectivity kind mismatches and missing endpoints", () => { |
| 1454 | const directedGraph = Graph.directed() as unknown as Graph.Graph<never, never, Graph.Kind> |
| 1455 | const undirectedGraph = Graph.undirected() as unknown as Graph.Graph<never, never, Graph.Kind> |
| 1456 | assertGraphError( |
| 1457 | () => Graph.connectedComponents(directedGraph as Graph.UndirectedGraph<never, never>), |
| 1458 | "Cannot find connected components of directed graph" |
| 1459 | ) |
| 1460 | assertGraphError( |
| 1461 | () => Graph.weaklyConnectedComponents(undirectedGraph as Graph.DirectedGraph<never, never>), |
| 1462 | "Cannot find weakly connected components of undirected graph" |
| 1463 | ) |
| 1464 | assertGraphError( |
| 1465 | () => Graph.stronglyConnectedComponents(undirectedGraph as Graph.DirectedGraph<never, never>), |
| 1466 | "Cannot find strongly connected components of undirected graph" |
| 1467 | ) |
| 1468 | assertGraphError( |
| 1469 | () => Graph.isTree(directedGraph as Graph.UndirectedGraph<never, never>), |
| 1470 | "Cannot determine tree status of directed graph" |
| 1471 | ) |
| 1472 | assertGraphError(() => Graph.hasPath(Graph.directed(), 0, 1), "Node 0 does not exist") |
| 1473 | }) |
| 1474 | }) |
| 1475 | |
| 1476 | describe("bipartite graphs", () => { |
| 1477 | it("recognizes even, odd, disconnected, and self-loop cases", () => { |
| 1478 | const even = undirected([0, 1, 2, 3], [[0, 1, 1], [1, 2, 1], [2, 3, 1], [3, 0, 1]]) |
| 1479 | assert.strictEqual(Graph.isBipartite(even), true) |
| 1480 | assert.strictEqual(Graph.isBipartite(Graph.beginMutation(even)), true) |
| 1481 | assert.strictEqual(Graph.isBipartite(undirected([0, 1, 2], [[0, 1, 1], [1, 2, 1], [2, 0, 1]])), false) |
| 1482 | assert.strictEqual(Graph.isBipartite(undirected([0, 1, 2, 3], [[0, 1, 1], [2, 3, 1]])), true) |
| 1483 | assert.strictEqual(Graph.isBipartite(undirected([0], [[0, 0, 1]])), false) |
| 1484 | }) |
| 1485 | |
| 1486 | it("reads fresh mutable structure after bipartite mutations", () => { |
| 1487 | const mutable = Graph.beginMutation(undirected([0, 1, 2], [[0, 1, 1], [1, 2, 1]])) |
| 1488 | assert.strictEqual(Graph.isBipartite(mutable), true) |
| 1489 | Graph.addEdge(mutable, 2, 0, 1) |
| 1490 | assert.strictEqual(Graph.isBipartite(mutable), false) |
| 1491 | Graph.removeEdge(mutable, 2) |
| 1492 | Graph.addEdge(mutable, 0, 1, 1) |
| 1493 | assert.strictEqual(Graph.isBipartite(mutable), true) |
| 1494 | Graph.addEdge(mutable, 2, 2, 1) |
| 1495 | assert.strictEqual(Graph.isBipartite(mutable), false) |
| 1496 | }) |
| 1497 | |
| 1498 | it("returns deterministic maximum matches and the first parallel edge", () => { |
| 1499 | const graph = undirected([0, 1, 2, 3], [[0, 2, "first"], [2, 0, "parallel"], [0, 3, "edge"], [1, 2, "edge"], [ |
| 1500 | 1, |
| 1501 | 3, |
| 1502 | "edge" |
| 1503 | ]]) |
| 1504 | assert.deepStrictEqual(Graph.maximumBipartiteMatching(graph), [ |
| 1505 | { left: 0, right: 2, edge: 0 }, |
| 1506 | { left: 1, right: 3, edge: 4 } |
| 1507 | ]) |
| 1508 | assert.deepStrictEqual(Graph.maximumBipartiteMatching(Graph.beginMutation(graph)), [ |
| 1509 | { left: 0, right: 2, edge: 0 }, |
| 1510 | { left: 1, right: 3, edge: 4 } |
| 1511 | ]) |
| 1512 | }) |
| 1513 | |
| 1514 | it("matches a brute-force oracle for every three-by-three bipartite graph", () => { |
| 1515 | const oracle = (adjacency: ReadonlyArray<ReadonlyArray<number>>, left = 0, used = 0): number => { |
| 1516 | if (left === adjacency.length) return 0 |
| 1517 | let best = oracle(adjacency, left + 1, used) |
| 1518 | for (const right of adjacency[left]) { |
| 1519 | if ((used & (1 << right)) === 0) best = Math.max(best, 1 + oracle(adjacency, left + 1, used | (1 << right))) |
| 1520 | } |
| 1521 | return best |
| 1522 | } |
| 1523 | for (let mask = 0; mask < 1 << 9; mask++) { |
| 1524 | const adjacency: Array<Array<number>> = [[], [], []] |
| 1525 | const graph = Graph.undirected<void, void>((mutable) => { |
| 1526 | for (let i = 0; i < 6; i++) Graph.addNode(mutable, undefined) |
| 1527 | for (let left = 0; left < 3; left++) { |
| 1528 | for (let right = 0; right < 3; right++) { |
| 1529 | if ((mask & (1 << (left * 3 + right))) !== 0) { |
| 1530 | adjacency[left].push(right) |
| 1531 | Graph.addEdge(mutable, left, right + 3, undefined) |
| 1532 | } |
| 1533 | } |
| 1534 | } |
| 1535 | }) |
| 1536 | const matching = Graph.maximumBipartiteMatching(graph) |
| 1537 | assert.strictEqual(matching.length, oracle(adjacency)) |
| 1538 | assert.strictEqual(new Set(matching.map((match) => match.left)).size, matching.length) |
| 1539 | assert.strictEqual(new Set(matching.map((match) => match.right)).size, matching.length) |
| 1540 | for (const match of matching) { |
| 1541 | assert.ok(match.left >= 0 && match.left < 3) |
| 1542 | assert.ok(match.right >= 3 && match.right < 6) |
| 1543 | const edge = Option.getOrThrow(Graph.getEdge(graph, match.edge)) |
| 1544 | assert.ok( |
| 1545 | (edge.source === match.left && edge.target === match.right) || |
| 1546 | (edge.source === match.right && edge.target === match.left) |
| 1547 | ) |
| 1548 | } |
| 1549 | } |
| 1550 | }) |
| 1551 | |
| 1552 | it("rejects directed and non-bipartite graphs", () => { |
| 1553 | assertGraphError( |
| 1554 | () => Graph.isBipartite(Graph.directed() as unknown as Graph.UndirectedGraph<never, never>), |
| 1555 | "Cannot determine bipartite status of directed graph" |
| 1556 | ) |
| 1557 | assertGraphError( |
| 1558 | () => Graph.maximumBipartiteMatching(Graph.directed() as unknown as Graph.UndirectedGraph<never, never>), |
| 1559 | "Cannot find bipartite matching of directed graph" |
| 1560 | ) |
| 1561 | assertGraphError( |
| 1562 | () => Graph.maximumBipartiteMatching(undirected([0, 1, 2], [[0, 1, 1], [1, 2, 1], [2, 0, 1]])), |
| 1563 | "Cannot find bipartite matching of non-bipartite graph" |
| 1564 | ) |
| 1565 | }) |
| 1566 | }) |
| 1567 | |
| 1568 | describe("low-link connectivity", () => { |
| 1569 | const analyze = <N, E>(graph: Graph.UndirectedGraph<N, E> | Graph.MutableUndirectedGraph<N, E>) => ({ |
| 1570 | bridges: Graph.bridges(graph), |
| 1571 | articulationPoints: Graph.articulationPoints(graph), |
| 1572 | biconnectedComponents: Graph.biconnectedComponents(graph) |
| 1573 | }) |
| 1574 | |
| 1575 | it("handles paths, cycles, disconnected components, parallel edges, loops, and sparse indexes", () => { |
| 1576 | const graph = Graph.fromSnapshot({ |
| 1577 | type: "undirected", |
| 1578 | nodes: [{ index: 2, data: "A" }, { index: 5, data: "B" }, { index: 9, data: "C" }, { index: 12, data: "D" }], |
| 1579 | edges: [ |
| 1580 | { index: 3, source: 5, target: 2, data: "first" }, |
| 1581 | { index: 7, source: 2, target: 5, data: "parallel" }, |
| 1582 | { index: 11, source: 5, target: 9, data: "bridge" }, |
| 1583 | { index: 13, source: 9, target: 9, data: "loop" } |
| 1584 | ] |
| 1585 | }) |
| 1586 | const expected = { |
| 1587 | bridges: [11], |
| 1588 | articulationPoints: [5], |
| 1589 | biconnectedComponents: [[2, 5], [5, 9], [9]] |
| 1590 | } |
| 1591 | assert.deepStrictEqual(analyze(graph), expected) |
| 1592 | assert.deepStrictEqual(analyze(Graph.beginMutation(graph)), expected) |
| 1593 | }) |
| 1594 | |
| 1595 | it("groups cycles sharing an articulation point across disconnected components", () => { |
| 1596 | const graph = undirected<void, void>(new Array(8).fill(undefined), [ |
| 1597 | [0, 1, undefined], |
| 1598 | [1, 2, undefined], |
| 1599 | [2, 0, undefined], |
| 1600 | [2, 3, undefined], |
| 1601 | [3, 4, undefined], |
| 1602 | [4, 2, undefined], |
| 1603 | [5, 6, undefined] |
| 1604 | ]) |
| 1605 | assert.deepStrictEqual(analyze(graph), { |
| 1606 | bridges: [6], |
| 1607 | articulationPoints: [2], |
| 1608 | biconnectedComponents: [[0, 1, 2], [2, 3, 4], [5, 6]] |
| 1609 | }) |
| 1610 | }) |
| 1611 | |
| 1612 | it("returns empty results for empty and isolated graphs", () => { |
| 1613 | assert.deepStrictEqual(analyze(Graph.undirected()), { |
| 1614 | bridges: [], |
| 1615 | articulationPoints: [], |
| 1616 | biconnectedComponents: [] |
| 1617 | }) |
| 1618 | assert.deepStrictEqual(analyze(undirected<void, never>([undefined], [])), { |
| 1619 | bridges: [], |
| 1620 | articulationPoints: [], |
| 1621 | biconnectedComponents: [] |
| 1622 | }) |
| 1623 | }) |
| 1624 | |
| 1625 | it("rejects directed graphs at runtime", () => { |
| 1626 | const graph = Graph.directed() as unknown as Graph.UndirectedGraph<never, never> |
| 1627 | for (const operation of [Graph.bridges, Graph.articulationPoints, Graph.biconnectedComponents]) { |
| 1628 | assertGraphError(() => operation(graph), "Cannot analyze undirected connectivity of directed graph") |
| 1629 | } |
| 1630 | }) |
| 1631 | }) |
| 1632 | |
| 1633 | describe("flow", () => { |
| 1634 | it("returns fixed flow and cut results in data-first and data-last forms", () => { |
| 1635 | const graph = directed(["source", "target"], [[0, 1, 3]]) |
| 1636 | const config = { source: 0, target: 1, capacity: (edge: number) => edge } |
| 1637 | const flow = { value: 3, flows: new Map([[0, 3]]), cut: [0] } |
| 1638 | const cut = { value: 3, edges: [0], source: [0], target: [1] } |
| 1639 | assert.deepStrictEqual(Graph.maximumFlow(graph, config), flow) |
| 1640 | assert.deepStrictEqual(Graph.maximumFlow(config)(graph), flow) |
| 1641 | assert.deepStrictEqual(Graph.minimumCut(graph, config), cut) |
| 1642 | assert.deepStrictEqual(Graph.minimumCut(config)(Graph.beginMutation(graph)), cut) |
| 1643 | }) |
| 1644 | |
| 1645 | it("enforces capacities, conservation, and max-flow/min-cut equality", () => { |
| 1646 | const capacities = [16, 13, 10, 4, 12, 9, 14, 7, 20, 4] |
| 1647 | const endpoints = [[0, 1], [0, 2], [1, 2], [2, 1], [1, 3], [3, 2], [2, 4], [4, 3], [3, 5], [4, 5]] as const |
| 1648 | const graph = directed<void, number>( |
| 1649 | new Array(6).fill(undefined), |
| 1650 | endpoints.map(([source, target], index) => [source, target, capacities[index]]) |
| 1651 | ) |
| 1652 | const config = { source: 0, target: 5, capacity: (edge: number) => edge } |
| 1653 | for (const candidate of [graph, Graph.beginMutation(graph)]) { |
| 1654 | const flow = Graph.maximumFlow(candidate, config) |
| 1655 | const cut = Graph.minimumCut(candidate, config) |
| 1656 | const balance = new Float64Array(6) |
| 1657 | for (let edge = 0; edge < endpoints.length; edge++) { |
| 1658 | const value = flow.flows.get(edge)! |
| 1659 | assert.ok(value >= 0 && value <= capacities[edge]) |
| 1660 | balance[endpoints[edge][0]] -= value |
| 1661 | balance[endpoints[edge][1]] += value |
| 1662 | } |
| 1663 | assert.strictEqual(flow.value, 23) |
| 1664 | assert.strictEqual(cut.value, 23) |
| 1665 | assert.strictEqual(cut.edges.reduce((total, edge) => total + capacities[edge], 0), 23) |
| 1666 | assert.deepStrictEqual(Array.from(balance), [-23, 0, 0, 0, 0, 23]) |
| 1667 | assert.deepStrictEqual([...cut.source, ...cut.target].sort((a, b) => a - b), [0, 1, 2, 3, 4, 5]) |
| 1668 | } |
| 1669 | }) |
| 1670 | |
| 1671 | it("uses reverse residual edges to reroute flow", () => { |
| 1672 | const graph = directed<void, number>(new Array(6).fill(undefined), [ |
| 1673 | [0, 1, 1], |
| 1674 | [0, 2, 1], |
| 1675 | [1, 3, 1], |
| 1676 | [2, 3, 1], |
| 1677 | [3, 5, 1], |
| 1678 | [1, 4, 1], |
| 1679 | [4, 5, 1] |
| 1680 | ]) |
| 1681 | assert.strictEqual(Graph.maximumFlow(graph, { source: 0, target: 5, capacity: (edge) => edge }).value, 2) |
| 1682 | }) |
| 1683 | |
| 1684 | it("handles parallel edges, self-loops, fractions, and disconnected targets", () => { |
| 1685 | const graph = directed<void, number>(new Array(4).fill(undefined), [ |
| 1686 | [0, 0, 100], |
| 1687 | [0, 1, 0], |
| 1688 | [0, 2, 0.75], |
| 1689 | [2, 1, 1], |
| 1690 | [0, 2, 0.25] |
| 1691 | ]) |
| 1692 | assert.deepStrictEqual(Graph.maximumFlow(graph, { source: 0, target: 1, capacity: (edge) => edge }), { |
| 1693 | value: 1, |
| 1694 | flows: new Map([[0, 0], [1, 0], [2, 0.75], [3, 1], [4, 0.25]]), |
| 1695 | cut: [1, 2, 4] |
| 1696 | }) |
| 1697 | assert.deepStrictEqual(Graph.maximumFlow(graph, { source: 0, target: 3, capacity: (edge) => edge }), { |
| 1698 | value: 0, |
| 1699 | flows: new Map([[0, 0], [1, 0], [2, 0], [3, 0], [4, 0]]), |
| 1700 | cut: [] |
| 1701 | }) |
| 1702 | }) |
| 1703 | |
| 1704 | it("rejects invalid graphs, endpoints, capacities, and finite-range overflow", () => { |
| 1705 | const graph = directed<void, number>([undefined, undefined], []) |
| 1706 | assertGraphError( |
| 1707 | () => Graph.maximumFlow(graph, { source: 0, target: 2, capacity: (edge) => edge }), |
| 1708 | "Node 2 does not exist" |
| 1709 | ) |
| 1710 | assertGraphError( |
| 1711 | () => Graph.maximumFlow(graph, { source: 0, target: 0, capacity: (edge) => edge }), |
| 1712 | "Flow source and target must be different nodes" |
| 1713 | ) |
| 1714 | assertGraphError( |
| 1715 | () => |
| 1716 | Graph.maximumFlow(Graph.undirected() as unknown as Graph.DirectedGraph<never, number>, { |
| 1717 | source: 0, |
| 1718 | target: 1, |
| 1719 | capacity: (edge) => edge |
| 1720 | }), |
| 1721 | "Cannot compute flow of undirected graph" |
| 1722 | ) |
| 1723 | for (const capacity of [-1, NaN, Infinity, -Infinity]) { |
| 1724 | const invalid = directed<void, number>([undefined, undefined], [[0, 0, capacity]]) |
| 1725 | assertGraphError( |
| 1726 | () => Graph.maximumFlow(invalid, { source: 0, target: 1, capacity: (edge) => edge }), |
| 1727 | "Edge 0 capacity must be a finite non-negative number" |
| 1728 | ) |
| 1729 | } |
| 1730 | const overflow = directed<void, number>([undefined, undefined], [[0, 1, Number.MAX_VALUE], [ |
| 1731 | 0, |
| 1732 | 1, |
| 1733 | Number.MAX_VALUE |
| 1734 | ]]) |
| 1735 | assertGraphError( |
| 1736 | () => Graph.maximumFlow(overflow, { source: 0, target: 1, capacity: (edge) => edge }), |
| 1737 | "Maximum flow exceeds the finite number range" |
| 1738 | ) |
| 1739 | }) |
| 1740 | }) |
| 1741 | |
| 1742 | describe("spanning forests and reductions", () => { |
| 1743 | it("preserves sparse indexes, isolated nodes, and fixed mutable parity in minimum spanning forests", () => { |
| 1744 | const graph = Graph.fromSnapshot({ |
| 1745 | type: "undirected", |
| 1746 | nodes: [{ index: 2, data: "A" }, { index: 5, data: "B" }, { index: 9, data: "C" }, { |
| 1747 | index: 20, |
| 1748 | data: "isolated" |
| 1749 | }], |
| 1750 | edges: [ |
| 1751 | { index: 3, source: 2, target: 5, data: 4 }, |
| 1752 | { index: 7, source: 2, target: 5, data: 1 }, |
| 1753 | { index: 11, source: 5, target: 9, data: -2 }, |
| 1754 | { index: 13, source: 2, target: 9, data: 2 }, |
| 1755 | { index: 17, source: 9, target: 20, data: Infinity } |
| 1756 | ] |
| 1757 | }) |
| 1758 | const expected = { |
| 1759 | type: "undirected", |
| 1760 | nodes: [{ index: 2, data: "A" }, { index: 5, data: "B" }, { index: 9, data: "C" }, { |
| 1761 | index: 20, |
| 1762 | data: "isolated" |
| 1763 | }], |
| 1764 | edges: [{ index: 7, source: 2, target: 5, data: 1 }, { index: 11, source: 5, target: 9, data: -2 }] |
| 1765 | } as const |
| 1766 | assertSnapshot(Graph.minimumSpanningForest(graph, (edge) => edge), expected) |
| 1767 | assertSnapshot(Graph.minimumSpanningForest(Graph.beginMutation(graph), (edge) => edge), expected) |
| 1768 | }) |
| 1769 | |
| 1770 | it("breaks equal spanning-forest weights by first edge order", () => { |
| 1771 | const graph = undirected([0, 1, 2], [[0, 1, 1], [1, 2, 1], [0, 2, 1]]) |
| 1772 | assert.deepStrictEqual( |
| 1773 | Graph.toSnapshot(Graph.minimumSpanningForest(graph, (edge) => edge)).edges.map((edge) => edge.index), |
| 1774 | [0, 1] |
| 1775 | ) |
| 1776 | }) |
| 1777 | |
| 1778 | it("preserves sparse reachability and first parallel edges in transitive reductions", () => { |
| 1779 | const graph = Graph.fromSnapshot({ |
| 1780 | type: "directed", |
| 1781 | nodes: [{ index: 2, data: "A" }, { index: 5, data: "B" }, { index: 9, data: "C" }], |
| 1782 | edges: [ |
| 1783 | { index: 3, source: 2, target: 5, data: "first" }, |
| 1784 | { index: 4, source: 2, target: 5, data: "parallel" }, |
| 1785 | { index: 7, source: 5, target: 9, data: "next" }, |
| 1786 | { index: 11, source: 2, target: 9, data: "redundant" } |
| 1787 | ] |
| 1788 | }) |
| 1789 | const expected = { |
| 1790 | type: "directed", |
| 1791 | nodes: [{ index: 2, data: "A" }, { index: 5, data: "B" }, { index: 9, data: "C" }], |
| 1792 | edges: [{ index: 3, source: 2, target: 5, data: "first" }, { index: 7, source: 5, target: 9, data: "next" }] |
| 1793 | } as const |
| 1794 | assertSnapshot(Graph.transitiveReduction(graph), expected) |
| 1795 | assertSnapshot(Graph.transitiveReduction(Graph.beginMutation(graph)), expected) |
| 1796 | }) |
| 1797 | |
| 1798 | it("keeps both branches of a diamond", () => { |
| 1799 | const graph = directed([0, 1, 2, 3], [[0, 1, 1], [0, 2, 1], [1, 3, 1], [2, 3, 1]]) |
| 1800 | assert.deepStrictEqual(Array.from(Graph.indices(Graph.edges(Graph.transitiveReduction(graph)))), [0, 1, 2, 3]) |
| 1801 | }) |
| 1802 | |
| 1803 | it("rejects invalid kinds, weights, and cyclic reductions", () => { |
| 1804 | assertGraphError( |
| 1805 | () => Graph.minimumSpanningForest(Graph.directed() as unknown as Graph.UndirectedGraph<never, number>, () => 1), |
| 1806 | "Cannot find minimum spanning forest of directed graph" |
| 1807 | ) |
| 1808 | for (const weight of [NaN, -Infinity]) { |
| 1809 | assertGraphError( |
| 1810 | () => Graph.minimumSpanningForest(undirected([0, 1], [[0, 1, weight]]), (edge) => edge), |
| 1811 | "Minimum spanning forest does not support NaN or -Infinity edge weights" |
| 1812 | ) |
| 1813 | } |
| 1814 | assertGraphError( |
| 1815 | () => Graph.transitiveReduction(Graph.undirected() as unknown as Graph.DirectedGraph<never, never>), |
| 1816 | "Cannot transitively reduce undirected graph" |
| 1817 | ) |
| 1818 | assertGraphError( |
| 1819 | () => Graph.transitiveReduction(directed([0, 1], [[0, 1, 1], [1, 0, 1]])), |
| 1820 | "Cannot transitively reduce cyclic graph" |
| 1821 | ) |
| 1822 | }) |
| 1823 | }) |
| 1824 | |
| 1825 | describe("pathfinding", () => { |
| 1826 | const graph = directed(["source", "first", "second", "target"], [ |
| 1827 | [0, 1, 1], |
| 1828 | [0, 2, 1], |
| 1829 | [2, 3, 1], |
| 1830 | [1, 3, 1] |
| 1831 | ]) |
| 1832 | const expected = { path: [0, 1, 3], edges: [0, 3], distance: 2, costs: [1, 1] } |
| 1833 | |
| 1834 | it("returns complete Dijkstra and A* paths with deterministic ties and fixed mutable parity", () => { |
| 1835 | const dijkstra = { source: 0, target: 3, cost: (edge: number) => edge } |
| 1836 | const astar = { ...dijkstra, heuristic: () => 0 } |
| 1837 | const bellmanFord = { path: [0, 2, 3], edges: [1, 2], distance: 2, costs: [1, 1] } |
| 1838 | assertPath(Graph.dijkstra(graph, dijkstra), expected) |
| 1839 | assertPath(Graph.dijkstra(Graph.beginMutation(graph), dijkstra), expected) |
| 1840 | assertPath(Graph.dijkstra(dijkstra)(graph), expected) |
| 1841 | assertPath(Graph.astar(graph, astar), expected) |
| 1842 | assertPath(Graph.astar(Graph.beginMutation(graph), astar), expected) |
| 1843 | assertPath(Graph.astar(astar)(graph), expected) |
| 1844 | assertPath(Graph.bellmanFord(dijkstra)(graph), bellmanFord) |
| 1845 | const all = Graph.floydWarshall((edge: number) => edge)(graph) |
| 1846 | assert.strictEqual(all.distances.get(0)?.get(3), 2) |
| 1847 | assert.deepStrictEqual(all.paths.get(0)?.get(3), expected.path) |
| 1848 | assert.deepStrictEqual(all.edges.get(0)?.get(3), expected.edges) |
| 1849 | assert.deepStrictEqual(all.costs.get(0)?.get(3), expected.costs) |
| 1850 | }) |
| 1851 | |
| 1852 | it("preserves parallel edges for topological and weighted algorithms", () => { |
| 1853 | const graph = directed([0, 1, 2], [[0, 1, 10], [0, 1, 1], [1, 2, 2]]) |
| 1854 | |
| 1855 | assertIndices(Graph.topo(graph), [0, 1, 2]) |
| 1856 | assertPath(Graph.dijkstra(graph, { source: 0, target: 2, cost: (edge) => edge }), { |
| 1857 | path: [0, 1, 2], |
| 1858 | edges: [1, 2], |
| 1859 | distance: 3, |
| 1860 | costs: [1, 2] |
| 1861 | }) |
| 1862 | }) |
| 1863 | |
| 1864 | it("handles decreased Dijkstra priorities with fresh order and stale entries", () => { |
| 1865 | const reordered = directed(["source", "improved", "shortcut", "direct", "target"], [ |
| 1866 | [0, 1, 10], |
| 1867 | [0, 2, 1], |
| 1868 | [0, 3, 2], |
| 1869 | [2, 1, 1], |
| 1870 | [1, 4, 1], |
| 1871 | [3, 4, 1] |
| 1872 | ]) |
| 1873 | assertPath(Graph.dijkstra(reordered, { source: 0, target: 4, cost: (edge) => edge }), { |
| 1874 | path: [0, 3, 4], |
| 1875 | edges: [2, 5], |
| 1876 | distance: 3, |
| 1877 | costs: [2, 1] |
| 1878 | }) |
| 1879 | |
| 1880 | const stale = directed(["source", "improved", "shortcut", "middle", "target"], [ |
| 1881 | [0, 1, 10], |
| 1882 | [0, 2, 1], |
| 1883 | [2, 1, 1], |
| 1884 | [1, 3, 20], |
| 1885 | [3, 4, 20] |
| 1886 | ]) |
| 1887 | assertPath(Graph.dijkstra(stale, { source: 0, target: 4, cost: (edge) => edge }), { |
| 1888 | path: [0, 2, 1, 3, 4], |
| 1889 | edges: [1, 2, 3, 4], |
| 1890 | distance: 42, |
| 1891 | costs: [1, 1, 20, 20] |
| 1892 | }) |
| 1893 | }) |
| 1894 | |
| 1895 | it("skips stale A* entries and does not reopen closed nodes", () => { |
| 1896 | const stale = directed(["source", "improved", "shortcut", "middle", "target"], [ |
| 1897 | [0, 1, 10], |
| 1898 | [0, 2, 1], |
| 1899 | [2, 1, 1], |
| 1900 | [1, 3, 20], |
| 1901 | [3, 4, 20] |
| 1902 | ]) |
| 1903 | assertPath(Graph.astar(stale, { source: 0, target: 4, cost: (edge) => edge, heuristic: () => 0 }), { |
| 1904 | path: [0, 2, 1, 3, 4], |
| 1905 | edges: [1, 2, 3, 4], |
| 1906 | distance: 42, |
| 1907 | costs: [1, 1, 20, 20] |
| 1908 | }) |
| 1909 | |
| 1910 | const closed = directed(["source", "closed", "later", "target"], [ |
| 1911 | [0, 1, 10], |
| 1912 | [1, 3, 1], |
| 1913 | [0, 2, 1], |
| 1914 | [2, 1, 1] |
| 1915 | ]) |
| 1916 | assertPath( |
| 1917 | Graph.astar(closed, { |
| 1918 | source: 0, |
| 1919 | target: 3, |
| 1920 | cost: (edge) => edge, |
| 1921 | heuristic: (node) => node === "closed" ? -100 : 0 |
| 1922 | }), |
| 1923 | { path: [0, 1, 3], edges: [0, 1], distance: 11, costs: [10, 1] } |
| 1924 | ) |
| 1925 | }) |
| 1926 | |
| 1927 | it("preserves sparse parallel edge identity across all shortest-path algorithms", () => { |
| 1928 | const graph = Graph.fromSnapshot({ |
| 1929 | type: "directed", |
| 1930 | nodes: [{ index: 2, data: "source" }, { index: 5, data: "target" }], |
| 1931 | edges: [{ index: 3, source: 2, target: 5, data: 1 }, { index: 1_000_000, source: 2, target: 5, data: 1 }] |
| 1932 | }) |
| 1933 | const expected = { path: [2, 5], edges: [3], distance: 1, costs: [1] } |
| 1934 | for (const candidate of [graph, Graph.beginMutation(graph)]) { |
| 1935 | assertPath(Graph.dijkstra(candidate, { source: 2, target: 5, cost: (edge) => edge }), expected) |
| 1936 | assertPath(Graph.astar(candidate, { source: 2, target: 5, cost: (edge) => edge, heuristic: () => 0 }), expected) |
| 1937 | assertPath(Graph.bellmanFord(candidate, { source: 2, target: 5, cost: (edge) => edge }), expected) |
| 1938 | const all = Graph.floydWarshall(candidate, (edge) => edge) |
| 1939 | assert.strictEqual(all.distances.get(2)?.get(5), 1) |
| 1940 | assert.deepStrictEqual(all.paths.get(2)?.get(5), [2, 5]) |
| 1941 | assert.deepStrictEqual(all.edges.get(2)?.get(5), [3]) |
| 1942 | assert.deepStrictEqual(all.costs.get(2)?.get(5), [1]) |
| 1943 | } |
| 1944 | }) |
| 1945 | |
| 1946 | it("handles unreachable and same-node paths completely", () => { |
| 1947 | const graph = directed<string, number>(["A", "B"], []) |
| 1948 | const expected = { path: [0], edges: [], distance: 0, costs: [] } |
| 1949 | assert.deepStrictEqual(Graph.dijkstra(graph, { source: 0, target: 1, cost: (edge) => edge }), Option.none()) |
| 1950 | assertPath(Graph.dijkstra(graph, { source: 0, target: 0, cost: (edge) => edge }), expected) |
| 1951 | assertPath(Graph.astar(graph, { source: 0, target: 0, cost: (edge) => edge, heuristic: () => 0 }), expected) |
| 1952 | assertPath(Graph.bellmanFord(graph, { source: 0, target: 0, cost: (edge) => edge }), expected) |
| 1953 | const all = Graph.floydWarshall(graph, (edge) => edge) |
| 1954 | assert.strictEqual(all.distances.get(0)?.get(1), Infinity) |
| 1955 | assert.strictEqual(all.paths.get(0)?.get(1), null) |
| 1956 | assert.deepStrictEqual(all.edges.get(0)?.get(1), []) |
| 1957 | assert.deepStrictEqual(all.costs.get(0)?.get(1), []) |
| 1958 | assert.strictEqual(all.distances.get(0)?.get(0), 0) |
| 1959 | assert.deepStrictEqual(all.paths.get(0)?.get(0), [0]) |
| 1960 | assert.deepStrictEqual(all.edges.get(0)?.get(0), []) |
| 1961 | assert.deepStrictEqual(all.costs.get(0)?.get(0), []) |
| 1962 | }) |
| 1963 | |
| 1964 | it("uses negative Bellman-Ford edges in shortest paths", () => { |
| 1965 | assertPath( |
| 1966 | Graph.bellmanFord(directed([0, 1, 2], [[0, 1, -1], [1, 2, 3], [0, 2, 5]]), { |
| 1967 | source: 0, |
| 1968 | target: 2, |
| 1969 | cost: (edge) => edge |
| 1970 | }), |
| 1971 | { path: [0, 1, 2], edges: [0, 1], distance: 2, costs: [-1, 3] } |
| 1972 | ) |
| 1973 | }) |
| 1974 | |
| 1975 | it("ignores negative cycles separated from the Bellman-Ford target by impassable edges", () => { |
| 1976 | const graph = directed([0, 1, 2, 3], [[0, 1, 1], [1, 2, -2], [2, 1, 1], [0, 3, 5], [2, 3, Infinity]]) |
| 1977 | const expected = { path: [0, 3], edges: [3], distance: 5, costs: [5] } |
| 1978 | assertPath(Graph.bellmanFord(graph, { source: 0, target: 3, cost: (edge) => edge }), expected) |
| 1979 | assertPath( |
| 1980 | Graph.bellmanFord(Graph.beginMutation(graph), { source: 0, target: 3, cost: (edge) => edge }), |
| 1981 | expected |
| 1982 | ) |
| 1983 | |
| 1984 | const unreachable = directed([0, 1, 2, 3], [[0, 1, 1], [1, 2, -2], [2, 1, 1], [2, 3, Infinity]]) |
| 1985 | assert.deepStrictEqual( |
| 1986 | Graph.bellmanFord(unreachable, { source: 0, target: 3, cost: (edge) => edge }), |
| 1987 | Option.none() |
| 1988 | ) |
| 1989 | }) |
| 1990 | |
| 1991 | it("detects directed and undirected negative self-loops when source equals target", () => { |
| 1992 | for (const graph of [directed([0], [[0, 0, -1]]), undirected([0], [[0, 0, -1]])]) { |
| 1993 | assertGraphError( |
| 1994 | () => Graph.bellmanFord(graph, { source: 0, target: 0, cost: (edge) => edge }), |
| 1995 | "Negative cycle affects path to node 0" |
| 1996 | ) |
| 1997 | } |
| 1998 | }) |
| 1999 | |
| 2000 | it("preserves null edge payloads in Floyd-Warshall multihop paths", () => { |
| 2001 | type Edge = null | { readonly weight: number } |
| 2002 | const graph = directed<string, Edge>(["A", "B", "C"], [ |
| 2003 | [0, 1, null], |
| 2004 | [1, 2, null], |
| 2005 | [0, 2, { weight: 10 }] |
| 2006 | ]) |
| 2007 | const result = Graph.floydWarshall(graph, (edge) => edge === null ? 1 : edge.weight) |
| 2008 | assert.strictEqual(result.distances.get(0)?.get(2), 2) |
| 2009 | assert.deepStrictEqual(result.paths.get(0)?.get(2), [0, 1, 2]) |
| 2010 | assert.deepStrictEqual(result.edges.get(0)?.get(2), [0, 1]) |
| 2011 | assert.deepStrictEqual(result.costs.get(0)?.get(2), [null, null]) |
| 2012 | }) |
| 2013 | |
| 2014 | it("treats positive Infinity as unreachable in every shortest-path algorithm", () => { |
| 2015 | const graph = directed([0, 1], [[0, 1, Infinity]]) |
| 2016 | assert.deepStrictEqual(Graph.dijkstra(graph, { source: 0, target: 1, cost: (edge) => edge }), Option.none()) |
| 2017 | assert.deepStrictEqual( |
| 2018 | Graph.astar(graph, { source: 0, target: 1, cost: (edge) => edge, heuristic: () => 0 }), |
| 2019 | Option.none() |
| 2020 | ) |
| 2021 | assert.deepStrictEqual(Graph.bellmanFord(graph, { source: 0, target: 1, cost: (edge) => edge }), Option.none()) |
| 2022 | const all = Graph.floydWarshall(graph, (edge) => edge) |
| 2023 | assert.strictEqual(all.distances.get(0)?.get(1), Infinity) |
| 2024 | assert.strictEqual(all.paths.get(0)?.get(1), null) |
| 2025 | assert.deepStrictEqual(all.edges.get(0)?.get(1), []) |
| 2026 | assert.deepStrictEqual(all.costs.get(0)?.get(1), []) |
| 2027 | }) |
| 2028 | |
| 2029 | it("reports relevant Bellman-Ford and Floyd-Warshall negative cycles", () => { |
| 2030 | const cycle = directed([0, 1, 2], [[0, 1, 1], [1, 2, -3], [2, 0, 1]]) |
| 2031 | assertGraphError( |
| 2032 | () => Graph.bellmanFord(cycle, { source: 0, target: 2, cost: (edge) => edge }), |
| 2033 | "Negative cycle affects path to node 2" |
| 2034 | ) |
| 2035 | assertGraphError(() => Graph.floydWarshall(cycle, (edge) => edge), "Negative cycle detected involving node 0") |
| 2036 | const negativeUndirected = undirected([0, 1], [[0, 1, -1]]) |
| 2037 | assertGraphError( |
| 2038 | () => Graph.bellmanFord(negativeUndirected, { source: 0, target: 1, cost: (edge) => edge }), |
| 2039 | "Negative cycle affects path to node 1" |
| 2040 | ) |
| 2041 | }) |
| 2042 | |
| 2043 | it("validates endpoints, edge weights, heuristics, and finite arithmetic", () => { |
| 2044 | assertGraphError( |
| 2045 | () => Graph.dijkstra(Graph.directed(), { source: 0, target: 1, cost: () => 1 }), |
| 2046 | "Node 0 does not exist" |
| 2047 | ) |
| 2048 | for (const weight of [-1, NaN, -Infinity]) { |
| 2049 | const invalid = directed([0, 1], [[0, 1, weight]]) |
| 2050 | assertGraphError( |
| 2051 | () => Graph.dijkstra(invalid, { source: 0, target: 1, cost: (edge) => edge }), |
| 2052 | "Dijkstra's algorithm requires non-negative edge weights" |
| 2053 | ) |
| 2054 | assertGraphError( |
| 2055 | () => Graph.astar(invalid, { source: 0, target: 1, cost: (edge) => edge, heuristic: () => 0 }), |
| 2056 | "A* algorithm requires non-negative edge weights" |
| 2057 | ) |
| 2058 | } |
| 2059 | for (const heuristic of [NaN, Infinity, -Infinity]) { |
| 2060 | assertGraphError(() => |
| 2061 | Graph.astar(directed<string, never>(["A"], []), { |
| 2062 | source: 0, |
| 2063 | target: 0, |
| 2064 | cost: () => 1, |
| 2065 | heuristic: () => heuristic |
| 2066 | }), "A* algorithm requires finite heuristic values") |
| 2067 | assertGraphError(() => |
| 2068 | Graph.astar(directed(["source", "middle", "target"], [[0, 1, 1], [1, 2, 1]]), { |
| 2069 | source: 0, |
| 2070 | target: 2, |
| 2071 | cost: (edge) => edge, |
| 2072 | heuristic: (node) => node === "middle" ? heuristic : 0 |
| 2073 | }), "A* algorithm requires finite heuristic values") |
| 2074 | } |
| 2075 | for (const weight of [NaN, -Infinity]) { |
| 2076 | const invalid = directed([0, 1], [[0, 1, weight]]) |
| 2077 | assertGraphError( |
| 2078 | () => Graph.bellmanFord(invalid, { source: 0, target: 1, cost: (edge) => edge }), |
| 2079 | "Bellman-Ford algorithm does not support NaN or -Infinity edge weights" |
| 2080 | ) |
| 2081 | assertGraphError( |
| 2082 | () => Graph.floydWarshall(invalid, (edge) => edge), |
| 2083 | "Floyd-Warshall algorithm does not support NaN or -Infinity edge weights" |
| 2084 | ) |
| 2085 | } |
| 2086 | const overflow = directed([0, 1, 2], [[0, 1, Number.MAX_VALUE], [1, 2, Number.MAX_VALUE]]) |
| 2087 | assertGraphError( |
| 2088 | () => Graph.dijkstra(overflow, { source: 0, target: 2, cost: (edge) => edge }), |
| 2089 | "Dijkstra distance calculation exceeded the finite number range" |
| 2090 | ) |
| 2091 | assertGraphError( |
| 2092 | () => Graph.astar(overflow, { source: 0, target: 2, cost: (edge) => edge, heuristic: () => 0 }), |
| 2093 | "A* distance calculation exceeded the finite number range" |
| 2094 | ) |
| 2095 | assertGraphError( |
| 2096 | () => |
| 2097 | Graph.astar(directed([0, 1], [[0, 1, Number.MAX_VALUE]]), { |
| 2098 | source: 0, |
| 2099 | target: 1, |
| 2100 | cost: (edge) => edge, |
| 2101 | heuristic: (node) => node === 1 ? Number.MAX_VALUE : 0 |
| 2102 | }), |
| 2103 | "A* priority calculation exceeded the finite number range" |
| 2104 | ) |
| 2105 | assertGraphError( |
| 2106 | () => Graph.bellmanFord(overflow, { source: 0, target: 2, cost: (edge) => edge }), |
| 2107 | "Bellman-Ford distance calculation exceeded the finite number range" |
| 2108 | ) |
| 2109 | assertGraphError( |
| 2110 | () => Graph.floydWarshall(overflow, (edge) => edge), |
| 2111 | "Floyd-Warshall distance calculation exceeded the finite number range" |
| 2112 | ) |
| 2113 | const underflow = directed([0, 1, 2], [[0, 1, -Number.MAX_VALUE], [1, 2, -Number.MAX_VALUE]]) |
| 2114 | assertGraphError( |
| 2115 | () => Graph.bellmanFord(underflow, { source: 0, target: 2, cost: (edge) => edge }), |
| 2116 | "Bellman-Ford distance calculation exceeded the finite number range" |
| 2117 | ) |
| 2118 | assertGraphError( |
| 2119 | () => Graph.floydWarshall(underflow, (edge) => edge), |
| 2120 | "Floyd-Warshall distance calculation exceeded the finite number range" |
| 2121 | ) |
| 2122 | }) |
| 2123 | |
| 2124 | it("validates negative Dijkstra and A* weights before early returns", () => { |
| 2125 | const early = directed([0, 1, 2], [[0, 1, 1], [0, 2, 2], [2, 1, -5]]) |
| 2126 | const same = directed([0], [[0, 0, -1]]) |
| 2127 | for (const [graph, source, target] of [[early, 0, 1], [same, 0, 0]] as const) { |
| 2128 | assertGraphError( |
| 2129 | () => Graph.dijkstra(graph, { source, target, cost: (edge) => edge }), |
| 2130 | "Dijkstra's algorithm requires non-negative edge weights" |
| 2131 | ) |
| 2132 | assertGraphError( |
| 2133 | () => Graph.astar(graph, { source, target, cost: (edge) => edge, heuristic: () => 0 }), |
| 2134 | "A* algorithm requires non-negative edge weights" |
| 2135 | ) |
| 2136 | } |
| 2137 | }) |
| 2138 | |
| 2139 | it("traverses undirected edges against stored orientation", () => { |
| 2140 | const graph = undirected(["A", "B", "C"], [[0, 1, 1], [2, 1, 1]]) |
| 2141 | const expected = { path: [0, 1, 2], edges: [0, 1], distance: 2, costs: [1, 1] } |
| 2142 | assertPath(Graph.dijkstra(graph, { source: 0, target: 2, cost: (edge) => edge }), expected) |
| 2143 | assertPath(Graph.astar(graph, { source: 0, target: 2, cost: (edge) => edge, heuristic: () => 0 }), expected) |
| 2144 | assertPath(Graph.bellmanFord(graph, { source: 0, target: 2, cost: (edge) => edge }), expected) |
| 2145 | const all = Graph.floydWarshall(graph, (edge) => edge) |
| 2146 | assert.strictEqual(all.distances.get(0)?.get(2), 2) |
| 2147 | assert.deepStrictEqual(all.paths.get(0)?.get(2), [0, 1, 2]) |
| 2148 | assert.deepStrictEqual(all.edges.get(0)?.get(2), [0, 1]) |
| 2149 | assert.deepStrictEqual(all.costs.get(0)?.get(2), [1, 1]) |
| 2150 | }) |
| 2151 | }) |
| 2152 | |
| 2153 | describe("path enumeration", () => { |
| 2154 | it("lazily and repeatably enumerates complete simple paths in edge order", () => { |
| 2155 | const graph = directed([0, 1, 2, 3], [ |
| 2156 | [0, 1, "01"], |
| 2157 | [0, 2, "02"], |
| 2158 | [1, 2, "12"], |
| 2159 | [1, 3, "13"], |
| 2160 | [2, 3, "23"], |
| 2161 | [2, 1, "21"] |
| 2162 | ]) |
| 2163 | const paths = Graph.simplePaths(graph, { source: 0, target: 3, limit: 3 }) |
| 2164 | const expected = [ |
| 2165 | { path: [0, 1, 2, 3], edges: [0, 2, 4], distance: 3, costs: ["01", "12", "23"] }, |
| 2166 | { path: [0, 1, 3], edges: [0, 3], distance: 2, costs: ["01", "13"] }, |
| 2167 | { path: [0, 2, 3], edges: [1, 4], distance: 2, costs: ["02", "23"] } |
| 2168 | ] |
| 2169 | assert.deepStrictEqual(Array.from(paths), expected) |
| 2170 | assert.deepStrictEqual(Array.from(paths), expected) |
| 2171 | assert.deepStrictEqual(Array.from(Graph.simplePaths({ source: 0, target: 3, limit: 3 })(graph)), expected) |
| 2172 | }) |
| 2173 | |
| 2174 | it("enumerates parallel and structurally tied shortest paths exactly", () => { |
| 2175 | const graph = directed([0, 1, 2, 3], [[0, 1, 1], [0, 2, 1], [1, 3, 1], [2, 3, 1], [0, 1, 1]]) |
| 2176 | const expected = [ |
| 2177 | { path: [0, 1, 3], edges: [0, 2], distance: 2, costs: [1, 1] }, |
| 2178 | { path: [0, 1, 3], edges: [4, 2], distance: 2, costs: [1, 1] }, |
| 2179 | { path: [0, 2, 3], edges: [1, 3], distance: 2, costs: [1, 1] } |
| 2180 | ] |
| 2181 | assert.deepStrictEqual( |
| 2182 | Array.from(Graph.allShortestPaths(graph, { source: 0, target: 3, cost: (edge) => edge })), |
| 2183 | expected |
| 2184 | ) |
| 2185 | assert.deepStrictEqual( |
| 2186 | Array.from(Graph.allShortestPaths({ source: 0, target: 3, cost: (edge: number) => edge })(graph)), |
| 2187 | expected |
| 2188 | ) |
| 2189 | assert.deepStrictEqual( |
| 2190 | Array.from(Graph.allShortestPaths(Graph.beginMutation(graph), { |
| 2191 | source: 0, |
| 2192 | target: 3, |
| 2193 | cost: (edge) => edge, |
| 2194 | limit: 2 |
| 2195 | })), |
| 2196 | expected.slice(0, 2) |
| 2197 | ) |
| 2198 | }) |
| 2199 | |
| 2200 | it("terminates zero-cost predecessor cycles and emits only simple shortest paths", () => { |
| 2201 | const graph = directed([0, 1, 2, 3], [[0, 1, 0], [1, 2, 0], [2, 1, 0], [1, 3, 1], [2, 3, 1]]) |
| 2202 | assert.deepStrictEqual( |
| 2203 | Array.from(Graph.allShortestPaths(graph, { source: 0, target: 3, cost: (edge) => edge })), |
| 2204 | [ |
| 2205 | { path: [0, 1, 3], edges: [0, 3], distance: 1, costs: [0, 1] }, |
| 2206 | { path: [0, 1, 2, 3], edges: [0, 1, 4], distance: 1, costs: [0, 0, 1] } |
| 2207 | ] |
| 2208 | ) |
| 2209 | }) |
| 2210 | |
| 2211 | it("defers shortest-path cost evaluation until iteration", () => { |
| 2212 | let calls = 0 |
| 2213 | const paths = Graph.allShortestPaths(directed([0, 1], [[0, 1, 1]]), { |
| 2214 | source: 0, |
| 2215 | target: 1, |
| 2216 | cost: (edge) => { |
| 2217 | calls++ |
| 2218 | return edge |
| 2219 | } |
| 2220 | }) |
| 2221 | assert.strictEqual(calls, 0) |
| 2222 | assert.deepStrictEqual(Array.from(paths), [{ path: [0, 1], edges: [0], distance: 1, costs: [1] }]) |
| 2223 | assert.strictEqual(calls, 1) |
| 2224 | }) |
| 2225 | |
| 2226 | it("revalidates mutable endpoints and isolates active snapshots", () => { |
| 2227 | const removed = Graph.beginMutation(directed([0, 1], [[0, 1, 1]])) |
| 2228 | const pending = Graph.simplePaths(removed, { source: 0, target: 1 }) |
| 2229 | Graph.removeNode(removed, 0) |
| 2230 | assertGraphError(() => Array.from(pending), "Node 0 does not exist") |
| 2231 | |
| 2232 | const shortestRemoved = Graph.beginMutation(directed([0, 1], [[0, 1, 1]])) |
| 2233 | const shortestPending = Graph.allShortestPaths(shortestRemoved, { |
| 2234 | source: 0, |
| 2235 | target: 1, |
| 2236 | cost: (edge) => edge |
| 2237 | }) |
| 2238 | Graph.removeNode(shortestRemoved, 1) |
| 2239 | assertGraphError(() => Array.from(shortestPending), "Node 1 does not exist") |
| 2240 | |
| 2241 | const mutable = Graph.beginMutation(directed([0, 1, 2, 3], [[0, 1, 1], [0, 2, 1], [1, 3, 1], [2, 3, 1]])) |
| 2242 | const paths = Graph.simplePaths(mutable, { source: 0, target: 3 }) |
| 2243 | const iterator = paths[Symbol.iterator]() |
| 2244 | assert.deepStrictEqual(iterator.next().value, { |
| 2245 | path: [0, 1, 3], |
| 2246 | edges: [0, 2], |
| 2247 | distance: 2, |
| 2248 | costs: [1, 1] |
| 2249 | }) |
| 2250 | Graph.removeEdge(mutable, 1) |
| 2251 | assert.deepStrictEqual(iterator.next().value, { |
| 2252 | path: [0, 2, 3], |
| 2253 | edges: [1, 3], |
| 2254 | distance: 2, |
| 2255 | costs: [1, 1] |
| 2256 | }) |
| 2257 | assert.deepStrictEqual(Array.from(paths), [{ path: [0, 1, 3], edges: [0, 2], distance: 2, costs: [1, 1] }]) |
| 2258 | |
| 2259 | const shortestMutable = Graph.beginMutation(directed([0, 1, 2, 3], [ |
| 2260 | [0, 1, 1], |
| 2261 | [0, 2, 1], |
| 2262 | [1, 3, 1], |
| 2263 | [2, 3, 1] |
| 2264 | ])) |
| 2265 | const shortest = Graph.allShortestPaths(shortestMutable, { source: 0, target: 3, cost: (edge) => edge }) |
| 2266 | const shortestIterator = shortest[Symbol.iterator]() |
| 2267 | assert.deepStrictEqual(shortestIterator.next().value, { |
| 2268 | path: [0, 1, 3], |
| 2269 | edges: [0, 2], |
| 2270 | distance: 2, |
| 2271 | costs: [1, 1] |
| 2272 | }) |
| 2273 | Graph.removeEdge(shortestMutable, 1) |
| 2274 | assert.deepStrictEqual(shortestIterator.next().value, { |
| 2275 | path: [0, 2, 3], |
| 2276 | edges: [1, 3], |
| 2277 | distance: 2, |
| 2278 | costs: [1, 1] |
| 2279 | }) |
| 2280 | assert.deepStrictEqual(Array.from(shortest), [ |
| 2281 | { path: [0, 1, 3], edges: [0, 2], distance: 2, costs: [1, 1] } |
| 2282 | ]) |
| 2283 | }) |
| 2284 | |
| 2285 | it("handles empty path enumerations", () => { |
| 2286 | const graph = directed<string, number>(["A", "B"], []) |
| 2287 | const same = [{ path: [0], edges: [], distance: 0, costs: [] }] |
| 2288 | |
| 2289 | assert.deepStrictEqual(Array.from(Graph.simplePaths(graph, { source: 0, target: 0 })), same) |
| 2290 | assert.deepStrictEqual( |
| 2291 | Array.from(Graph.allShortestPaths(graph, { source: 0, target: 0, cost: (edge) => edge })), |
| 2292 | same |
| 2293 | ) |
| 2294 | assert.deepStrictEqual( |
| 2295 | Array.from(Graph.allShortestPaths(graph, { source: 0, target: 1, cost: (edge) => edge })), |
| 2296 | [] |
| 2297 | ) |
| 2298 | }) |
| 2299 | |
| 2300 | it("validates limits, endpoints, and non-negative shortest-path costs", () => { |
| 2301 | const graph = directed([0, 1], [[0, 1, -1]]) |
| 2302 | assertGraphError( |
| 2303 | () => Array.from(Graph.allShortestPaths(graph, { source: 0, target: 1, cost: (edge) => edge })), |
| 2304 | "All shortest paths requires non-negative edge weights" |
| 2305 | ) |
| 2306 | assertGraphError( |
| 2307 | () => Array.from(Graph.allShortestPaths(graph, { source: 0, target: 1, cost: (edge) => edge, limit: 0 })), |
| 2308 | "All shortest paths requires non-negative edge weights" |
| 2309 | ) |
| 2310 | const overflow = directed([0, 1, 2], [[0, 1, Number.MAX_VALUE], [1, 2, Number.MAX_VALUE]]) |
| 2311 | assertGraphError( |
| 2312 | () => Array.from(Graph.allShortestPaths(overflow, { source: 0, target: 2, cost: (edge) => edge })), |
| 2313 | "All shortest paths distance calculation exceeded the finite number range" |
| 2314 | ) |
| 2315 | assertGraphError( |
| 2316 | () => Graph.simplePaths(graph, { source: 0, target: 1, limit: -1 }), |
| 2317 | "Path enumeration limit must be a non-negative integer or Infinity" |
| 2318 | ) |
| 2319 | assertGraphError(() => Graph.simplePaths(graph, { source: 0, target: 2 }), "Node 2 does not exist") |
| 2320 | assert.deepStrictEqual(Array.from(Graph.simplePaths(graph, { source: 0, target: 1, limit: 0 })), []) |
| 2321 | }) |
| 2322 | }) |
| 2323 | |
| 2324 | describe("traversal", () => { |
| 2325 | const graph = directed(["A", "B", "C", "D"], [[0, 1, 1], [0, 2, 2], [1, 3, 3], [2, 3, 4]]) |
| 2326 | |
| 2327 | it("traverses DFS, BFS, and postorder in documented order", () => { |
| 2328 | assertIndices(Graph.dfs(graph, { start: [0] }), [0, 1, 3, 2]) |
| 2329 | assertIndices(Graph.bfs(graph, { start: [0] }), [0, 1, 2, 3]) |
| 2330 | assertIndices(Graph.dfsPostOrder(graph, { start: [0] }), [3, 1, 2, 0]) |
| 2331 | assertIndices(Graph.dfs(graph), []) |
| 2332 | }) |
| 2333 | |
| 2334 | it("preserves postorder with parallel edges, self-loops, and directionless traversal", () => { |
| 2335 | const parallel = directed([0, 1, 2, 3, 4], [ |
| 2336 | [0, 1, 1], |
| 2337 | [0, 1, 2], |
| 2338 | [0, 1, 3], |
| 2339 | [1, 2, 4], |
| 2340 | [1, 3, 5], |
| 2341 | [1, 4, 6], |
| 2342 | [1, 1, 7] |
| 2343 | ]) |
| 2344 | assertIndices(Graph.dfsPostOrder(parallel, { start: [0] }), [2, 3, 4, 1, 0]) |
| 2345 | assertIndices(Graph.dfsPostOrder(parallel, { start: [0, 1] }), [2, 3, 4, 1, 0]) |
| 2346 | |
| 2347 | const directionless = directed([0, 1, 2, 3], [[0, 1, 1], [2, 1, 2], [1, 3, 3], [1, 1, 4]]) |
| 2348 | assertIndices(Graph.dfsPostOrder(directionless, { start: [1], direction: "undirected" }), [3, 0, 2, 1]) |
| 2349 | }) |
| 2350 | |
| 2351 | it("uses shortest distance for radius membership and supports traversal directions", () => { |
| 2352 | const graph = directed([0, 1, 2, 3], [[0, 1, 1], [1, 2, 1], [0, 2, 1], [2, 3, 1]]) |
| 2353 | assertIndices(Graph.dfs(graph, { start: [0], radius: 2 }), [0, 1, 2, 3]) |
| 2354 | assertIndices(Graph.bfs(graph, { start: [2], direction: "incoming" }), [2, 1, 0]) |
| 2355 | assertIndices(Graph.dfsPostOrder(graph, { start: [2], direction: "incoming" }), [0, 1, 2]) |
| 2356 | assertIndices(Graph.bfs(graph, { start: [1], direction: "undirected", radius: 1 }), [1, 2, 0]) |
| 2357 | assertIndices( |
| 2358 | Graph.dfsPostOrder(directed([0, 1, 2], [[0, 1, 1], [1, 2, 1]]), { |
| 2359 | start: [0], |
| 2360 | radius: 1 |
| 2361 | }), |
| 2362 | [1, 0] |
| 2363 | ) |
| 2364 | }) |
| 2365 | |
| 2366 | it("preserves bounded undirected DFS order for reciprocal neighbors", () => { |
| 2367 | const graph = directed<void, number>(new Array(5).fill(undefined), [[0, 1, 1], [4, 1, 2], [1, 4, 3]]) |
| 2368 | |
| 2369 | assertIndices(Graph.dfs(graph, { start: [1], direction: "undirected", radius: 2 }), [1, 4, 0]) |
| 2370 | }) |
| 2371 | |
| 2372 | it("validates radius in data-first and data-last forms", () => { |
| 2373 | for (const radius of [NaN, -Infinity, -1, 0.5]) { |
| 2374 | for ( |
| 2375 | const run of [ |
| 2376 | () => Graph.dfs(graph, { start: [0], radius }), |
| 2377 | () => Graph.bfs({ start: [0], radius })(graph), |
| 2378 | () => Graph.dfsPostOrder(graph, { start: [0], radius }) |
| 2379 | ] |
| 2380 | ) assertGraphError(run, "Traversal radius must be a non-negative integer or Infinity") |
| 2381 | } |
| 2382 | }) |
| 2383 | |
| 2384 | it("copies starts, prioritizes distinct roots, and preserves sparse indexes", () => { |
| 2385 | const start = [0] |
| 2386 | const walkers = [Graph.dfs(graph, { start }), Graph.bfs(graph, { start }), Graph.dfsPostOrder(graph, { start })] |
| 2387 | start[0] = 3 |
| 2388 | assertIndices(walkers[0], [0, 1, 3, 2]) |
| 2389 | assertIndices(walkers[1], [0, 1, 2, 3]) |
| 2390 | assertIndices(walkers[2], [3, 1, 2, 0]) |
| 2391 | assertIndices(Graph.bfs(graph, { start: [0, 0, 2, 2] }), [0, 2, 1, 3]) |
| 2392 | |
| 2393 | const sparse = Graph.fromSnapshot({ |
| 2394 | type: "directed", |
| 2395 | nodes: [{ index: 2, data: "A" }, { index: 5, data: "B" }, { index: 1_000_000, data: "C" }], |
| 2396 | edges: [{ index: 3, source: 2, target: 5, data: 1 }, { |
| 2397 | index: 1_000_000, |
| 2398 | source: 5, |
| 2399 | target: 1_000_000, |
| 2400 | data: 2 |
| 2401 | }] |
| 2402 | }) |
| 2403 | assertIndices(Graph.bfs(sparse, { start: [2] }), [2, 5, 1_000_000]) |
| 2404 | assertIndices(Graph.dfsPostOrder(sparse, { start: [2] }), [1_000_000, 5, 2]) |
| 2405 | }) |
| 2406 | |
| 2407 | it("revalidates missing starts for fresh DFS, BFS, and postorder iterators", () => { |
| 2408 | const mutable = Graph.beginMutation(directed([0, 1], [[0, 1, 1]])) |
| 2409 | const walkers = [ |
| 2410 | Graph.indices(Graph.dfs(mutable, { start: [0] })), |
| 2411 | Graph.indices(Graph.bfs(mutable, { start: [0] })), |
| 2412 | Graph.indices(Graph.dfsPostOrder(mutable, { start: [0] })) |
| 2413 | ] |
| 2414 | Graph.removeNode(mutable, 0) |
| 2415 | for (const walker of walkers) assertGraphError(() => walker[Symbol.iterator](), "Node 0 does not exist") |
| 2416 | }) |
| 2417 | |
| 2418 | it("isolates active mutable traversal snapshots while fresh iterators see mutations", () => { |
| 2419 | const mutable = Graph.beginMutation(directed(["A", "B", "C"], [[0, 1, 1], [1, 2, 2]])) |
| 2420 | const walkers = [ |
| 2421 | Graph.indices(Graph.dfs(mutable, { start: [0] })), |
| 2422 | Graph.indices(Graph.bfs(mutable, { start: [0] })), |
| 2423 | Graph.indices(Graph.dfsPostOrder(mutable, { start: [0] })) |
| 2424 | ] |
| 2425 | const active = walkers.map((walker) => walker[Symbol.iterator]()) |
| 2426 | Graph.removeNode(mutable, 1) |
| 2427 | assert.deepStrictEqual(Array.from({ [Symbol.iterator]: () => active[0] }), [0, 1, 2]) |
| 2428 | assert.deepStrictEqual(Array.from({ [Symbol.iterator]: () => active[1] }), [0, 1, 2]) |
| 2429 | assert.deepStrictEqual(Array.from({ [Symbol.iterator]: () => active[2] }), [2, 1, 0]) |
| 2430 | for (const walker of walkers) assert.deepStrictEqual(Array.from(walker), [0]) |
| 2431 | }) |
| 2432 | |
| 2433 | it("topologically sorts with prioritized initials and validates fresh mutable state", () => { |
| 2434 | const graph = directed(["A", "B", "C", "D"], [[0, 1, 1], [2, 3, 1]]) |
| 2435 | assertIndices(Graph.topo(graph, { initials: [2] }), [2, 0, 3, 1]) |
| 2436 | |
| 2437 | const mutable = Graph.beginMutation(directed<string, number>(["A", "B"], [])) |
| 2438 | const walker = Graph.topo(mutable) |
| 2439 | assertIndices(walker, [0, 1]) |
| 2440 | Graph.addEdge(mutable, 0, 1, 1) |
| 2441 | Graph.addEdge(mutable, 1, 0, 2) |
| 2442 | assertGraphError(() => Array.from(Graph.indices(walker)), "Cannot perform topological sort on cyclic graph") |
| 2443 | }) |
| 2444 | |
| 2445 | it("isolates active mutable topological snapshots while fresh iterators see mutations", () => { |
| 2446 | const mutable = Graph.beginMutation(directed([0, 1, 2], [[0, 1, 1], [1, 2, 1]])) |
| 2447 | const walker = Graph.indices(Graph.topo(mutable)) |
| 2448 | const active = walker[Symbol.iterator]() |
| 2449 | Graph.removeNode(mutable, 1) |
| 2450 | |
| 2451 | assert.deepStrictEqual(Array.from({ [Symbol.iterator]: () => active }), [0, 1, 2]) |
| 2452 | assert.deepStrictEqual(Array.from(walker), [0, 2]) |
| 2453 | }) |
| 2454 | |
| 2455 | it("rejects invalid topological graphs and initials", () => { |
| 2456 | assertGraphError( |
| 2457 | () => Graph.topo(Graph.undirected() as unknown as Graph.DirectedGraph<never, never>), |
| 2458 | "Cannot perform topological sort on undirected graph" |
| 2459 | ) |
| 2460 | assertGraphError( |
| 2461 | () => Graph.topo(directed([0, 1], [[0, 1, 1], [1, 0, 1]])), |
| 2462 | "Cannot perform topological sort on cyclic graph" |
| 2463 | ) |
| 2464 | const graph = directed([0, 1], [[0, 1, 1]]) |
| 2465 | assertGraphError(() => Array.from(Graph.topo(graph, { initials: [1] })), "Initial node 1 has incoming edges") |
| 2466 | assertGraphError(() => Graph.topo(graph, { initials: [2] }), "Node 2 does not exist") |
| 2467 | }) |
| 2468 | |
| 2469 | it("keeps nodes, edges, and externals live on mutable graphs", () => { |
| 2470 | const mutable = Graph.beginMutation(directed(["A", "B"], [[0, 1, 1]])) |
| 2471 | const nodes = Graph.indices(Graph.nodes(mutable))[Symbol.iterator]() |
| 2472 | const edges = Graph.indices(Graph.edges(mutable))[Symbol.iterator]() |
| 2473 | const externals = Graph.indices(Graph.externals(mutable))[Symbol.iterator]() |
| 2474 | assert.strictEqual(nodes.next().value, 0) |
| 2475 | assert.strictEqual(edges.next().value, 0) |
| 2476 | assert.strictEqual(externals.next().value, 1) |
| 2477 | |
| 2478 | Graph.addNode(mutable, "C") |
| 2479 | Graph.addEdge(mutable, 1, 2, 2) |
| 2480 | assert.deepStrictEqual(Array.from({ [Symbol.iterator]: () => nodes }), [1, 2]) |
| 2481 | assert.deepStrictEqual(Array.from({ [Symbol.iterator]: () => edges }), [1]) |
| 2482 | assert.deepStrictEqual(Array.from({ [Symbol.iterator]: () => externals }), [2]) |
| 2483 | }) |
| 2484 | |
| 2485 | it("selects outgoing sinks and incoming sources", () => { |
| 2486 | const graph = directed(["source", "middle", "sink", "isolated"], [[0, 1, 1], [1, 2, 2]]) |
| 2487 | assertIndices(Graph.externals(graph), [2, 3]) |
| 2488 | assertIndices(Graph.externals(graph, { direction: "outgoing" }), [2, 3]) |
| 2489 | assertIndices(Graph.externals(graph, { direction: "incoming" }), [0, 3]) |
| 2490 | }) |
| 2491 | }) |
| 2492 | |
| 2493 | describe("Walker", () => { |
| 2494 | it("projects representative walkers through indices, values, entries, and visit", () => { |
| 2495 | const walker = new Graph.Walker<number, string>(function*(visit) { |
| 2496 | yield visit(2, "A") |
| 2497 | yield visit(5, "B") |
| 2498 | }) |
| 2499 | |
| 2500 | assert.deepStrictEqual(Array.from(Graph.indices(walker)), [2, 5]) |
| 2501 | assert.deepStrictEqual(Array.from(Graph.values(walker)), ["A", "B"]) |
| 2502 | assert.deepStrictEqual(Array.from(Graph.entries(walker)), [[2, "A"], [5, "B"]]) |
| 2503 | assert.deepStrictEqual(Array.from(walker.visit((index, value) => `${index}:${value}`)), ["2:A", "5:B"]) |
| 2504 | }) |
| 2505 | |
| 2506 | it("is repeatable and gives independent iterators fresh state", () => { |
| 2507 | const walker = new Graph.Walker<number, string>(function*(visit) { |
| 2508 | yield visit(0, "A") |
| 2509 | yield visit(1, "B") |
| 2510 | }) |
| 2511 | assert.deepStrictEqual(Array.from(walker), [[0, "A"], [1, "B"]]) |
| 2512 | assert.deepStrictEqual(Array.from(walker), [[0, "A"], [1, "B"]]) |
| 2513 | |
| 2514 | const left = walker[Symbol.iterator]() |
| 2515 | const right = walker[Symbol.iterator]() |
| 2516 | assert.deepStrictEqual(left.next(), { done: false, value: [0, "A"] }) |
| 2517 | assert.deepStrictEqual(right.next(), { done: false, value: [0, "A"] }) |
| 2518 | assert.deepStrictEqual(left.next(), { done: false, value: [1, "B"] }) |
| 2519 | assert.deepStrictEqual(right.next(), { done: false, value: [1, "B"] }) |
| 2520 | }) |
| 2521 | |
| 2522 | it("preserves receivers supplied by iterable iterator methods", () => { |
| 2523 | const walker = new Graph.Walker<number, string>((visit) => new Set([visit(0, "A"), visit(1, "B")])) |
| 2524 | assert.deepStrictEqual(Array.from(walker), [[0, "A"], [1, "B"]]) |
| 2525 | }) |
| 2526 | }) |
| 2527 | }) |