3506 lines
124 KiB
TypeScript
3506 lines
124 KiB
TypeScript
import { assertNone, assertSome, strictEqual } from "@effect/vitest/utils"
|
|
import { Equal, Graph, Hash, Option } from "effect"
|
|
import { describe, expect, it } from "vitest"
|
|
|
|
const assertSomeEdge = <E>(edge: Option.Option<Graph.Edge<E>>): Graph.Edge<E> => {
|
|
if (Option.isNone(edge)) {
|
|
throw new Error("Expected edge to be present")
|
|
}
|
|
return edge.value
|
|
}
|
|
|
|
const makeReversedUndirectedPath = () =>
|
|
Graph.undirected<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
Graph.addEdge(mutable, c, b, 1)
|
|
})
|
|
|
|
describe("Graph", () => {
|
|
describe("constructors", () => {
|
|
it("should create empty directed graph", () => {
|
|
const graph = Graph.directed<string, number>()
|
|
|
|
expect(graph.type).toBe("directed")
|
|
expect(Graph.nodeCount(graph)).toBe(0)
|
|
expect(Graph.edgeCount(graph)).toBe(0)
|
|
})
|
|
|
|
it("should create empty undirected graph", () => {
|
|
const graph = Graph.undirected<string, number>()
|
|
|
|
expect(graph.type).toBe("undirected")
|
|
expect(Graph.nodeCount(graph)).toBe(0)
|
|
expect(Graph.edgeCount(graph)).toBe(0)
|
|
})
|
|
})
|
|
|
|
it("toString", () => {
|
|
const graph = Graph.directed<undefined, number>((mutable) => {
|
|
const nodeA = Graph.addNode(mutable, undefined)
|
|
const nodeB = Graph.addNode(mutable, undefined)
|
|
Graph.addEdge(mutable, nodeA, nodeB, 1)
|
|
})
|
|
strictEqual(String(graph), "Graph(directed, 2, 1)")
|
|
})
|
|
|
|
describe("isGraph", () => {
|
|
it("should return true for graph instances", () => {
|
|
const directedGraph = Graph.directed<string, number>()
|
|
const undirectedGraph = Graph.undirected<string, number>()
|
|
|
|
expect(Graph.isGraph(directedGraph)).toBe(true)
|
|
expect(Graph.isGraph(undirectedGraph)).toBe(true)
|
|
})
|
|
|
|
it("should return false for non-graph values", () => {
|
|
expect(Graph.isGraph({})).toBe(false)
|
|
expect(Graph.isGraph(null)).toBe(false)
|
|
expect(Graph.isGraph(undefined)).toBe(false)
|
|
expect(Graph.isGraph("string")).toBe(false)
|
|
expect(Graph.isGraph(42)).toBe(false)
|
|
expect(Graph.isGraph([])).toBe(false)
|
|
})
|
|
|
|
it("should be iterable using for...of syntax", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
Graph.addNode(mutable, "Node A")
|
|
Graph.addNode(mutable, "Node B")
|
|
Graph.addNode(mutable, "Node C")
|
|
})
|
|
|
|
const collected: Array<readonly [number, string]> = []
|
|
for (const entry of graph) {
|
|
collected.push(entry)
|
|
}
|
|
|
|
expect(collected).toHaveLength(3)
|
|
expect(collected).toEqual([
|
|
[0, "Node A"],
|
|
[1, "Node B"],
|
|
[2, "Node C"]
|
|
])
|
|
})
|
|
|
|
it("should support manual iterator operations", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
Graph.addNode(mutable, "Node A")
|
|
Graph.addNode(mutable, "Node B")
|
|
})
|
|
|
|
const iterator = graph[Symbol.iterator]()
|
|
const first = iterator.next()
|
|
const second = iterator.next()
|
|
const third = iterator.next()
|
|
|
|
expect(first.done).toBe(false)
|
|
expect(first.value).toEqual([0, "Node A"])
|
|
expect(second.done).toBe(false)
|
|
expect(second.value).toEqual([1, "Node B"])
|
|
expect(third.done).toBe(true)
|
|
})
|
|
})
|
|
|
|
describe("undefined data handling", () => {
|
|
describe("undefined node data", () => {
|
|
it("should allow adding nodes with undefined data", () => {
|
|
const graph = Graph.directed<undefined, number>((mutable) => {
|
|
const nodeA = Graph.addNode(mutable, undefined)
|
|
const nodeB = Graph.addNode(mutable, undefined)
|
|
Graph.addEdge(mutable, nodeA, nodeB, 1)
|
|
})
|
|
|
|
expect(Graph.nodeCount(graph)).toBe(2)
|
|
expect(Graph.edgeCount(graph)).toBe(1)
|
|
expect(Graph.getNode(graph, 0)).toEqual(Option.some(undefined))
|
|
expect(Graph.getNode(graph, 1)).toEqual(Option.some(undefined))
|
|
})
|
|
|
|
it("should correctly update nodes with undefined data", () => {
|
|
const graph = Graph.directed<undefined | string, number>((mutable) => {
|
|
Graph.addNode(mutable, undefined)
|
|
Graph.addNode(mutable, "defined")
|
|
})
|
|
|
|
const updated = Graph.mutate(graph, (mutable) => {
|
|
Graph.updateNode(mutable, 0, () => "now defined")
|
|
Graph.updateNode(mutable, 1, () => undefined)
|
|
})
|
|
|
|
expect(Graph.getNode(updated, 0)).toEqual(Option.some("now defined"))
|
|
expect(Graph.getNode(updated, 1)).toEqual(Option.some(undefined))
|
|
})
|
|
|
|
it("should correctly compare graphs with undefined node data", () => {
|
|
const graph1 = Graph.directed<undefined, number>((mutable) => {
|
|
Graph.addNode(mutable, undefined)
|
|
Graph.addNode(mutable, undefined)
|
|
})
|
|
|
|
const graph2 = Graph.directed<undefined, number>((mutable) => {
|
|
Graph.addNode(mutable, undefined)
|
|
Graph.addNode(mutable, undefined)
|
|
})
|
|
|
|
expect(Equal.equals(graph1, graph2)).toBe(true)
|
|
})
|
|
|
|
it("should find nodes with undefined data using predicates", () => {
|
|
const graph = Graph.directed<undefined | string, number>((mutable) => {
|
|
Graph.addNode(mutable, undefined)
|
|
Graph.addNode(mutable, "defined")
|
|
Graph.addNode(mutable, undefined)
|
|
})
|
|
|
|
const undefinedNode = Graph.findNode(graph, (data) => data === undefined)
|
|
const undefinedNodes = Graph.findNodes(graph, (data) => data === undefined)
|
|
|
|
expect(undefinedNode).toEqual(Option.some(0))
|
|
expect(undefinedNodes).toEqual([0, 2])
|
|
})
|
|
|
|
it("should iterate correctly over graphs with undefined node data", () => {
|
|
const graph = Graph.directed<undefined, number>((mutable) => {
|
|
Graph.addNode(mutable, undefined)
|
|
Graph.addNode(mutable, undefined)
|
|
})
|
|
|
|
const collected: Array<readonly [number, undefined]> = []
|
|
for (const entry of graph) {
|
|
collected.push(entry)
|
|
}
|
|
|
|
expect(collected).toEqual([
|
|
[0, undefined],
|
|
[1, undefined]
|
|
])
|
|
})
|
|
})
|
|
|
|
describe("undefined edge data", () => {
|
|
it("should allow adding edges with undefined data", () => {
|
|
const graph = Graph.directed<string, undefined>((mutable) => {
|
|
const nodeA = Graph.addNode(mutable, "A")
|
|
const nodeB = Graph.addNode(mutable, "B")
|
|
Graph.addEdge(mutable, nodeA, nodeB, undefined)
|
|
})
|
|
|
|
expect(Graph.edgeCount(graph)).toBe(1)
|
|
expect(Graph.getEdge(graph, 0)).toEqual(Option.some(new Graph.Edge({ source: 0, target: 1, data: undefined })))
|
|
})
|
|
|
|
it("should correctly update edges with undefined data", () => {
|
|
const graph = Graph.directed<string, undefined | number>((mutable) => {
|
|
const nodeA = Graph.addNode(mutable, "A")
|
|
const nodeB = Graph.addNode(mutable, "B")
|
|
Graph.addEdge(mutable, nodeA, nodeB, undefined)
|
|
Graph.addEdge(mutable, nodeB, nodeA, 42)
|
|
})
|
|
|
|
const updated = Graph.mutate(graph, (mutable) => {
|
|
Graph.updateEdge(mutable, 0, () => 100)
|
|
Graph.updateEdge(mutable, 1, () => undefined)
|
|
})
|
|
|
|
const edge0 = Graph.getEdge(updated, 0)
|
|
const edge1 = Graph.getEdge(updated, 1)
|
|
|
|
expect(edge0).toEqual(Option.some(new Graph.Edge({ source: 0, target: 1, data: 100 })))
|
|
expect(edge1).toEqual(Option.some(new Graph.Edge({ source: 1, target: 0, data: undefined })))
|
|
})
|
|
|
|
it("should correctly compare graphs with undefined edge data", () => {
|
|
const graph1 = Graph.directed<string, undefined>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
Graph.addEdge(mutable, a, b, undefined)
|
|
})
|
|
|
|
const graph2 = Graph.directed<string, undefined>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
Graph.addEdge(mutable, a, b, undefined)
|
|
})
|
|
|
|
expect(Equal.equals(graph1, graph2)).toBe(true)
|
|
})
|
|
|
|
it("should find edges with undefined data using predicates", () => {
|
|
const graph = Graph.directed<string, undefined | number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, undefined)
|
|
Graph.addEdge(mutable, b, c, 42)
|
|
Graph.addEdge(mutable, c, a, undefined)
|
|
})
|
|
|
|
const undefinedEdge = Graph.findEdge(graph, (data) => data === undefined)
|
|
const undefinedEdges = Graph.findEdges(graph, (data) => data === undefined)
|
|
|
|
expect(undefinedEdge).toEqual(Option.some(0))
|
|
expect(undefinedEdges).toEqual([0, 2])
|
|
})
|
|
|
|
it("should produce consistent hashes for graphs with undefined edge data", () => {
|
|
const graph1 = Graph.directed<string, undefined | number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, undefined)
|
|
Graph.addEdge(mutable, b, c, 42)
|
|
})
|
|
|
|
const graph2 = Graph.directed<string, undefined | number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, undefined)
|
|
Graph.addEdge(mutable, b, c, 42)
|
|
})
|
|
|
|
// Graphs with identical structure should have the same hash
|
|
expect(Hash.hash(graph1)).toBe(Hash.hash(graph2))
|
|
|
|
// Graph with different edge data should have different hash
|
|
const graph3 = Graph.directed<string, undefined | number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, 100) // Different data
|
|
Graph.addEdge(mutable, b, c, 42)
|
|
})
|
|
|
|
expect(Hash.hash(graph1)).not.toBe(Hash.hash(graph3))
|
|
})
|
|
|
|
it("should correctly handle Equal.equals with graphs containing undefined edge data", () => {
|
|
const graph1 = Graph.directed<string, undefined | number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
Graph.addEdge(mutable, a, b, undefined)
|
|
})
|
|
|
|
const graph2 = Graph.directed<string, undefined | number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
Graph.addEdge(mutable, a, b, undefined)
|
|
})
|
|
|
|
const graph3 = Graph.directed<string, undefined | number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
Graph.addEdge(mutable, a, b, 42)
|
|
})
|
|
|
|
// Equal graphs with undefined edge data should be equal
|
|
expect(Equal.equals(graph1, graph2)).toBe(true)
|
|
|
|
// Graphs with different edge data should not be equal
|
|
expect(Equal.equals(graph1, graph3)).toBe(false)
|
|
})
|
|
})
|
|
|
|
describe("mixed undefined scenarios", () => {
|
|
it("should handle graphs with both undefined nodes and edges", () => {
|
|
const graph = Graph.directed<undefined, undefined>((mutable) => {
|
|
const nodeA = Graph.addNode(mutable, undefined)
|
|
const nodeB = Graph.addNode(mutable, undefined)
|
|
Graph.addEdge(mutable, nodeA, nodeB, undefined)
|
|
})
|
|
|
|
expect(Graph.nodeCount(graph)).toBe(2)
|
|
expect(Graph.edgeCount(graph)).toBe(1)
|
|
expect(Graph.getNode(graph, 0)).toEqual(Option.some(undefined))
|
|
expect(Graph.getEdge(graph, 0)).toEqual(Option.some(new Graph.Edge({ source: 0, target: 1, data: undefined })))
|
|
})
|
|
|
|
it("should correctly handle graph operations with mixed undefined data", () => {
|
|
const graph = Graph.directed<undefined | string, undefined | number>((mutable) => {
|
|
const a = Graph.addNode(mutable, undefined)
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, undefined)
|
|
Graph.addEdge(mutable, a, b, undefined)
|
|
Graph.addEdge(mutable, b, c, 42)
|
|
Graph.addEdge(mutable, c, a, undefined)
|
|
})
|
|
|
|
// Test neighbors
|
|
const neighborsOfA = Graph.neighbors(graph, 0)
|
|
const neighborsOfB = Graph.neighbors(graph, 1)
|
|
|
|
expect(neighborsOfA).toEqual([1])
|
|
expect(neighborsOfB).toEqual([2])
|
|
|
|
// Test filtering
|
|
const nodesWithUndefined = Graph.findNodes(graph, (data) => data === undefined)
|
|
const edgesWithUndefined = Graph.findEdges(graph, (data) => data === undefined)
|
|
|
|
expect(nodesWithUndefined).toEqual([0, 2])
|
|
expect(edgesWithUndefined).toEqual([0, 2])
|
|
})
|
|
})
|
|
})
|
|
|
|
describe("beginMutation", () => {
|
|
it("should create a mutable graph from an immutable graph", () => {
|
|
const graph = Graph.directed<string, number>()
|
|
const mutable = Graph.beginMutation(graph)
|
|
|
|
expect(mutable.type).toBe("directed")
|
|
expect(Graph.nodeCount(mutable)).toBe(Graph.nodeCount(graph))
|
|
expect(Graph.edgeCount(mutable)).toBe(Graph.edgeCount(graph))
|
|
})
|
|
})
|
|
|
|
describe("endMutation", () => {
|
|
it("should convert a mutable graph back to immutable", () => {
|
|
const graph = Graph.directed<string, number>()
|
|
const mutable = Graph.beginMutation(graph)
|
|
const result = Graph.endMutation(mutable)
|
|
|
|
expect(result.type).toBe("directed")
|
|
expect(Graph.nodeCount(result)).toBe(Graph.nodeCount(mutable))
|
|
expect(Graph.edgeCount(result)).toBe(Graph.edgeCount(mutable))
|
|
})
|
|
})
|
|
|
|
describe("mutate", () => {
|
|
it("should create a new graph instance", () => {
|
|
const graph = Graph.directed<string, number>()
|
|
|
|
const result = Graph.mutate(graph, () => {
|
|
// No mutations performed
|
|
})
|
|
|
|
expect(result).not.toBe(graph)
|
|
expect(Equal.equals(result, graph)).toBe(true) // Structural equality
|
|
})
|
|
|
|
it("should handle empty mutation function", () => {
|
|
const graph = Graph.directed<string, number>()
|
|
|
|
const result = Graph.mutate(graph, () => {
|
|
// Do nothing
|
|
})
|
|
|
|
expect(Graph.nodeCount(result)).toBe(0)
|
|
expect(Graph.edgeCount(result)).toBe(0)
|
|
})
|
|
})
|
|
|
|
describe("addNode", () => {
|
|
it("should add a node to a mutable graph and return its index", () => {
|
|
const graph = Graph.directed<string, number>()
|
|
let nodeIndex: Graph.NodeIndex
|
|
|
|
const result = Graph.mutate(graph, (mutable) => {
|
|
nodeIndex = Graph.addNode(mutable, "Node A")
|
|
})
|
|
|
|
expect(Graph.nodeCount(result)).toBe(1)
|
|
expect(Graph.getNode(result, nodeIndex!)).toEqual(Option.some("Node A"))
|
|
})
|
|
})
|
|
|
|
describe("getNode", () => {
|
|
it("should return the node data for existing nodes", () => {
|
|
let nodeA: Graph.NodeIndex
|
|
let nodeB: Graph.NodeIndex
|
|
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
nodeA = Graph.addNode(mutable, "Node A")
|
|
nodeB = Graph.addNode(mutable, "Node B")
|
|
})
|
|
|
|
expect(Graph.getNode(graph, nodeA!)).toEqual(Option.some("Node A"))
|
|
expect(Graph.getNode(graph, nodeB!)).toEqual(Option.some("Node B"))
|
|
})
|
|
|
|
it("should return None for non-existent nodes", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
Graph.addNode(mutable, "Node A")
|
|
})
|
|
|
|
const nonExistent = Graph.getNode(graph, 999)
|
|
expect(Option.isNone(nonExistent)).toBe(true)
|
|
})
|
|
})
|
|
|
|
describe("hasNode", () => {
|
|
it("should return true for existing nodes", () => {
|
|
let nodeA: Graph.NodeIndex
|
|
let nodeB: Graph.NodeIndex
|
|
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
nodeA = Graph.addNode(mutable, "Node A")
|
|
nodeB = Graph.addNode(mutable, "Node B")
|
|
})
|
|
|
|
expect(Graph.hasNode(graph, nodeA!)).toBe(true)
|
|
expect(Graph.hasNode(graph, nodeB!)).toBe(true)
|
|
})
|
|
|
|
it("should return false for non-existent nodes", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
Graph.addNode(mutable, "Node A")
|
|
})
|
|
|
|
expect(Graph.hasNode(graph, 999)).toBe(false)
|
|
expect(Graph.hasNode(graph, -1)).toBe(false)
|
|
})
|
|
})
|
|
|
|
describe("nodeCount", () => {
|
|
it("should return 0 for empty graph", () => {
|
|
const graph = Graph.directed<string, number>()
|
|
expect(Graph.nodeCount(graph)).toBe(0)
|
|
})
|
|
|
|
it("should return correct count after adding nodes", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
expect(Graph.nodeCount(mutable)).toBe(0)
|
|
Graph.addNode(mutable, "Node A")
|
|
expect(Graph.nodeCount(mutable)).toBe(1)
|
|
Graph.addNode(mutable, "Node B")
|
|
expect(Graph.nodeCount(mutable)).toBe(2)
|
|
Graph.addNode(mutable, "Node C")
|
|
expect(Graph.nodeCount(mutable)).toBe(3)
|
|
})
|
|
|
|
expect(Graph.nodeCount(graph)).toBe(3)
|
|
})
|
|
})
|
|
|
|
describe("findNode", () => {
|
|
it("should find node by predicate", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
Graph.addNode(mutable, "Node A")
|
|
Graph.addNode(mutable, "Node B")
|
|
Graph.addNode(mutable, "Node C")
|
|
})
|
|
|
|
const result = Graph.findNode(graph, (data) => data === "Node B")
|
|
expect(result).toEqual(Option.some(1))
|
|
})
|
|
|
|
it("should return None when no node matches", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
Graph.addNode(mutable, "Node A")
|
|
Graph.addNode(mutable, "Node B")
|
|
})
|
|
|
|
const result = Graph.findNode(graph, (data) => data === "Node C")
|
|
expect(result).toEqual(Option.none())
|
|
})
|
|
|
|
it("should find first matching node when multiple match", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
Graph.addNode(mutable, "Start A")
|
|
Graph.addNode(mutable, "Start B")
|
|
Graph.addNode(mutable, "Start C")
|
|
})
|
|
|
|
const result = Graph.findNode(graph, (data) => data.startsWith("Start"))
|
|
expect(result).toEqual(Option.some(0))
|
|
})
|
|
})
|
|
|
|
describe("findNodes", () => {
|
|
it("should find all matching nodes", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
Graph.addNode(mutable, "Start A")
|
|
Graph.addNode(mutable, "Node B")
|
|
Graph.addNode(mutable, "Start C")
|
|
Graph.addNode(mutable, "Start D")
|
|
})
|
|
|
|
const result = Graph.findNodes(graph, (data) => data.startsWith("Start"))
|
|
expect(result).toEqual([0, 2, 3])
|
|
})
|
|
})
|
|
|
|
describe("findEdge", () => {
|
|
it("should find edge by predicate", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const nodeA = Graph.addNode(mutable, "Node A")
|
|
const nodeB = Graph.addNode(mutable, "Node B")
|
|
const nodeC = Graph.addNode(mutable, "Node C")
|
|
Graph.addEdge(mutable, nodeA, nodeB, 10)
|
|
Graph.addEdge(mutable, nodeB, nodeC, 20)
|
|
})
|
|
|
|
const result = Graph.findEdge(graph, (data) => data === 20)
|
|
expect(result).toEqual(Option.some(1))
|
|
})
|
|
|
|
it("should return None when no edge matches", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const nodeA = Graph.addNode(mutable, "Node A")
|
|
const nodeB = Graph.addNode(mutable, "Node B")
|
|
Graph.addEdge(mutable, nodeA, nodeB, 10)
|
|
})
|
|
|
|
const result = Graph.findEdge(graph, (data) => data === 99)
|
|
expect(result).toEqual(Option.none())
|
|
})
|
|
|
|
it("should find first matching edge when multiple match", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const nodeA = Graph.addNode(mutable, "Node A")
|
|
const nodeB = Graph.addNode(mutable, "Node B")
|
|
const nodeC = Graph.addNode(mutable, "Node C")
|
|
Graph.addEdge(mutable, nodeA, nodeB, 15)
|
|
Graph.addEdge(mutable, nodeB, nodeC, 25)
|
|
Graph.addEdge(mutable, nodeC, nodeA, 35)
|
|
})
|
|
|
|
const result = Graph.findEdge(graph, (data) => data > 20)
|
|
expect(result).toEqual(Option.some(1))
|
|
})
|
|
})
|
|
|
|
describe("findEdges", () => {
|
|
it("should find all matching edges", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const nodeA = Graph.addNode(mutable, "Node A")
|
|
const nodeB = Graph.addNode(mutable, "Node B")
|
|
const nodeC = Graph.addNode(mutable, "Node C")
|
|
Graph.addEdge(mutable, nodeA, nodeB, 10)
|
|
Graph.addEdge(mutable, nodeB, nodeC, 20)
|
|
Graph.addEdge(mutable, nodeC, nodeA, 30)
|
|
Graph.addEdge(mutable, nodeA, nodeC, 25)
|
|
})
|
|
|
|
const result = Graph.findEdges(graph, (data) => data >= 20)
|
|
expect(result).toEqual([1, 2, 3])
|
|
})
|
|
})
|
|
|
|
describe("updateNode", () => {
|
|
it("should update node data", () => {
|
|
const updated = Graph.directed<string, number>((mutable) => {
|
|
Graph.addNode(mutable, "Node A")
|
|
Graph.addNode(mutable, "Node B")
|
|
Graph.updateNode(mutable, 0, (data) => data.toUpperCase())
|
|
})
|
|
|
|
const nodeData = Graph.getNode(updated, 0)
|
|
assertSome(nodeData, "NODE A")
|
|
})
|
|
|
|
it("should do nothing if node doesn't exist", () => {
|
|
let nodeA: Graph.NodeIndex
|
|
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
nodeA = Graph.addNode(mutable, "Node A")
|
|
Graph.updateNode(mutable, 999, (data) => data.toUpperCase())
|
|
})
|
|
|
|
// Original node should be unchanged
|
|
const nodeData = Graph.getNode(graph, nodeA!)
|
|
assertSome(nodeData, "Node A")
|
|
})
|
|
})
|
|
|
|
describe("updateEdge", () => {
|
|
it("should update edge data", () => {
|
|
const result = Graph.mutate(Graph.directed<string, number>(), (mutable) => {
|
|
const nodeA = Graph.addNode(mutable, "Node A")
|
|
const nodeB = Graph.addNode(mutable, "Node B")
|
|
const edgeIndex = Graph.addEdge(mutable, nodeA, nodeB, 10)
|
|
Graph.updateEdge(mutable, edgeIndex, (data) => data * 2)
|
|
})
|
|
|
|
const edge = Graph.getEdge(result, 0)
|
|
assertSome(edge, new Graph.Edge({ source: 0, target: 1, data: 20 }))
|
|
})
|
|
|
|
it("should do nothing if edge doesn't exist", () => {
|
|
Graph.mutate(Graph.directed<string, number>(), (mutable) => {
|
|
const nodeA = Graph.addNode(mutable, "Node A")
|
|
const nodeB = Graph.addNode(mutable, "Node B")
|
|
const edgeIndex = Graph.addEdge(mutable, nodeA, nodeB, 10)
|
|
|
|
// Try to update non-existent edge
|
|
Graph.updateEdge(mutable, 999, (data) => data * 2)
|
|
|
|
// Original edge should be unchanged
|
|
const edge = Graph.getEdge(mutable, edgeIndex)
|
|
assertSome(edge, new Graph.Edge({ source: 0, target: 1, data: 10 }))
|
|
})
|
|
})
|
|
})
|
|
|
|
describe("mapNodes", () => {
|
|
it("should transform all node data", () => {
|
|
let nodeA: Graph.NodeIndex
|
|
let nodeB: Graph.NodeIndex
|
|
let nodeC: Graph.NodeIndex
|
|
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
nodeA = Graph.addNode(mutable, "node a")
|
|
nodeB = Graph.addNode(mutable, "node b")
|
|
nodeC = Graph.addNode(mutable, "node c")
|
|
Graph.mapNodes(mutable, (data) => data.toUpperCase())
|
|
})
|
|
|
|
expect(Graph.getNode(graph, nodeA!)).toEqual(Option.some("NODE A"))
|
|
expect(Graph.getNode(graph, nodeB!)).toEqual(Option.some("NODE B"))
|
|
expect(Graph.getNode(graph, nodeC!)).toEqual(Option.some("NODE C"))
|
|
})
|
|
|
|
it("should apply transformation to all nodes", () => {
|
|
let firstNode: Graph.NodeIndex
|
|
let secondNode: Graph.NodeIndex
|
|
let thirdNode: Graph.NodeIndex
|
|
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
firstNode = Graph.addNode(mutable, "first")
|
|
secondNode = Graph.addNode(mutable, "second")
|
|
thirdNode = Graph.addNode(mutable, "third")
|
|
Graph.mapNodes(mutable, (data) => data + " (transformed)")
|
|
})
|
|
|
|
const node0 = Graph.getNode(graph, firstNode!)
|
|
const node1 = Graph.getNode(graph, secondNode!)
|
|
const node2 = Graph.getNode(graph, thirdNode!)
|
|
|
|
assertSome(node0, "first (transformed)")
|
|
assertSome(node1, "second (transformed)")
|
|
assertSome(node2, "third (transformed)")
|
|
})
|
|
|
|
it("should modify graph in place during construction", () => {
|
|
let originalNode: Graph.NodeIndex
|
|
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
originalNode = Graph.addNode(mutable, "original")
|
|
// Before transformation
|
|
const beforeData = Graph.getNode(mutable, originalNode!)
|
|
assertSome(beforeData, "original")
|
|
|
|
// Apply transformation
|
|
Graph.mapNodes(mutable, (data) => data.toUpperCase())
|
|
})
|
|
|
|
// After transformation
|
|
const afterData = Graph.getNode(graph, originalNode!)
|
|
assertSome(afterData, "ORIGINAL")
|
|
})
|
|
})
|
|
|
|
describe("mapEdges", () => {
|
|
it("should transform all edge data", () => {
|
|
let edgeAB: Graph.EdgeIndex
|
|
let edgeBC: Graph.EdgeIndex
|
|
let edgeCA: Graph.EdgeIndex
|
|
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
edgeAB = Graph.addEdge(mutable, a, b, 10)
|
|
edgeBC = Graph.addEdge(mutable, b, c, 20)
|
|
edgeCA = Graph.addEdge(mutable, c, a, 30)
|
|
Graph.mapEdges(mutable, (data) => data * 2)
|
|
})
|
|
|
|
const edge0 = Graph.getEdge(graph, edgeAB!)
|
|
const edge1 = Graph.getEdge(graph, edgeBC!)
|
|
const edge2 = Graph.getEdge(graph, edgeCA!)
|
|
|
|
expect(assertSomeEdge(edge0).data).toBe(20)
|
|
expect(assertSomeEdge(edge1).data).toBe(40)
|
|
expect(assertSomeEdge(edge2).data).toBe(60)
|
|
})
|
|
|
|
it("should modify graph in place during construction", () => {
|
|
let edgeAB: Graph.EdgeIndex
|
|
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
edgeAB = Graph.addEdge(mutable, a, b, 10)
|
|
|
|
// Before transformation
|
|
const beforeData = Graph.getEdge(mutable, edgeAB!)
|
|
assertSome(beforeData, new Graph.Edge({ source: 0, target: 1, data: 10 }))
|
|
|
|
// Apply transformation
|
|
Graph.mapEdges(mutable, (data) => data * 5)
|
|
})
|
|
|
|
// After transformation
|
|
const afterData = Graph.getEdge(graph, edgeAB!)
|
|
expect(assertSomeEdge(afterData).data).toBe(50)
|
|
})
|
|
})
|
|
|
|
describe("reverse", () => {
|
|
it("should reverse all edge directions", () => {
|
|
let nodeA: Graph.NodeIndex
|
|
let nodeB: Graph.NodeIndex
|
|
let nodeC: Graph.NodeIndex
|
|
let edgeAB: Graph.EdgeIndex
|
|
let edgeBC: Graph.EdgeIndex
|
|
let edgeCA: Graph.EdgeIndex
|
|
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
nodeA = Graph.addNode(mutable, "A")
|
|
nodeB = Graph.addNode(mutable, "B")
|
|
nodeC = Graph.addNode(mutable, "C")
|
|
edgeAB = Graph.addEdge(mutable, nodeA, nodeB, 1) // A -> B
|
|
edgeBC = Graph.addEdge(mutable, nodeB, nodeC, 2) // B -> C
|
|
edgeCA = Graph.addEdge(mutable, nodeC, nodeA, 3) // C -> A
|
|
Graph.reverse(mutable) // Now B -> A, C -> B, A -> C
|
|
})
|
|
|
|
const edge0 = Graph.getEdge(graph, edgeAB!)
|
|
const edge1 = Graph.getEdge(graph, edgeBC!)
|
|
const edge2 = Graph.getEdge(graph, edgeCA!)
|
|
|
|
assertSome(edge0, new Graph.Edge({ source: nodeB!, target: nodeA!, data: 1 }))
|
|
assertSome(edge1, new Graph.Edge({ source: nodeC!, target: nodeB!, data: 2 }))
|
|
assertSome(edge2, new Graph.Edge({ source: nodeA!, target: nodeC!, data: 3 }))
|
|
})
|
|
|
|
it("should update adjacency lists correctly", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, 1) // A -> B
|
|
Graph.addEdge(mutable, a, c, 2) // A -> C
|
|
Graph.reverse(mutable) // Now B -> A, C -> A
|
|
})
|
|
|
|
// After reversal:
|
|
// - Node A should have no outgoing edges
|
|
// - Node B should have edge to A
|
|
// - Node C should have edge to A
|
|
|
|
const neighborsA = Graph.neighbors(graph, 0)
|
|
const neighborsB = Graph.neighbors(graph, 1)
|
|
const neighborsC = Graph.neighbors(graph, 2)
|
|
|
|
expect(Array.from(neighborsA)).toEqual([]) // A has no outgoing edges
|
|
expect(Array.from(neighborsB)).toEqual([0]) // B -> A
|
|
expect(Array.from(neighborsC)).toEqual([0]) // C -> A
|
|
})
|
|
|
|
it("should preserve adjacency lists when adding edges after reversal", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
Graph.reverse(mutable)
|
|
Graph.addEdge(mutable, a, b, 2)
|
|
})
|
|
|
|
expect(Graph.edgeCount(graph)).toBe(2)
|
|
expect(Graph.neighbors(graph, 0)).toEqual([1])
|
|
expect(Graph.hasEdge(graph, 0, 1)).toBe(true)
|
|
expect(Graph.hasEdge(graph, 1, 0)).toBe(true)
|
|
})
|
|
|
|
it("should be a no-op for undirected graphs", () => {
|
|
const graph = Graph.undirected<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
Graph.reverse(mutable)
|
|
})
|
|
|
|
expect(Graph.neighbors(graph, 0)).toEqual([1])
|
|
expect(Graph.neighbors(graph, 1)).toEqual([0])
|
|
expect(Graph.hasEdge(graph, 0, 1)).toBe(true)
|
|
expect(Graph.hasEdge(graph, 1, 0)).toBe(true)
|
|
})
|
|
})
|
|
|
|
describe("filterMapNodes", () => {
|
|
it("should filter and transform nodes", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
Graph.addNode(mutable, "active")
|
|
Graph.addNode(mutable, "inactive")
|
|
Graph.addNode(mutable, "active")
|
|
Graph.addNode(mutable, "pending")
|
|
|
|
// Keep only "active" nodes and transform to uppercase
|
|
Graph.filterMapNodes(mutable, (data) => data === "active" ? Option.some(data.toUpperCase()) : Option.none())
|
|
})
|
|
|
|
// Should only have 2 nodes remaining (the "active" ones)
|
|
expect(Graph.nodeCount(graph)).toBe(2)
|
|
|
|
// Check the remaining nodes have been transformed
|
|
const nodeData0 = Graph.getNode(graph, 0)
|
|
const nodeData2 = Graph.getNode(graph, 2)
|
|
|
|
expect(Option.isSome(nodeData0)).toBe(true)
|
|
expect(Option.isSome(nodeData2)).toBe(true)
|
|
|
|
if (Option.isSome(nodeData0) && Option.isSome(nodeData2)) {
|
|
expect(nodeData0.value).toBe("ACTIVE")
|
|
expect(nodeData2.value).toBe("ACTIVE")
|
|
}
|
|
|
|
// Filtered out nodes should not exist
|
|
expect(Option.isNone(Graph.getNode(graph, 1))).toBe(true)
|
|
expect(Option.isNone(Graph.getNode(graph, 3))).toBe(true)
|
|
})
|
|
|
|
it("should remove edges connected to filtered nodes", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "keep")
|
|
const b = Graph.addNode(mutable, "remove")
|
|
const c = Graph.addNode(mutable, "keep")
|
|
|
|
Graph.addEdge(mutable, a, b, 1) // keep -> remove
|
|
Graph.addEdge(mutable, b, c, 2) // remove -> keep
|
|
Graph.addEdge(mutable, a, c, 3) // keep -> keep
|
|
|
|
// Filter out "remove" nodes
|
|
Graph.filterMapNodes(mutable, (data) => data === "keep" ? Option.some(data) : Option.none())
|
|
})
|
|
|
|
// Should have 2 nodes and 1 edge remaining
|
|
expect(Graph.nodeCount(graph)).toBe(2)
|
|
expect(Graph.edgeCount(graph)).toBe(1)
|
|
|
|
// Only the keep -> keep edge should remain
|
|
const remainingEdge = Graph.getEdge(graph, 2)
|
|
assertSome(remainingEdge, new Graph.Edge({ source: 0, target: 2, data: 3 }))
|
|
|
|
// Edges involving removed node should be gone
|
|
expect(Graph.getEdge(graph, 0)).toEqual(Option.none())
|
|
expect(Graph.getEdge(graph, 1)).toEqual(Option.none())
|
|
})
|
|
|
|
it("should handle transformation without filtering", () => {
|
|
const graph = Graph.directed<number, string>((mutable) => {
|
|
Graph.addNode(mutable, 1)
|
|
Graph.addNode(mutable, 2)
|
|
Graph.addNode(mutable, 3)
|
|
|
|
// Transform all nodes by doubling them
|
|
Graph.filterMapNodes(mutable, (data) => Option.some(data * 2))
|
|
})
|
|
|
|
expect(Graph.nodeCount(graph)).toBe(3)
|
|
|
|
const node0 = Graph.getNode(graph, 0)
|
|
const node1 = Graph.getNode(graph, 1)
|
|
const node2 = Graph.getNode(graph, 2)
|
|
|
|
assertSome(node0, 2)
|
|
assertSome(node1, 4)
|
|
assertSome(node2, 6)
|
|
})
|
|
|
|
it("should handle filtering without transformation", () => {
|
|
const graph = Graph.directed<number, string>((mutable) => {
|
|
Graph.addNode(mutable, 1)
|
|
Graph.addNode(mutable, 2)
|
|
Graph.addNode(mutable, 3)
|
|
Graph.addNode(mutable, 4)
|
|
|
|
// Keep only even numbers
|
|
Graph.filterMapNodes(mutable, (data) => data % 2 === 0 ? Option.some(data) : Option.none())
|
|
})
|
|
|
|
expect(Graph.nodeCount(graph)).toBe(2)
|
|
|
|
const node1 = Graph.getNode(graph, 1)
|
|
const node3 = Graph.getNode(graph, 3)
|
|
|
|
assertSome(node1, 2)
|
|
assertSome(node3, 4)
|
|
|
|
// Odd numbers should be removed
|
|
assertNone(Graph.getNode(graph, 0))
|
|
assertNone(Graph.getNode(graph, 2))
|
|
})
|
|
})
|
|
|
|
describe("filterMapEdges", () => {
|
|
it("should filter and transform edges", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, 5) // Remove (< 10)
|
|
Graph.addEdge(mutable, b, c, 15) // Keep and double (30)
|
|
Graph.addEdge(mutable, c, a, 25) // Keep and double (50)
|
|
|
|
// Keep only edges with weight >= 10 and double their weight
|
|
Graph.filterMapEdges(mutable, (data) => data >= 10 ? Option.some(data * 2) : Option.none())
|
|
})
|
|
|
|
// Should have 2 edges remaining
|
|
expect(Graph.edgeCount(graph)).toBe(2)
|
|
expect(Graph.nodeCount(graph)).toBe(3) // All nodes should remain
|
|
|
|
// Check that remaining edges have been transformed
|
|
const edge1 = Graph.getEdge(graph, 1)
|
|
const edge2 = Graph.getEdge(graph, 2)
|
|
|
|
expect(assertSomeEdge(edge1).data).toBe(30) // 15 * 2
|
|
expect(assertSomeEdge(edge2).data).toBe(50) // 25 * 2
|
|
|
|
// Filtered out edge should not exist
|
|
expect(Graph.getEdge(graph, 0)).toEqual(Option.none())
|
|
})
|
|
|
|
it("should update adjacency lists when removing edges", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
|
|
Graph.addEdge(mutable, a, b, 1) // Keep
|
|
Graph.addEdge(mutable, a, c, 2) // Remove
|
|
Graph.addEdge(mutable, b, c, 3) // Keep
|
|
|
|
// Keep only odd numbers
|
|
Graph.filterMapEdges(mutable, (data) => data % 2 === 1 ? Option.some(data) : Option.none())
|
|
})
|
|
|
|
// Should have 2 edges remaining (1 and 3)
|
|
expect(Graph.edgeCount(graph)).toBe(2)
|
|
|
|
// Check adjacency: A should only connect to B now
|
|
const neighborsA = Array.from(Graph.neighbors(graph, 0))
|
|
expect(neighborsA).toEqual([1]) // A -> B only
|
|
|
|
// Check that B still connects to C
|
|
const neighborsB = Array.from(Graph.neighbors(graph, 1))
|
|
expect(neighborsB).toEqual([2]) // B -> C
|
|
|
|
// Check that C has no outgoing edges
|
|
const neighborsC = Array.from(Graph.neighbors(graph, 2))
|
|
expect(neighborsC).toEqual([]) // C has no outgoing edges
|
|
})
|
|
|
|
it("should handle transformation without filtering", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, 10)
|
|
Graph.addEdge(mutable, b, c, 20)
|
|
Graph.addEdge(mutable, c, a, 30)
|
|
|
|
// Transform all edges by adding 100
|
|
Graph.filterMapEdges(mutable, (data) => Option.some(data + 100))
|
|
})
|
|
|
|
expect(Graph.edgeCount(graph)).toBe(3)
|
|
|
|
const edge0 = Graph.getEdge(graph, 0)
|
|
const edge1 = Graph.getEdge(graph, 1)
|
|
const edge2 = Graph.getEdge(graph, 2)
|
|
|
|
expect(assertSomeEdge(edge0).data).toBe(110)
|
|
expect(assertSomeEdge(edge1).data).toBe(120)
|
|
expect(assertSomeEdge(edge2).data).toBe(130)
|
|
})
|
|
|
|
it("should handle filtering without transformation", () => {
|
|
const graph = Graph.directed<string, { weight: number; type: string }>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, { weight: 10, type: "primary" })
|
|
Graph.addEdge(mutable, b, c, { weight: 20, type: "secondary" })
|
|
Graph.addEdge(mutable, c, a, { weight: 30, type: "primary" })
|
|
|
|
// Keep only "primary" edges
|
|
Graph.filterMapEdges(mutable, (data) => data.type === "primary" ? Option.some(data) : Option.none())
|
|
})
|
|
|
|
expect(Graph.edgeCount(graph)).toBe(2)
|
|
|
|
const edge0 = Graph.getEdge(graph, 0)
|
|
const edge2 = Graph.getEdge(graph, 2)
|
|
|
|
expect(assertSomeEdge(edge0).data.type).toBe("primary")
|
|
expect(assertSomeEdge(edge2).data.type).toBe("primary")
|
|
|
|
// Secondary edge should be removed
|
|
expect(Graph.getEdge(graph, 1)).toEqual(Option.none())
|
|
})
|
|
})
|
|
|
|
describe("filterNodes", () => {
|
|
it("should filter nodes by predicate", () => {
|
|
let activeNode1: Graph.NodeIndex
|
|
let inactiveNode: Graph.NodeIndex
|
|
let activeNode2: Graph.NodeIndex
|
|
let pendingNode: Graph.NodeIndex
|
|
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
activeNode1 = Graph.addNode(mutable, "active")
|
|
inactiveNode = Graph.addNode(mutable, "inactive")
|
|
activeNode2 = Graph.addNode(mutable, "active")
|
|
pendingNode = Graph.addNode(mutable, "pending")
|
|
|
|
// Keep only "active" nodes
|
|
Graph.filterNodes(mutable, (data) => data === "active")
|
|
})
|
|
|
|
expect(Graph.nodeCount(graph)).toBe(2)
|
|
|
|
const node0 = Graph.getNode(graph, activeNode1!)
|
|
const node2 = Graph.getNode(graph, activeNode2!)
|
|
|
|
assertSome(node0, "active")
|
|
assertSome(node2, "active")
|
|
|
|
// Filtered out nodes should be removed
|
|
assertNone(Graph.getNode(graph, inactiveNode!))
|
|
assertNone(Graph.getNode(graph, pendingNode!))
|
|
})
|
|
|
|
it("should remove connected edges when filtering nodes", () => {
|
|
let edgeAB: Graph.EdgeIndex
|
|
let edgeBC: Graph.EdgeIndex
|
|
let edgeAC: Graph.EdgeIndex
|
|
|
|
const graph = Graph.directed<string, string>((mutable) => {
|
|
const a = Graph.addNode(mutable, "keep")
|
|
const b = Graph.addNode(mutable, "remove")
|
|
const c = Graph.addNode(mutable, "keep")
|
|
|
|
edgeAB = Graph.addEdge(mutable, a, b, "A-B")
|
|
edgeBC = Graph.addEdge(mutable, b, c, "B-C")
|
|
edgeAC = Graph.addEdge(mutable, a, c, "A-C")
|
|
|
|
// Remove node "remove"
|
|
Graph.filterNodes(mutable, (data) => data === "keep")
|
|
})
|
|
|
|
expect(Graph.nodeCount(graph)).toBe(2) // Only "keep" nodes remain
|
|
expect(Graph.edgeCount(graph)).toBe(1) // Only A-C edge remains
|
|
|
|
// Check remaining edge
|
|
const edge2 = Graph.getEdge(graph, edgeAC!)
|
|
assertSome(edge2, new Graph.Edge({ source: 0, target: 2, data: "A-C" }))
|
|
|
|
// Check removed edges
|
|
expect(Graph.getEdge(graph, edgeAB!)).toEqual(Option.none()) // A-B removed
|
|
expect(Graph.getEdge(graph, edgeBC!)).toEqual(Option.none()) // B-C removed
|
|
})
|
|
})
|
|
|
|
describe("filterEdges", () => {
|
|
it("should filter edges by predicate", () => {
|
|
let edgeAB: Graph.EdgeIndex
|
|
let edgeBC: Graph.EdgeIndex
|
|
let edgeCA: Graph.EdgeIndex
|
|
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
|
|
edgeAB = Graph.addEdge(mutable, a, b, 5)
|
|
edgeBC = Graph.addEdge(mutable, b, c, 15)
|
|
edgeCA = Graph.addEdge(mutable, c, a, 25)
|
|
|
|
// Keep only edges with weight >= 10
|
|
Graph.filterEdges(mutable, (data) => data >= 10)
|
|
})
|
|
|
|
expect(Graph.nodeCount(graph)).toBe(3) // All nodes remain
|
|
expect(Graph.edgeCount(graph)).toBe(2) // Edge with weight 5 removed
|
|
|
|
const edge1 = Graph.getEdge(graph, edgeBC!)
|
|
const edge2 = Graph.getEdge(graph, edgeCA!)
|
|
|
|
assertSome(edge1, new Graph.Edge({ source: 1, target: 2, data: 15 }))
|
|
assertSome(edge2, new Graph.Edge({ source: 2, target: 0, data: 25 }))
|
|
|
|
// Edge with weight 5 should be removed
|
|
expect(Graph.getEdge(graph, edgeAB!)).toEqual(Option.none())
|
|
})
|
|
|
|
it("should update adjacency lists when filtering edges", () => {
|
|
let nodeA: Graph.NodeIndex
|
|
let nodeB: Graph.NodeIndex
|
|
let nodeC: Graph.NodeIndex
|
|
|
|
const graph = Graph.directed<string, string>((mutable) => {
|
|
nodeA = Graph.addNode(mutable, "A")
|
|
nodeB = Graph.addNode(mutable, "B")
|
|
nodeC = Graph.addNode(mutable, "C")
|
|
|
|
Graph.addEdge(mutable, nodeA, nodeB, "primary")
|
|
Graph.addEdge(mutable, nodeA, nodeC, "secondary")
|
|
Graph.addEdge(mutable, nodeB, nodeC, "primary")
|
|
|
|
// Keep only "primary" edges
|
|
Graph.filterEdges(mutable, (data) => data === "primary")
|
|
})
|
|
|
|
expect(Graph.edgeCount(graph)).toBe(2)
|
|
|
|
// Check adjacency - A should only connect to B now
|
|
const neighborsA = Array.from(Graph.neighbors(graph, nodeA!))
|
|
expect(neighborsA).toEqual([nodeB!]) // A -> B only
|
|
|
|
const neighborsB = Array.from(Graph.neighbors(graph, nodeB!))
|
|
expect(neighborsB).toEqual([nodeC!]) // B -> C
|
|
|
|
const neighborsC = Array.from(Graph.neighbors(graph, nodeC!))
|
|
expect(neighborsC).toEqual([]) // C has no outgoing edges
|
|
})
|
|
})
|
|
|
|
describe("addEdge", () => {
|
|
it("should add an edge between two existing nodes", () => {
|
|
let edgeIndex: Graph.EdgeIndex
|
|
|
|
const result = Graph.directed<string, number>((mutable) => {
|
|
const nodeA = Graph.addNode(mutable, "Node A")
|
|
const nodeB = Graph.addNode(mutable, "Node B")
|
|
edgeIndex = Graph.addEdge(mutable, nodeA, nodeB, 42)
|
|
})
|
|
|
|
expect(edgeIndex!).toBe(0)
|
|
expect(Graph.edgeCount(result)).toBe(1)
|
|
})
|
|
|
|
it("should add multiple edges with sequential indices", () => {
|
|
let edgeA: Graph.EdgeIndex
|
|
let edgeB: Graph.EdgeIndex
|
|
let edgeC: Graph.EdgeIndex
|
|
|
|
const result = Graph.directed<string, number>((mutable) => {
|
|
const nodeA = Graph.addNode(mutable, "Node A")
|
|
const nodeB = Graph.addNode(mutable, "Node B")
|
|
const nodeC = Graph.addNode(mutable, "Node C")
|
|
|
|
edgeA = Graph.addEdge(mutable, nodeA, nodeB, 10)
|
|
edgeB = Graph.addEdge(mutable, nodeB, nodeC, 20)
|
|
edgeC = Graph.addEdge(mutable, nodeA, nodeC, 30)
|
|
})
|
|
|
|
expect(edgeA!).toBe(0)
|
|
expect(edgeB!).toBe(1)
|
|
expect(edgeC!).toBe(2)
|
|
expect(Graph.edgeCount(result)).toBe(3)
|
|
})
|
|
|
|
it("should throw error when source node doesn't exist", () => {
|
|
expect(() => {
|
|
Graph.directed<string, number>((mutable) => {
|
|
const nodeB = Graph.addNode(mutable, "Node B")
|
|
const nonExistentNode = 999
|
|
Graph.addEdge(mutable, nonExistentNode, nodeB, 42)
|
|
})
|
|
}).toThrow("Node 999 does not exist")
|
|
})
|
|
|
|
it("should throw error when target node doesn't exist", () => {
|
|
expect(() => {
|
|
Graph.directed<string, number>((mutable) => {
|
|
const nodeA = Graph.addNode(mutable, "Node A")
|
|
const nonExistentNode = 999
|
|
Graph.addEdge(mutable, nodeA, nonExistentNode, 42)
|
|
})
|
|
}).toThrow("Node 999 does not exist")
|
|
})
|
|
})
|
|
|
|
describe("removeNode", () => {
|
|
it("should remove a node and all its incident edges", () => {
|
|
const result = Graph.directed<string, number>((mutable) => {
|
|
const nodeA = Graph.addNode(mutable, "Node A")
|
|
const nodeB = Graph.addNode(mutable, "Node B")
|
|
const nodeC = Graph.addNode(mutable, "Node C")
|
|
|
|
Graph.addEdge(mutable, nodeA, nodeB, 10)
|
|
Graph.addEdge(mutable, nodeB, nodeC, 20)
|
|
Graph.addEdge(mutable, nodeC, nodeA, 30)
|
|
|
|
expect(Graph.nodeCount(mutable)).toBe(3)
|
|
expect(Graph.edgeCount(mutable)).toBe(3)
|
|
|
|
// Remove nodeB which has 2 incident edges
|
|
Graph.removeNode(mutable, nodeB)
|
|
|
|
expect(Graph.nodeCount(mutable)).toBe(2)
|
|
expect(Graph.edgeCount(mutable)).toBe(1) // Only nodeC -> nodeA edge remains
|
|
})
|
|
|
|
expect(Graph.nodeCount(result)).toBe(2)
|
|
expect(Graph.edgeCount(result)).toBe(1)
|
|
})
|
|
|
|
it("should handle removing non-existent node gracefully", () => {
|
|
const result = Graph.directed<string, number>((mutable) => {
|
|
Graph.addNode(mutable, "Node A") // Just need one node for count
|
|
const nonExistentNode = 999
|
|
|
|
expect(Graph.nodeCount(mutable)).toBe(1)
|
|
Graph.removeNode(mutable, nonExistentNode) // Should not throw
|
|
expect(Graph.nodeCount(mutable)).toBe(1) // Should remain unchanged
|
|
})
|
|
|
|
expect(Graph.nodeCount(result)).toBe(1)
|
|
})
|
|
|
|
it("should handle isolated node removal", () => {
|
|
const result = Graph.directed<string, number>((mutable) => {
|
|
Graph.addNode(mutable, "Node A") // Keep for final count
|
|
const nodeB = Graph.addNode(mutable, "Node B") // Isolated node to remove
|
|
|
|
expect(Graph.nodeCount(mutable)).toBe(2)
|
|
expect(Graph.edgeCount(mutable)).toBe(0)
|
|
|
|
Graph.removeNode(mutable, nodeB)
|
|
|
|
expect(Graph.nodeCount(mutable)).toBe(1)
|
|
expect(Graph.edgeCount(mutable)).toBe(0)
|
|
})
|
|
|
|
expect(Graph.nodeCount(result)).toBe(1)
|
|
})
|
|
})
|
|
|
|
describe("removeEdge", () => {
|
|
it("should remove an edge between two nodes", () => {
|
|
let edgeIndex: Graph.EdgeIndex
|
|
|
|
const result = Graph.directed<string, number>((mutable) => {
|
|
const nodeA = Graph.addNode(mutable, "Node A")
|
|
const nodeB = Graph.addNode(mutable, "Node B")
|
|
edgeIndex = Graph.addEdge(mutable, nodeA, nodeB, 42)
|
|
|
|
expect(Graph.edgeCount(mutable)).toBe(1)
|
|
|
|
Graph.removeEdge(mutable, edgeIndex)
|
|
|
|
expect(Graph.edgeCount(mutable)).toBe(0)
|
|
})
|
|
|
|
expect(Graph.edgeCount(result)).toBe(0)
|
|
})
|
|
|
|
it("should handle removing non-existent edge gracefully", () => {
|
|
const result = Graph.directed<string, number>((mutable) => {
|
|
const nodeA = Graph.addNode(mutable, "Node A")
|
|
const nodeB = Graph.addNode(mutable, "Node B")
|
|
Graph.addEdge(mutable, nodeA, nodeB, 42)
|
|
|
|
const nonExistentEdge = 999
|
|
|
|
expect(Graph.edgeCount(mutable)).toBe(1)
|
|
Graph.removeEdge(mutable, nonExistentEdge) // Should not throw
|
|
expect(Graph.edgeCount(mutable)).toBe(1) // Should remain unchanged
|
|
})
|
|
|
|
expect(Graph.edgeCount(result)).toBe(1)
|
|
})
|
|
|
|
it("should handle multiple edges between same nodes", () => {
|
|
const result = Graph.directed<string, number>((mutable) => {
|
|
const nodeA = Graph.addNode(mutable, "Node A")
|
|
const nodeB = Graph.addNode(mutable, "Node B")
|
|
|
|
const edge1 = Graph.addEdge(mutable, nodeA, nodeB, 10)
|
|
const edge2 = Graph.addEdge(mutable, nodeA, nodeB, 20)
|
|
|
|
expect(Graph.edgeCount(mutable)).toBe(2)
|
|
|
|
Graph.removeEdge(mutable, edge1)
|
|
|
|
expect(Graph.edgeCount(mutable)).toBe(1)
|
|
|
|
// Verify second edge still exists
|
|
const edge2Data = mutable.edges.get(edge2)
|
|
expect(edge2Data).toBeDefined()
|
|
})
|
|
|
|
expect(Graph.edgeCount(result)).toBe(1)
|
|
})
|
|
})
|
|
|
|
describe("getEdge", () => {
|
|
it("should return edge data for existing edge", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const nodeA = Graph.addNode(mutable, "Node A")
|
|
const nodeB = Graph.addNode(mutable, "Node B")
|
|
Graph.addEdge(mutable, nodeA, nodeB, 42)
|
|
})
|
|
|
|
const edgeIndex = 0
|
|
const edge = Graph.getEdge(graph, edgeIndex)
|
|
|
|
assertSome(edge, new Graph.Edge({ source: 0, target: 1, data: 42 }))
|
|
})
|
|
|
|
it("should return None for non-existent edge", () => {
|
|
const graph = Graph.directed<string, number>()
|
|
const edgeIndex = 999
|
|
const edge = Graph.getEdge(graph, edgeIndex)
|
|
|
|
expect(edge).toEqual(Option.none())
|
|
})
|
|
|
|
describe("hasEdge", () => {
|
|
it("should return true for existing edge", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const nodeA = Graph.addNode(mutable, "Node A")
|
|
const nodeB = Graph.addNode(mutable, "Node B")
|
|
Graph.addEdge(mutable, nodeA, nodeB, 42)
|
|
})
|
|
|
|
const nodeA = 0
|
|
const nodeB = 1
|
|
|
|
expect(Graph.hasEdge(graph, nodeA, nodeB)).toBe(true)
|
|
})
|
|
|
|
it("should return false for non-existent edge", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const nodeA = Graph.addNode(mutable, "Node A")
|
|
const nodeB = Graph.addNode(mutable, "Node B")
|
|
Graph.addNode(mutable, "Node C")
|
|
Graph.addEdge(mutable, nodeA, nodeB, 42)
|
|
})
|
|
|
|
const nodeA = 0
|
|
const nodeC = 2
|
|
|
|
expect(Graph.hasEdge(graph, nodeA, nodeC)).toBe(false)
|
|
})
|
|
|
|
it("should return false for non-existent source node", () => {
|
|
const graph = Graph.directed<string, number>()
|
|
const nodeA = 0
|
|
const nodeB = 1
|
|
|
|
expect(Graph.hasEdge(graph, nodeA, nodeB)).toBe(false)
|
|
})
|
|
|
|
it("should be symmetric for undirected graphs", () => {
|
|
const graph = Graph.undirected<string, number>((mutable) => {
|
|
const nodeA = Graph.addNode(mutable, "Node A")
|
|
const nodeB = Graph.addNode(mutable, "Node B")
|
|
Graph.addEdge(mutable, nodeA, nodeB, 42)
|
|
})
|
|
|
|
expect(Graph.hasEdge(graph, 0, 1)).toBe(true)
|
|
expect(Graph.hasEdge(graph, 1, 0)).toBe(true)
|
|
})
|
|
})
|
|
|
|
describe("edgeCount", () => {
|
|
it("should return 0 for empty graph", () => {
|
|
const graph = Graph.directed<string, number>()
|
|
expect(Graph.edgeCount(graph)).toBe(0)
|
|
})
|
|
|
|
it("should return correct edge count", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const nodeA = Graph.addNode(mutable, "Node A")
|
|
const nodeB = Graph.addNode(mutable, "Node B")
|
|
const nodeC = Graph.addNode(mutable, "Node C")
|
|
Graph.addEdge(mutable, nodeA, nodeB, 1)
|
|
Graph.addEdge(mutable, nodeB, nodeC, 2)
|
|
Graph.addEdge(mutable, nodeC, nodeA, 3)
|
|
})
|
|
|
|
expect(Graph.edgeCount(graph)).toBe(3)
|
|
})
|
|
})
|
|
|
|
describe("neighbors", () => {
|
|
it("should return correct neighbors for directed graph", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const nodeA = Graph.addNode(mutable, "Node A")
|
|
const nodeB = Graph.addNode(mutable, "Node B")
|
|
const nodeC = Graph.addNode(mutable, "Node C")
|
|
Graph.addEdge(mutable, nodeA, nodeB, 1)
|
|
Graph.addEdge(mutable, nodeA, nodeC, 2)
|
|
})
|
|
|
|
const nodeA = 0
|
|
const nodeB = 1
|
|
const nodeC = 2
|
|
|
|
const neighborsA = Graph.neighbors(graph, nodeA)
|
|
expect(neighborsA).toContain(nodeB)
|
|
expect(neighborsA).toContain(nodeC)
|
|
expect(neighborsA).toHaveLength(2)
|
|
|
|
const neighborsB = Graph.neighbors(graph, nodeB)
|
|
expect(neighborsB).toEqual([])
|
|
})
|
|
})
|
|
|
|
describe("neighbors with undirected graphs", () => {
|
|
it("should return correct neighbors for single edge", () => {
|
|
const graph = Graph.undirected<number, void>((mutable) => {
|
|
Graph.addNode(mutable, 0)
|
|
Graph.addNode(mutable, 1)
|
|
Graph.addEdge(mutable, 0, 1, undefined)
|
|
})
|
|
|
|
expect(Graph.neighbors(graph, 0)).toEqual([1])
|
|
expect(Graph.neighbors(graph, 1)).toEqual([0])
|
|
})
|
|
|
|
it("should return correct neighbors for linear graph", () => {
|
|
const graph = Graph.undirected<number, void>((mutable) => {
|
|
Graph.addNode(mutable, 0)
|
|
Graph.addNode(mutable, 1)
|
|
Graph.addNode(mutable, 2)
|
|
Graph.addEdge(mutable, 0, 1, undefined)
|
|
Graph.addEdge(mutable, 1, 2, undefined)
|
|
})
|
|
|
|
expect(Graph.neighbors(graph, 0)).toEqual([1])
|
|
expect(Graph.neighbors(graph, 1).sort()).toEqual([0, 2])
|
|
expect(Graph.neighbors(graph, 2)).toEqual([1])
|
|
})
|
|
|
|
it("should handle multiple edges between same nodes", () => {
|
|
const graph = Graph.undirected<number, void>((mutable) => {
|
|
Graph.addNode(mutable, 0)
|
|
Graph.addNode(mutable, 1)
|
|
Graph.addEdge(mutable, 0, 1, undefined)
|
|
Graph.addEdge(mutable, 0, 1, undefined)
|
|
})
|
|
|
|
// Should deduplicate neighbors
|
|
expect(Graph.neighbors(graph, 0)).toEqual([1])
|
|
expect(Graph.neighbors(graph, 1)).toEqual([0])
|
|
})
|
|
|
|
it("should handle self-loops", () => {
|
|
const graph = Graph.undirected<number, void>((mutable) => {
|
|
Graph.addNode(mutable, 0)
|
|
Graph.addEdge(mutable, 0, 0, undefined)
|
|
})
|
|
|
|
expect(Graph.neighbors(graph, 0)).toEqual([0])
|
|
})
|
|
|
|
it("should handle node with no neighbors", () => {
|
|
const graph = Graph.undirected<number, void>((mutable) => {
|
|
Graph.addNode(mutable, 0)
|
|
Graph.addNode(mutable, 1)
|
|
})
|
|
|
|
expect(Graph.neighbors(graph, 0)).toEqual([])
|
|
expect(Graph.neighbors(graph, 1)).toEqual([])
|
|
})
|
|
})
|
|
|
|
describe("successors and predecessors", () => {
|
|
it("should return outgoing and incoming directed neighbors", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const nodeA = Graph.addNode(mutable, "Node A")
|
|
const nodeB = Graph.addNode(mutable, "Node B")
|
|
const nodeC = Graph.addNode(mutable, "Node C")
|
|
Graph.addEdge(mutable, nodeA, nodeB, 1)
|
|
Graph.addEdge(mutable, nodeC, nodeB, 2)
|
|
})
|
|
|
|
expect(Graph.successors(graph, 0)).toEqual([1])
|
|
expect(Graph.predecessors(graph, 1).sort()).toEqual([0, 2])
|
|
})
|
|
|
|
it("should throw for undirected graphs", () => {
|
|
const graph = Graph.undirected<string, number>((mutable) => {
|
|
const nodeA = Graph.addNode(mutable, "Node A")
|
|
const nodeB = Graph.addNode(mutable, "Node B")
|
|
Graph.addEdge(mutable, nodeA, nodeB, 1)
|
|
})
|
|
|
|
expect(() => Graph.successors(graph as any, 0)).toThrow("Cannot get successors of undirected graph")
|
|
expect(() => Graph.predecessors(graph as any, 0)).toThrow("Cannot get predecessors of undirected graph")
|
|
})
|
|
})
|
|
|
|
describe("neighborsDirected", () => {
|
|
it("should return incoming neighbors", () => {
|
|
let nodeA: Graph.NodeIndex
|
|
let nodeB: Graph.NodeIndex
|
|
let nodeC: Graph.NodeIndex
|
|
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
nodeA = Graph.addNode(mutable, "Node A")
|
|
nodeB = Graph.addNode(mutable, "Node B")
|
|
nodeC = Graph.addNode(mutable, "Node C")
|
|
Graph.addEdge(mutable, nodeA, nodeB, 1)
|
|
Graph.addEdge(mutable, nodeC, nodeB, 2)
|
|
})
|
|
|
|
const incomingB = Graph.neighborsDirected(graph, nodeB!, "incoming")
|
|
expect(incomingB.sort()).toEqual([nodeA!, nodeC!].sort())
|
|
|
|
const incomingA = Graph.neighborsDirected(graph, nodeA!, "incoming")
|
|
expect(incomingA).toEqual([])
|
|
})
|
|
|
|
it("should return outgoing neighbors", () => {
|
|
let nodeA: Graph.NodeIndex
|
|
let nodeB: Graph.NodeIndex
|
|
let nodeC: Graph.NodeIndex
|
|
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
nodeA = Graph.addNode(mutable, "Node A")
|
|
nodeB = Graph.addNode(mutable, "Node B")
|
|
nodeC = Graph.addNode(mutable, "Node C")
|
|
Graph.addEdge(mutable, nodeA, nodeB, 1)
|
|
Graph.addEdge(mutable, nodeA, nodeC, 2)
|
|
})
|
|
|
|
const outgoingA = Graph.neighborsDirected(graph, nodeA!, "outgoing")
|
|
expect(outgoingA.sort()).toEqual([nodeB!, nodeC!].sort())
|
|
|
|
const outgoingB = Graph.neighborsDirected(graph, nodeB!, "outgoing")
|
|
expect(outgoingB).toEqual([])
|
|
})
|
|
|
|
it("should handle node with no connections", () => {
|
|
let nodeA: Graph.NodeIndex
|
|
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
nodeA = Graph.addNode(mutable, "Node A")
|
|
})
|
|
|
|
expect(Graph.neighborsDirected(graph, nodeA!, "incoming")).toEqual([])
|
|
expect(Graph.neighborsDirected(graph, nodeA!, "outgoing")).toEqual([])
|
|
})
|
|
|
|
it("should throw for undirected graphs", () => {
|
|
const graph = Graph.undirected<string, number>((mutable) => {
|
|
const nodeA = Graph.addNode(mutable, "Node A")
|
|
const nodeB = Graph.addNode(mutable, "Node B")
|
|
Graph.addEdge(mutable, nodeA, nodeB, 1)
|
|
})
|
|
|
|
expect(() => Graph.neighborsDirected(graph as any, 0, "outgoing"))
|
|
.toThrow("Cannot get directed neighbors of undirected graph")
|
|
})
|
|
})
|
|
})
|
|
|
|
describe("toGraphViz", () => {
|
|
it("should export empty directed graph", () => {
|
|
const graph = Graph.directed<string, number>()
|
|
const dot = Graph.toGraphViz(graph)
|
|
|
|
expect(dot).toBe("digraph G {\n}")
|
|
})
|
|
|
|
it("should export empty undirected graph", () => {
|
|
const graph = Graph.undirected<string, number>()
|
|
const dot = Graph.toGraphViz(graph)
|
|
|
|
expect(dot).toBe("graph G {\n}")
|
|
})
|
|
|
|
it("should export directed graph with nodes and edges", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const nodeA = Graph.addNode(mutable, "Node A")
|
|
const nodeB = Graph.addNode(mutable, "Node B")
|
|
const nodeC = Graph.addNode(mutable, "Node C")
|
|
Graph.addEdge(mutable, nodeA, nodeB, 1)
|
|
Graph.addEdge(mutable, nodeB, nodeC, 2)
|
|
Graph.addEdge(mutable, nodeC, nodeA, 3)
|
|
})
|
|
|
|
const dot = Graph.toGraphViz(graph)
|
|
|
|
expect(dot).toContain("digraph G {")
|
|
expect(dot).toContain("\"0\" [label=\"Node A\"];")
|
|
expect(dot).toContain("\"1\" [label=\"Node B\"];")
|
|
expect(dot).toContain("\"2\" [label=\"Node C\"];")
|
|
expect(dot).toContain("\"0\" -> \"1\" [label=\"1\"];")
|
|
expect(dot).toContain("\"1\" -> \"2\" [label=\"2\"];")
|
|
expect(dot).toContain("\"2\" -> \"0\" [label=\"3\"];")
|
|
expect(dot).toContain("}")
|
|
})
|
|
|
|
it("should export undirected graph with correct edge format", () => {
|
|
const graph = Graph.undirected<string, number>((mutable) => {
|
|
const nodeA = Graph.addNode(mutable, "A")
|
|
const nodeB = Graph.addNode(mutable, "B")
|
|
Graph.addEdge(mutable, nodeA, nodeB, 1)
|
|
})
|
|
|
|
const dot = Graph.toGraphViz(graph)
|
|
|
|
expect(dot).toContain("graph G {")
|
|
expect(dot).toContain("\"0\" -- \"1\" [label=\"1\"];")
|
|
})
|
|
|
|
it("should support custom node and edge labels", () => {
|
|
const graph = Graph.directed<{ name: string }, { weight: number }>((mutable) => {
|
|
const nodeA = Graph.addNode(mutable, { name: "Alice" })
|
|
const nodeB = Graph.addNode(mutable, { name: "Bob" })
|
|
Graph.addEdge(mutable, nodeA, nodeB, { weight: 42 })
|
|
})
|
|
|
|
const dot = Graph.toGraphViz(graph, {
|
|
nodeLabel: (data) => data.name,
|
|
edgeLabel: (data) => `weight: ${data.weight}`,
|
|
graphName: "MyGraph"
|
|
})
|
|
|
|
expect(dot).toContain("digraph MyGraph {")
|
|
expect(dot).toContain("\"0\" [label=\"Alice\"];")
|
|
expect(dot).toContain("\"1\" [label=\"Bob\"];")
|
|
expect(dot).toContain("\"0\" -> \"1\" [label=\"weight: 42\"];")
|
|
})
|
|
|
|
it("should escape quotes in labels", () => {
|
|
const graph = Graph.directed<string, string>((mutable) => {
|
|
const nodeA = Graph.addNode(mutable, "Node \"A\"")
|
|
const nodeB = Graph.addNode(mutable, "Node \"B\"")
|
|
Graph.addEdge(mutable, nodeA, nodeB, "Edge \"1\"")
|
|
})
|
|
|
|
const dot = Graph.toGraphViz(graph)
|
|
|
|
expect(dot).toContain("\"0\" [label=\"Node \\\"A\\\"\"];")
|
|
expect(dot).toContain("\"1\" [label=\"Node \\\"B\\\"\"];")
|
|
expect(dot).toContain("\"0\" -> \"1\" [label=\"Edge \\\"1\\\"\"];")
|
|
})
|
|
|
|
it("should demonstrate graph visualization", () => {
|
|
// Create a simple directed graph representing a dependency graph
|
|
const graph = Graph.directed<string, string>((mutable) => {
|
|
const app = Graph.addNode(mutable, "App")
|
|
const auth = Graph.addNode(mutable, "Auth")
|
|
const db = Graph.addNode(mutable, "Database")
|
|
const cache = Graph.addNode(mutable, "Cache")
|
|
|
|
Graph.addEdge(mutable, app, auth, "uses")
|
|
Graph.addEdge(mutable, app, db, "stores")
|
|
Graph.addEdge(mutable, auth, db, "validates")
|
|
Graph.addEdge(mutable, app, cache, "caches")
|
|
})
|
|
|
|
const dot = Graph.toGraphViz(graph, {
|
|
graphName: "DependencyGraph"
|
|
})
|
|
|
|
// Uncomment the next line to see the GraphViz output in test console
|
|
// console.log("\nDependency Graph DOT format:\n" + dot)
|
|
|
|
expect(dot).toContain("digraph DependencyGraph {")
|
|
expect(dot).toContain("\"0\" [label=\"App\"];")
|
|
expect(dot).toContain("\"0\" -> \"1\" [label=\"uses\"];")
|
|
expect(dot).toContain("\"0\" -> \"2\" [label=\"stores\"];")
|
|
expect(dot).toContain("\"1\" -> \"2\" [label=\"validates\"];")
|
|
expect(dot).toContain("\"0\" -> \"3\" [label=\"caches\"];")
|
|
})
|
|
|
|
it("should demonstrate undirected graph visualization", () => {
|
|
// Create a simple social network graph
|
|
const graph = Graph.undirected<string, string>((mutable) => {
|
|
const alice = Graph.addNode(mutable, "Alice")
|
|
const bob = Graph.addNode(mutable, "Bob")
|
|
const charlie = Graph.addNode(mutable, "Charlie")
|
|
const diana = Graph.addNode(mutable, "Diana")
|
|
|
|
Graph.addEdge(mutable, alice, bob, "friends")
|
|
Graph.addEdge(mutable, bob, charlie, "friends")
|
|
Graph.addEdge(mutable, charlie, diana, "friends")
|
|
Graph.addEdge(mutable, alice, diana, "friends")
|
|
})
|
|
|
|
const dot = Graph.toGraphViz(graph, {
|
|
graphName: "SocialNetwork"
|
|
})
|
|
|
|
// Uncomment the next line to see the GraphViz output in test console
|
|
// console.log("\nSocial Network DOT format:\n" + dot)
|
|
|
|
expect(dot).toContain("graph SocialNetwork {")
|
|
expect(dot).toContain("\"0\" [label=\"Alice\"];")
|
|
expect(dot).toContain("\"0\" -- \"1\" [label=\"friends\"];")
|
|
expect(dot).toContain("\"1\" -- \"2\" [label=\"friends\"];")
|
|
expect(dot).toContain("\"2\" -- \"3\" [label=\"friends\"];")
|
|
expect(dot).toContain("\"0\" -- \"3\" [label=\"friends\"];")
|
|
})
|
|
})
|
|
|
|
describe("toMermaid", () => {
|
|
it("should export empty directed graph", () => {
|
|
const graph = Graph.directed<string, number>()
|
|
const mermaid = Graph.toMermaid(graph)
|
|
expect(mermaid).toBe("flowchart TD")
|
|
})
|
|
|
|
it("should export empty undirected graph", () => {
|
|
const graph = Graph.undirected<string, number>()
|
|
const mermaid = Graph.toMermaid(graph)
|
|
expect(mermaid).toBe("graph TD")
|
|
})
|
|
|
|
it("should export directed graph with nodes", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
Graph.addNode(mutable, "Node A")
|
|
Graph.addNode(mutable, "Node B")
|
|
Graph.addNode(mutable, "Node C")
|
|
})
|
|
|
|
const mermaid = Graph.toMermaid(graph)
|
|
expect(mermaid).toContain("flowchart TD")
|
|
expect(mermaid).toContain("0[\"Node A\"]")
|
|
expect(mermaid).toContain("1[\"Node B\"]")
|
|
expect(mermaid).toContain("2[\"Node C\"]")
|
|
})
|
|
|
|
it("should export undirected graph with nodes", () => {
|
|
const graph = Graph.undirected<string, number>((mutable) => {
|
|
Graph.addNode(mutable, "Alice")
|
|
Graph.addNode(mutable, "Bob")
|
|
})
|
|
|
|
const mermaid = Graph.toMermaid(graph)
|
|
expect(mermaid).toContain("graph TD")
|
|
expect(mermaid).toContain("0[\"Alice\"]")
|
|
expect(mermaid).toContain("1[\"Bob\"]")
|
|
})
|
|
|
|
it("should support all node shapes", () => {
|
|
const shapes: Array<[string, any]> = [
|
|
["rectangle", "rectangle"],
|
|
["rounded", "rounded"],
|
|
["circle", "circle"],
|
|
["diamond", "diamond"],
|
|
["hexagon", "hexagon"],
|
|
["stadium", "stadium"],
|
|
["subroutine", "subroutine"],
|
|
["cylindrical", "cylindrical"]
|
|
]
|
|
|
|
shapes.forEach(([shapeName, shapeValue]) => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
Graph.addNode(mutable, "Test")
|
|
})
|
|
|
|
const mermaid = Graph.toMermaid(graph, {
|
|
nodeShape: () => shapeValue
|
|
})
|
|
|
|
expect(mermaid).toContain("flowchart TD")
|
|
|
|
// Test expected shape format
|
|
switch (shapeName) {
|
|
case "rectangle":
|
|
expect(mermaid).toContain("0[\"Test\"]")
|
|
break
|
|
case "rounded":
|
|
expect(mermaid).toContain("0(\"Test\")")
|
|
break
|
|
case "circle":
|
|
expect(mermaid).toContain("0((\"Test\"))")
|
|
break
|
|
case "diamond":
|
|
expect(mermaid).toContain("0{\"Test\"}")
|
|
break
|
|
case "hexagon":
|
|
expect(mermaid).toContain("0{{\"Test\"}}")
|
|
break
|
|
case "stadium":
|
|
expect(mermaid).toContain("0([\"Test\"])")
|
|
break
|
|
case "subroutine":
|
|
expect(mermaid).toContain("0[[\"Test\"]]")
|
|
break
|
|
case "cylindrical":
|
|
expect(mermaid).toContain("0[(\"Test\")]")
|
|
break
|
|
}
|
|
})
|
|
})
|
|
|
|
it("should escape special characters in labels", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
Graph.addNode(mutable, "Node with \"quotes\"")
|
|
Graph.addNode(mutable, "Node with [brackets]")
|
|
Graph.addNode(mutable, "Node with | pipe")
|
|
Graph.addNode(mutable, "Node with \\ backslash")
|
|
Graph.addNode(mutable, "Node with \n newline")
|
|
})
|
|
|
|
const mermaid = Graph.toMermaid(graph)
|
|
|
|
expect(mermaid).toContain("0[\"Node with #quot;quotes#quot;\"]")
|
|
expect(mermaid).toContain("1[\"Node with #91;brackets#93;\"]")
|
|
expect(mermaid).toContain("2[\"Node with #124; pipe\"]")
|
|
expect(mermaid).toContain("3[\"Node with #92; backslash\"]")
|
|
expect(mermaid).toContain("4[\"Node with <br/> newline\"]")
|
|
})
|
|
|
|
it("should export directed graph with edges", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const nodeA = Graph.addNode(mutable, "Node A")
|
|
const nodeB = Graph.addNode(mutable, "Node B")
|
|
const nodeC = Graph.addNode(mutable, "Node C")
|
|
Graph.addEdge(mutable, nodeA, nodeB, 1)
|
|
Graph.addEdge(mutable, nodeB, nodeC, 2)
|
|
Graph.addEdge(mutable, nodeC, nodeA, 3)
|
|
})
|
|
|
|
const mermaid = Graph.toMermaid(graph)
|
|
expect(mermaid).toContain("flowchart TD")
|
|
expect(mermaid).toContain("0[\"Node A\"]")
|
|
expect(mermaid).toContain("1[\"Node B\"]")
|
|
expect(mermaid).toContain("2[\"Node C\"]")
|
|
expect(mermaid).toContain("0 -->|\"1\"| 1")
|
|
expect(mermaid).toContain("1 -->|\"2\"| 2")
|
|
expect(mermaid).toContain("2 -->|\"3\"| 0")
|
|
})
|
|
|
|
it("should export undirected graph with edges", () => {
|
|
const graph = Graph.undirected<string, string>((mutable) => {
|
|
const alice = Graph.addNode(mutable, "Alice")
|
|
const bob = Graph.addNode(mutable, "Bob")
|
|
const charlie = Graph.addNode(mutable, "Charlie")
|
|
Graph.addEdge(mutable, alice, bob, "friends")
|
|
Graph.addEdge(mutable, bob, charlie, "colleagues")
|
|
})
|
|
|
|
const mermaid = Graph.toMermaid(graph)
|
|
expect(mermaid).toContain("graph TD")
|
|
expect(mermaid).toContain("0[\"Alice\"]")
|
|
expect(mermaid).toContain("1[\"Bob\"]")
|
|
expect(mermaid).toContain("2[\"Charlie\"]")
|
|
expect(mermaid).toContain("0 ---|\"friends\"| 1")
|
|
expect(mermaid).toContain("1 ---|\"colleagues\"| 2")
|
|
})
|
|
|
|
it("should handle empty edge labels", () => {
|
|
const graph = Graph.directed<string, string>((mutable) => {
|
|
const nodeA = Graph.addNode(mutable, "A")
|
|
const nodeB = Graph.addNode(mutable, "B")
|
|
Graph.addEdge(mutable, nodeA, nodeB, "")
|
|
})
|
|
|
|
const mermaid = Graph.toMermaid(graph)
|
|
expect(mermaid).toContain("0 --> 1")
|
|
})
|
|
|
|
it("should support all diagram directions", () => {
|
|
const directions = ["TB", "TD", "BT", "RL", "LR"] as const
|
|
|
|
directions.forEach((dir) => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
Graph.addNode(mutable, "A")
|
|
Graph.addNode(mutable, "B")
|
|
})
|
|
|
|
const mermaid = Graph.toMermaid(graph, { direction: dir })
|
|
expect(mermaid).toContain(`flowchart ${dir}`)
|
|
expect(mermaid).toContain("0[\"A\"]")
|
|
expect(mermaid).toContain("1[\"B\"]")
|
|
})
|
|
})
|
|
|
|
it("should auto-detect diagram type based on graph type", () => {
|
|
// Directed graph should auto-detect as flowchart
|
|
const directedGraph = Graph.directed<string, number>((mutable) => {
|
|
Graph.addNode(mutable, "A")
|
|
})
|
|
const directedMermaid = Graph.toMermaid(directedGraph)
|
|
expect(directedMermaid).toContain("flowchart TD")
|
|
|
|
// Undirected graph should auto-detect as graph
|
|
const undirectedGraph = Graph.undirected<string, number>((mutable) => {
|
|
Graph.addNode(mutable, "A")
|
|
})
|
|
const undirectedMermaid = Graph.toMermaid(undirectedGraph)
|
|
expect(undirectedMermaid).toContain("graph TD")
|
|
})
|
|
|
|
it("should allow manual diagram type override", () => {
|
|
// Override directed graph to use 'graph' type
|
|
const directedGraph = Graph.directed<string, number>((mutable) => {
|
|
Graph.addNode(mutable, "A")
|
|
})
|
|
const overriddenMermaid = Graph.toMermaid(directedGraph, {
|
|
diagramType: "graph"
|
|
})
|
|
expect(overriddenMermaid).toContain("graph TD")
|
|
|
|
// Override undirected graph to use 'flowchart' type
|
|
const undirectedGraph = Graph.undirected<string, number>((mutable) => {
|
|
Graph.addNode(mutable, "B")
|
|
})
|
|
const overriddenFlowchart = Graph.toMermaid(undirectedGraph, {
|
|
diagramType: "flowchart"
|
|
})
|
|
expect(overriddenFlowchart).toContain("flowchart TD")
|
|
})
|
|
|
|
it("should combine direction and diagram type options", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
Graph.addNode(mutable, "Test")
|
|
})
|
|
|
|
const mermaid = Graph.toMermaid(graph, {
|
|
direction: "LR",
|
|
diagramType: "graph"
|
|
})
|
|
|
|
expect(mermaid).toContain("graph LR")
|
|
expect(mermaid).toContain("0[\"Test\"]")
|
|
})
|
|
|
|
it("should handle self-loops correctly", () => {
|
|
const graph = Graph.directed<string, string>((mutable) => {
|
|
const nodeA = Graph.addNode(mutable, "A")
|
|
Graph.addEdge(mutable, nodeA, nodeA, "self")
|
|
})
|
|
|
|
const mermaid = Graph.toMermaid(graph)
|
|
expect(mermaid).toContain("flowchart TD")
|
|
expect(mermaid).toContain("0[\"A\"]")
|
|
expect(mermaid).toContain("0 -->|\"self\"| 0")
|
|
})
|
|
|
|
it("should handle multi-edges correctly", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const nodeA = Graph.addNode(mutable, "A")
|
|
const nodeB = Graph.addNode(mutable, "B")
|
|
Graph.addEdge(mutable, nodeA, nodeB, 1)
|
|
Graph.addEdge(mutable, nodeA, nodeB, 2)
|
|
Graph.addEdge(mutable, nodeA, nodeB, 3)
|
|
})
|
|
|
|
const mermaid = Graph.toMermaid(graph)
|
|
expect(mermaid).toContain("flowchart TD")
|
|
expect(mermaid).toContain("0[\"A\"]")
|
|
expect(mermaid).toContain("1[\"B\"]")
|
|
// Should contain all three edges
|
|
expect(mermaid).toContain("0 -->|\"1\"| 1")
|
|
expect(mermaid).toContain("0 -->|\"2\"| 1")
|
|
expect(mermaid).toContain("0 -->|\"3\"| 1")
|
|
})
|
|
|
|
it("should handle disconnected components", () => {
|
|
const graph = Graph.directed<string, string>((mutable) => {
|
|
// Component 1: A -> B
|
|
const nodeA = Graph.addNode(mutable, "A")
|
|
const nodeB = Graph.addNode(mutable, "B")
|
|
Graph.addEdge(mutable, nodeA, nodeB, "A->B")
|
|
|
|
// Component 2: C -> D (disconnected)
|
|
const nodeC = Graph.addNode(mutable, "C")
|
|
const nodeD = Graph.addNode(mutable, "D")
|
|
Graph.addEdge(mutable, nodeC, nodeD, "C->D")
|
|
|
|
// Isolated node E
|
|
Graph.addNode(mutable, "E")
|
|
})
|
|
|
|
const mermaid = Graph.toMermaid(graph)
|
|
expect(mermaid).toContain("flowchart TD")
|
|
expect(mermaid).toContain("0[\"A\"]")
|
|
expect(mermaid).toContain("1[\"B\"]")
|
|
expect(mermaid).toContain("2[\"C\"]")
|
|
expect(mermaid).toContain("3[\"D\"]")
|
|
expect(mermaid).toContain("4[\"E\"]")
|
|
expect(mermaid).toContain("0 -->|\"A-#gt;B\"| 1")
|
|
expect(mermaid).toContain("2 -->|\"C-#gt;D\"| 3")
|
|
})
|
|
|
|
it("should handle custom labels with complex data", () => {
|
|
interface NodeData {
|
|
id: string
|
|
value: number
|
|
metadata: { type: string }
|
|
}
|
|
|
|
interface EdgeData {
|
|
weight: number
|
|
type: string
|
|
}
|
|
|
|
const graph = Graph.directed<NodeData, EdgeData>((mutable) => {
|
|
const node1 = Graph.addNode(mutable, {
|
|
id: "node1",
|
|
value: 42,
|
|
metadata: { type: "input" }
|
|
})
|
|
const node2 = Graph.addNode(mutable, {
|
|
id: "node2",
|
|
value: 84,
|
|
metadata: { type: "processing" }
|
|
})
|
|
Graph.addEdge(mutable, node1, node2, { weight: 1.5, type: "data" })
|
|
})
|
|
|
|
const mermaid = Graph.toMermaid(graph, {
|
|
nodeLabel: (data) => `${data.id}:${data.value}`,
|
|
edgeLabel: (data) => `${data.type}(${data.weight})`,
|
|
direction: "LR"
|
|
})
|
|
|
|
expect(mermaid).toContain("flowchart LR")
|
|
expect(mermaid).toContain("0[\"node1:42\"]")
|
|
expect(mermaid).toContain("1[\"node2:84\"]")
|
|
expect(mermaid).toContain("0 -->|\"data#40;1.5#41;\"| 1")
|
|
})
|
|
})
|
|
|
|
describe("isAcyclic", () => {
|
|
it("should detect acyclic directed graphs (DAGs)", () => {
|
|
const dag = Graph.directed<string, string>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
const d = Graph.addNode(mutable, "D")
|
|
Graph.addEdge(mutable, a, b, "A->B")
|
|
Graph.addEdge(mutable, a, c, "A->C")
|
|
Graph.addEdge(mutable, b, d, "B->D")
|
|
Graph.addEdge(mutable, c, d, "C->D")
|
|
})
|
|
|
|
expect(Graph.isAcyclic(dag)).toBe(true)
|
|
})
|
|
|
|
it("should detect cycles in directed graphs", () => {
|
|
const cyclic = Graph.directed<string, string>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, "A->B")
|
|
Graph.addEdge(mutable, b, c, "B->C")
|
|
Graph.addEdge(mutable, c, a, "C->A") // Creates cycle
|
|
})
|
|
|
|
expect(Graph.isAcyclic(cyclic)).toBe(false)
|
|
})
|
|
|
|
it("should handle disconnected components", () => {
|
|
const disconnected = Graph.directed<string, string>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
const d = Graph.addNode(mutable, "D")
|
|
Graph.addEdge(mutable, a, b, "A->B") // Component 1: A->B (acyclic)
|
|
Graph.addEdge(mutable, c, d, "C->D") // Component 2: C->D (acyclic)
|
|
// No connections between components
|
|
})
|
|
|
|
expect(Graph.isAcyclic(disconnected)).toBe(true)
|
|
})
|
|
|
|
it("should detect cycles in one component of disconnected graph", () => {
|
|
const mixedComponents = Graph.directed<string, string>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
const d = Graph.addNode(mutable, "D")
|
|
Graph.addEdge(mutable, a, b, "A->B") // Component 1: A->B (acyclic)
|
|
Graph.addEdge(mutable, c, d, "C->D") // Component 2: C->D->C (cyclic)
|
|
Graph.addEdge(mutable, d, c, "D->C")
|
|
})
|
|
|
|
expect(Graph.isAcyclic(mixedComponents)).toBe(false)
|
|
})
|
|
|
|
it("should treat a reversed-storage undirected chain as acyclic", () => {
|
|
const graph = makeReversedUndirectedPath()
|
|
|
|
expect(Graph.isAcyclic(graph)).toBe(true)
|
|
})
|
|
|
|
it("should detect cycles in undirected graphs", () => {
|
|
const graph = Graph.undirected<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
Graph.addEdge(mutable, b, c, 1)
|
|
Graph.addEdge(mutable, c, a, 1)
|
|
})
|
|
|
|
expect(Graph.isAcyclic(graph)).toBe(false)
|
|
})
|
|
})
|
|
|
|
describe("isBipartite", () => {
|
|
it("should detect bipartite undirected graphs", () => {
|
|
const bipartite = Graph.undirected<string, string>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
const d = Graph.addNode(mutable, "D")
|
|
Graph.addEdge(mutable, a, b, "edge") // Set 1: {A, C}, Set 2: {B, D}
|
|
Graph.addEdge(mutable, b, c, "edge")
|
|
Graph.addEdge(mutable, c, d, "edge")
|
|
Graph.addEdge(mutable, d, a, "edge")
|
|
})
|
|
|
|
expect(Graph.isBipartite(bipartite)).toBe(true)
|
|
})
|
|
|
|
it("should detect non-bipartite graphs (odd cycles)", () => {
|
|
const triangle = Graph.undirected<string, string>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, "edge")
|
|
Graph.addEdge(mutable, b, c, "edge")
|
|
Graph.addEdge(mutable, c, a, "edge") // Triangle (3-cycle)
|
|
})
|
|
|
|
expect(Graph.isBipartite(triangle)).toBe(false)
|
|
})
|
|
|
|
it("should handle path graphs (always bipartite)", () => {
|
|
const path = Graph.undirected<string, string>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
const d = Graph.addNode(mutable, "D")
|
|
Graph.addEdge(mutable, a, b, "edge")
|
|
Graph.addEdge(mutable, b, c, "edge")
|
|
Graph.addEdge(mutable, c, d, "edge")
|
|
})
|
|
|
|
expect(Graph.isBipartite(path)).toBe(true)
|
|
})
|
|
|
|
it("should handle disconnected components", () => {
|
|
const disconnected = Graph.undirected<string, string>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
const d = Graph.addNode(mutable, "D")
|
|
Graph.addEdge(mutable, a, b, "edge") // Component 1: A-B (bipartite)
|
|
Graph.addEdge(mutable, c, d, "edge") // Component 2: C-D (bipartite)
|
|
// No connections between components
|
|
})
|
|
|
|
expect(Graph.isBipartite(disconnected)).toBe(true)
|
|
})
|
|
|
|
it("should detect non-bipartite component in disconnected graph", () => {
|
|
const mixedComponents = Graph.undirected<string, string>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
const d = Graph.addNode(mutable, "D")
|
|
const e = Graph.addNode(mutable, "E")
|
|
Graph.addEdge(mutable, a, b, "edge") // Component 1: A-B (bipartite)
|
|
Graph.addEdge(mutable, c, d, "edge") // Component 2: triangle (non-bipartite)
|
|
Graph.addEdge(mutable, d, e, "edge")
|
|
Graph.addEdge(mutable, e, c, "edge")
|
|
})
|
|
|
|
expect(Graph.isBipartite(mixedComponents)).toBe(false)
|
|
})
|
|
})
|
|
|
|
describe("connectedComponents", () => {
|
|
it("should find connected components in disconnected undirected graph", () => {
|
|
const graph = Graph.undirected<string, string>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
const d = Graph.addNode(mutable, "D")
|
|
Graph.addNode(mutable, "E")
|
|
Graph.addEdge(mutable, a, b, "edge") // Component 1: A-B
|
|
Graph.addEdge(mutable, c, d, "edge") // Component 2: C-D
|
|
// E is isolated - Component 3: E
|
|
})
|
|
|
|
const components = Graph.connectedComponents(graph)
|
|
expect(components).toHaveLength(3)
|
|
|
|
// Sort components by size and first element for deterministic testing
|
|
components.sort((a, b) => a.length - b.length || a[0] - b[0])
|
|
expect(components[0]).toEqual([4]) // E isolated
|
|
expect(components[1]).toHaveLength(2) // A-B or C-D
|
|
expect(components[2]).toHaveLength(2) // A-B or C-D
|
|
})
|
|
|
|
it("should handle fully connected component", () => {
|
|
const graph = Graph.undirected<string, string>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, "edge")
|
|
Graph.addEdge(mutable, b, c, "edge")
|
|
Graph.addEdge(mutable, c, a, "edge")
|
|
})
|
|
|
|
const components = Graph.connectedComponents(graph)
|
|
expect(components).toHaveLength(1)
|
|
expect(components[0]).toHaveLength(3)
|
|
expect(components[0].sort()).toEqual([0, 1, 2])
|
|
})
|
|
})
|
|
|
|
describe("stronglyConnectedComponents", () => {
|
|
it("should find strongly connected components in directed graph", () => {
|
|
const graph = Graph.directed<string, string>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
const d = Graph.addNode(mutable, "D")
|
|
Graph.addEdge(mutable, a, b, "A->B")
|
|
Graph.addEdge(mutable, b, c, "B->C")
|
|
Graph.addEdge(mutable, c, a, "C->A") // SCC: A-B-C
|
|
Graph.addEdge(mutable, b, d, "B->D") // D is separate
|
|
})
|
|
|
|
const sccs = Graph.stronglyConnectedComponents(graph)
|
|
expect(sccs).toHaveLength(2)
|
|
|
|
// Sort SCCs by size for deterministic testing
|
|
sccs.sort((a, b) => a.length - b.length)
|
|
expect(sccs[0]).toEqual([3]) // D is alone
|
|
expect(sccs[1]).toHaveLength(3) // A-B-C cycle
|
|
expect(sccs[1].sort()).toEqual([0, 1, 2])
|
|
})
|
|
|
|
it("should handle acyclic directed graph (each node is its own SCC)", () => {
|
|
const dag = Graph.directed<string, string>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, "A->B")
|
|
Graph.addEdge(mutable, b, c, "B->C")
|
|
})
|
|
|
|
const sccs = Graph.stronglyConnectedComponents(dag)
|
|
expect(sccs).toHaveLength(3)
|
|
// Each SCC should contain exactly one node
|
|
sccs.forEach((scc) => {
|
|
expect(scc).toHaveLength(1)
|
|
})
|
|
})
|
|
|
|
it("should handle fully connected components", () => {
|
|
const graph = Graph.directed<string, string>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
// Create bidirectional edges (fully connected)
|
|
Graph.addEdge(mutable, a, b, "A->B")
|
|
Graph.addEdge(mutable, b, a, "B->A")
|
|
Graph.addEdge(mutable, b, c, "B->C")
|
|
Graph.addEdge(mutable, c, b, "C->B")
|
|
Graph.addEdge(mutable, a, c, "A->C")
|
|
Graph.addEdge(mutable, c, a, "C->A")
|
|
})
|
|
|
|
const sccs = Graph.stronglyConnectedComponents(graph)
|
|
expect(sccs).toHaveLength(1)
|
|
expect(sccs[0]).toHaveLength(3)
|
|
expect(sccs[0].sort()).toEqual([0, 1, 2])
|
|
})
|
|
|
|
it("should handle disconnected components with cycles", () => {
|
|
const graph = Graph.directed<string, string>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
const d = Graph.addNode(mutable, "D")
|
|
// First SCC: A->B->A
|
|
Graph.addEdge(mutable, a, b, "A->B")
|
|
Graph.addEdge(mutable, b, a, "B->A")
|
|
// Second SCC: C->D->C
|
|
Graph.addEdge(mutable, c, d, "C->D")
|
|
Graph.addEdge(mutable, d, c, "D->C")
|
|
})
|
|
|
|
const sccs = Graph.stronglyConnectedComponents(graph)
|
|
expect(sccs).toHaveLength(2)
|
|
sccs.forEach((scc) => {
|
|
expect(scc).toHaveLength(2)
|
|
})
|
|
})
|
|
|
|
it("should throw for undirected graphs", () => {
|
|
const graph = makeReversedUndirectedPath()
|
|
|
|
expect(() => Graph.stronglyConnectedComponents(graph as any))
|
|
.toThrow("Cannot find strongly connected components of undirected graph")
|
|
})
|
|
})
|
|
|
|
describe("dijkstra", () => {
|
|
it("should find shortest path in simple graph", () => {
|
|
let nodeA: Graph.NodeIndex
|
|
let nodeB: Graph.NodeIndex
|
|
let nodeC: Graph.NodeIndex
|
|
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
nodeA = Graph.addNode(mutable, "A")
|
|
nodeB = Graph.addNode(mutable, "B")
|
|
nodeC = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, nodeA, nodeB, 5)
|
|
Graph.addEdge(mutable, nodeA, nodeC, 10)
|
|
Graph.addEdge(mutable, nodeB, nodeC, 2)
|
|
})
|
|
|
|
const result = Graph.dijkstra(graph, {
|
|
source: nodeA!,
|
|
target: nodeC!,
|
|
cost: (edge) => edge
|
|
})
|
|
|
|
assertSome(result, { path: [nodeA!, nodeB!, nodeC!], distance: 7, costs: [5, 2] })
|
|
})
|
|
|
|
it("should return None for unreachable nodes", () => {
|
|
let nodeA: Graph.NodeIndex
|
|
let nodeB: Graph.NodeIndex
|
|
let nodeC: Graph.NodeIndex
|
|
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
nodeA = Graph.addNode(mutable, "A")
|
|
nodeB = Graph.addNode(mutable, "B")
|
|
nodeC = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, nodeA, nodeB, 1)
|
|
// No path from A to C
|
|
})
|
|
|
|
const result = Graph.dijkstra(graph, {
|
|
source: nodeA!,
|
|
target: nodeC!,
|
|
cost: (edge) => edge
|
|
})
|
|
|
|
expect(result).toEqual(Option.none())
|
|
})
|
|
|
|
it("should handle same source and target", () => {
|
|
let nodeA: Graph.NodeIndex
|
|
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
nodeA = Graph.addNode(mutable, "A")
|
|
})
|
|
|
|
const result = Graph.dijkstra(graph, {
|
|
source: nodeA!,
|
|
target: nodeA!,
|
|
cost: (edge) => edge
|
|
})
|
|
|
|
assertSome(result, { path: [nodeA!], distance: 0, costs: [] })
|
|
})
|
|
|
|
it("should throw for negative weights", () => {
|
|
let nodeA: Graph.NodeIndex
|
|
let nodeB: Graph.NodeIndex
|
|
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
nodeA = Graph.addNode(mutable, "A")
|
|
nodeB = Graph.addNode(mutable, "B")
|
|
Graph.addEdge(mutable, nodeA, nodeB, -1)
|
|
})
|
|
|
|
expect(() =>
|
|
Graph.dijkstra(graph, {
|
|
source: nodeA!,
|
|
target: nodeB!,
|
|
cost: (edge) => edge
|
|
})
|
|
).toThrow(
|
|
"Dijkstra's algorithm requires non-negative edge weights"
|
|
)
|
|
})
|
|
|
|
it("should throw for negative weights before early target termination", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const source = Graph.addNode(mutable, "source")
|
|
const target = Graph.addNode(mutable, "target")
|
|
const other = Graph.addNode(mutable, "other")
|
|
Graph.addEdge(mutable, source, target, 1)
|
|
Graph.addEdge(mutable, source, other, 2)
|
|
Graph.addEdge(mutable, other, target, -5)
|
|
})
|
|
|
|
expect(() =>
|
|
Graph.dijkstra(graph, {
|
|
source: 0,
|
|
target: 1,
|
|
cost: (edge) => edge
|
|
})
|
|
).toThrow("Dijkstra's algorithm requires non-negative edge weights")
|
|
})
|
|
|
|
it("should validate weights before returning same source and target", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const node = Graph.addNode(mutable, "node")
|
|
Graph.addEdge(mutable, node, node, -1)
|
|
})
|
|
|
|
expect(() =>
|
|
Graph.dijkstra(graph, {
|
|
source: 0,
|
|
target: 0,
|
|
cost: (edge) => edge
|
|
})
|
|
).toThrow("Dijkstra's algorithm requires non-negative edge weights")
|
|
})
|
|
|
|
it("should throw for non-existent nodes", () => {
|
|
const graph = Graph.directed<string, number>()
|
|
|
|
expect(() =>
|
|
Graph.dijkstra(graph, {
|
|
source: 0,
|
|
target: 1,
|
|
cost: (edge) => edge
|
|
})
|
|
).toThrow("Node 0 does not exist")
|
|
})
|
|
|
|
it("should traverse undirected edges in reverse storage direction", () => {
|
|
const graph = makeReversedUndirectedPath()
|
|
|
|
const result = Graph.dijkstra(graph, {
|
|
source: 0,
|
|
target: 2,
|
|
cost: (edge) => edge
|
|
})
|
|
|
|
assertSome(result, { path: [0, 1, 2], distance: 2, costs: [1, 1] })
|
|
})
|
|
})
|
|
|
|
describe("astar", () => {
|
|
it("should find shortest path with heuristic", () => {
|
|
let nodeA: Graph.NodeIndex
|
|
let nodeB: Graph.NodeIndex
|
|
let nodeC: Graph.NodeIndex
|
|
|
|
const graph = Graph.directed<{ x: number; y: number }, number>((mutable) => {
|
|
nodeA = Graph.addNode(mutable, { x: 0, y: 0 })
|
|
nodeB = Graph.addNode(mutable, { x: 1, y: 0 })
|
|
nodeC = Graph.addNode(mutable, { x: 2, y: 0 })
|
|
Graph.addEdge(mutable, nodeA, nodeB, 1)
|
|
Graph.addEdge(mutable, nodeB, nodeC, 1)
|
|
})
|
|
|
|
const heuristic = (source: { x: number; y: number }, target: { x: number; y: number }) =>
|
|
Math.abs(source.x - target.x) + Math.abs(source.y - target.y)
|
|
|
|
const result = Graph.astar(graph, {
|
|
source: nodeA!,
|
|
target: nodeC!,
|
|
cost: (edge) => edge,
|
|
heuristic
|
|
})
|
|
|
|
assertSome(result, { path: [nodeA!, nodeB!, nodeC!], distance: 2, costs: [1, 1] })
|
|
})
|
|
|
|
it("should return None for unreachable nodes", () => {
|
|
const graph = Graph.directed<{ x: number; y: number }, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, { x: 0, y: 0 })
|
|
const b = Graph.addNode(mutable, { x: 1, y: 0 })
|
|
Graph.addNode(mutable, { x: 2, y: 0 })
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
// No path from A to C
|
|
})
|
|
|
|
const heuristic = (source: { x: number; y: number }, target: { x: number; y: number }) =>
|
|
Math.abs(source.x - target.x) + Math.abs(source.y - target.y)
|
|
|
|
const result = Graph.astar(graph, {
|
|
source: 0,
|
|
target: 2,
|
|
cost: (edge) => edge,
|
|
heuristic
|
|
})
|
|
assertNone(result)
|
|
})
|
|
|
|
it("should handle same source and target", () => {
|
|
const graph = Graph.directed<{ x: number; y: number }, number>((mutable) => {
|
|
Graph.addNode(mutable, { x: 0, y: 0 })
|
|
})
|
|
|
|
const heuristic = (source: { x: number; y: number }, target: { x: number; y: number }) =>
|
|
Math.abs(source.x - target.x) + Math.abs(source.y - target.y)
|
|
|
|
const result = Graph.astar(graph, {
|
|
source: 0,
|
|
target: 0,
|
|
cost: (edge) => edge,
|
|
heuristic
|
|
})
|
|
|
|
assertSome(result, { path: [0], distance: 0, costs: [] })
|
|
})
|
|
|
|
it("should throw for negative weights", () => {
|
|
const graph = Graph.directed<{ x: number; y: number }, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, { x: 0, y: 0 })
|
|
const b = Graph.addNode(mutable, { x: 1, y: 0 })
|
|
Graph.addEdge(mutable, a, b, -1)
|
|
})
|
|
|
|
const heuristic = (source: { x: number; y: number }, target: { x: number; y: number }) =>
|
|
Math.abs(source.x - target.x) + Math.abs(source.y - target.y)
|
|
|
|
expect(() =>
|
|
Graph.astar(graph, {
|
|
source: 0,
|
|
target: 1,
|
|
cost: (edge) => edge,
|
|
heuristic
|
|
})
|
|
).toThrow("A* algorithm requires non-negative edge weights")
|
|
})
|
|
|
|
it("should throw for negative weights before early target termination", () => {
|
|
const graph = Graph.directed<{ x: number; y: number }, number>((mutable) => {
|
|
const source = Graph.addNode(mutable, { x: 0, y: 0 })
|
|
const target = Graph.addNode(mutable, { x: 1, y: 0 })
|
|
const other = Graph.addNode(mutable, { x: 2, y: 0 })
|
|
Graph.addEdge(mutable, source, target, 1)
|
|
Graph.addEdge(mutable, source, other, 2)
|
|
Graph.addEdge(mutable, other, target, -5)
|
|
})
|
|
|
|
expect(() =>
|
|
Graph.astar(graph, {
|
|
source: 0,
|
|
target: 1,
|
|
cost: (edge) => edge,
|
|
heuristic: () => 0
|
|
})
|
|
).toThrow("A* algorithm requires non-negative edge weights")
|
|
})
|
|
|
|
it("should validate weights before returning same source and target", () => {
|
|
const graph = Graph.directed<{ x: number; y: number }, number>((mutable) => {
|
|
const node = Graph.addNode(mutable, { x: 0, y: 0 })
|
|
Graph.addEdge(mutable, node, node, -1)
|
|
})
|
|
|
|
expect(() =>
|
|
Graph.astar(graph, {
|
|
source: 0,
|
|
target: 0,
|
|
cost: (edge) => edge,
|
|
heuristic: () => 0
|
|
})
|
|
).toThrow("A* algorithm requires non-negative edge weights")
|
|
})
|
|
|
|
it("should traverse undirected edges in reverse storage direction", () => {
|
|
const graph = makeReversedUndirectedPath()
|
|
|
|
const result = Graph.astar(graph, {
|
|
source: 0,
|
|
target: 2,
|
|
cost: (edge) => edge,
|
|
heuristic: () => 0
|
|
})
|
|
|
|
assertSome(result, { path: [0, 1, 2], distance: 2, costs: [1, 1] })
|
|
})
|
|
})
|
|
|
|
describe("Bellman-Ford", () => {
|
|
it("should find shortest path with negative weights", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, -1)
|
|
Graph.addEdge(mutable, b, c, 3)
|
|
Graph.addEdge(mutable, a, c, 5)
|
|
})
|
|
|
|
const result = Graph.bellmanFord(graph, {
|
|
source: 0,
|
|
target: 2,
|
|
cost: (edge) => edge
|
|
})
|
|
|
|
assertSome(result, { path: [0, 1, 2], distance: 2, costs: [-1, 3] })
|
|
})
|
|
|
|
it("should return None for unreachable nodes", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
// No path from A to C
|
|
})
|
|
|
|
const result = Graph.bellmanFord(graph, {
|
|
source: 0,
|
|
target: 2,
|
|
cost: (edge) => edge
|
|
})
|
|
|
|
assertNone(result)
|
|
})
|
|
|
|
it("should handle same source and target", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
Graph.addNode(mutable, "A")
|
|
})
|
|
|
|
const result = Graph.bellmanFord(graph, {
|
|
source: 0,
|
|
target: 0,
|
|
cost: (edge) => edge
|
|
})
|
|
|
|
assertSome(result, { path: [0], distance: 0, costs: [] })
|
|
})
|
|
|
|
it("should detect negative cycles", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
Graph.addEdge(mutable, b, c, -3)
|
|
Graph.addEdge(mutable, c, a, 1)
|
|
})
|
|
|
|
const result = Graph.bellmanFord(graph, {
|
|
source: 0,
|
|
target: 2,
|
|
cost: (edge) => edge
|
|
})
|
|
|
|
expect(result).toEqual(Option.none())
|
|
})
|
|
|
|
it("should traverse undirected edges in reverse storage direction", () => {
|
|
const graph = makeReversedUndirectedPath()
|
|
|
|
const result = Graph.bellmanFord(graph, {
|
|
source: 0,
|
|
target: 2,
|
|
cost: (edge) => edge
|
|
})
|
|
|
|
assertSome(result, { path: [0, 1, 2], distance: 2, costs: [1, 1] })
|
|
})
|
|
|
|
it("should treat a reachable negative undirected edge as a negative cycle", () => {
|
|
const graph = Graph.undirected<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
Graph.addEdge(mutable, a, b, -1)
|
|
})
|
|
|
|
const result = Graph.bellmanFord(graph, {
|
|
source: 0,
|
|
target: 1,
|
|
cost: (edge) => edge
|
|
})
|
|
|
|
assertNone(result)
|
|
})
|
|
})
|
|
|
|
describe("Floyd-Warshall", () => {
|
|
it("should find all-pairs shortest paths", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, 3)
|
|
Graph.addEdge(mutable, b, c, 2)
|
|
Graph.addEdge(mutable, a, c, 7)
|
|
})
|
|
|
|
const result = Graph.floydWarshall(graph, (edge) => edge)
|
|
|
|
// Check distance A to C (should be 5 via B, not 7 direct)
|
|
expect(result.distances.get(0)?.get(2)).toBe(5)
|
|
expect(result.paths.get(0)?.get(2)).toEqual([0, 1, 2])
|
|
expect(result.costs.get(0)?.get(2)).toEqual([3, 2])
|
|
|
|
// Check distance A to B
|
|
expect(result.distances.get(0)?.get(1)).toBe(3)
|
|
expect(result.paths.get(0)?.get(1)).toEqual([0, 1])
|
|
|
|
// Check distance B to C
|
|
expect(result.distances.get(1)?.get(2)).toBe(2)
|
|
expect(result.paths.get(1)?.get(2)).toEqual([1, 2])
|
|
})
|
|
|
|
it("should handle unreachable nodes", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
// No path from A to C
|
|
})
|
|
|
|
const result = Graph.floydWarshall(graph, (edge) => edge)
|
|
|
|
expect(result.distances.get(0)?.get(2)).toBe(Infinity)
|
|
expect(result.paths.get(0)?.get(2)).toBeNull()
|
|
})
|
|
|
|
it("should handle same source and target", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
Graph.addNode(mutable, "A")
|
|
})
|
|
|
|
const result = Graph.floydWarshall(graph, (edge) => edge)
|
|
|
|
expect(result.distances.get(0)?.get(0)).toBe(0)
|
|
expect(result.paths.get(0)?.get(0)).toEqual([0])
|
|
expect(result.costs.get(0)?.get(0)).toEqual([])
|
|
})
|
|
|
|
it("should detect negative cycles", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
Graph.addEdge(mutable, b, c, -3)
|
|
Graph.addEdge(mutable, c, a, 1)
|
|
})
|
|
|
|
expect(() => Graph.floydWarshall(graph, (edge) => edge)).toThrow("Negative cycle detected")
|
|
})
|
|
|
|
it("should traverse undirected edges in reverse storage direction", () => {
|
|
const graph = makeReversedUndirectedPath()
|
|
|
|
const result = Graph.floydWarshall(graph, (edge) => edge)
|
|
|
|
expect(result.distances.get(0)?.get(2)).toBe(2)
|
|
expect(result.paths.get(0)?.get(2)).toEqual([0, 1, 2])
|
|
expect(result.costs.get(0)?.get(2)).toEqual([1, 1])
|
|
})
|
|
|
|
it("should treat negative undirected edges as negative cycles", () => {
|
|
const graph = Graph.undirected<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
Graph.addEdge(mutable, a, b, -1)
|
|
})
|
|
|
|
expect(() => Graph.floydWarshall(graph, (edge) => edge)).toThrow("Negative cycle detected")
|
|
})
|
|
})
|
|
|
|
describe("Iterator Base Methods", () => {
|
|
it("should provide values() method for DFS iterator", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
Graph.addEdge(mutable, b, c, 2)
|
|
})
|
|
|
|
const dfsIterator = Graph.dfs(graph, { start: [0] })
|
|
const values = Array.from(Graph.values(dfsIterator))
|
|
|
|
expect(values).toEqual(["A", "B", "C"])
|
|
})
|
|
|
|
it("should provide entries() method for DFS iterator", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
Graph.addEdge(mutable, b, c, 2)
|
|
})
|
|
|
|
const dfsIterator = Graph.dfs(graph, { start: [0] })
|
|
const entries = Array.from(Graph.entries(dfsIterator))
|
|
|
|
expect(entries).toEqual([[0, "A"], [1, "B"], [2, "C"]])
|
|
})
|
|
|
|
it("should provide values() method for BFS iterator", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
Graph.addEdge(mutable, a, c, 2)
|
|
})
|
|
|
|
const bfsIterator = Graph.bfs(graph, { start: [0] })
|
|
const values = Array.from(Graph.values(bfsIterator))
|
|
|
|
expect(values).toEqual(["A", "B", "C"])
|
|
})
|
|
|
|
it("should provide entries() method for BFS iterator", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
Graph.addEdge(mutable, a, c, 2)
|
|
})
|
|
|
|
const bfsIterator = Graph.bfs(graph, { start: [0] })
|
|
const entries = Array.from(Graph.entries(bfsIterator))
|
|
|
|
expect(entries).toEqual([[0, "A"], [1, "B"], [2, "C"]])
|
|
})
|
|
|
|
it("should provide values() method for Topo iterator", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
Graph.addEdge(mutable, b, c, 2)
|
|
})
|
|
|
|
const topoIterator = Graph.topo(graph)
|
|
|
|
const values = Array.from(Graph.values(topoIterator))
|
|
expect(values).toEqual(["A", "B", "C"])
|
|
})
|
|
|
|
it("should provide entries() method for Topo iterator", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
Graph.addEdge(mutable, b, c, 2)
|
|
})
|
|
|
|
const topoIterator = Graph.topo(graph)
|
|
|
|
const entries = Array.from(Graph.entries(topoIterator))
|
|
expect(entries).toEqual([[0, "A"], [1, "B"], [2, "C"]])
|
|
})
|
|
|
|
it("should prioritize valid initials and still include all nodes", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
const d = Graph.addNode(mutable, "D")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
Graph.addEdge(mutable, c, d, 2)
|
|
})
|
|
|
|
const order = Array.from(Graph.indices(Graph.topo(graph, { initials: [2] })))
|
|
expect(order).toEqual([2, 0, 3, 1])
|
|
})
|
|
|
|
it("should reject initials with incoming edges", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
})
|
|
|
|
expect(() => Array.from(Graph.topo(graph, { initials: [1] })))
|
|
.toThrow("Initial node 1 has incoming edges")
|
|
})
|
|
|
|
it("should throw for cyclic graphs", () => {
|
|
const cyclicGraph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
Graph.addEdge(mutable, b, a, 2) // Creates cycle
|
|
})
|
|
|
|
expect(() => Graph.topo(cyclicGraph)).toThrow("Cannot perform topological sort on cyclic graph")
|
|
})
|
|
|
|
it("should throw for undirected graphs", () => {
|
|
const graph = makeReversedUndirectedPath()
|
|
|
|
expect(() => Graph.topo(graph)).toThrow("Cannot perform topological sort on undirected graph")
|
|
})
|
|
|
|
it("should handle corrupted graph state during topological sort", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
})
|
|
|
|
// Test edge case by corrupting graph internals during iteration
|
|
const mutableGraph = graph as any
|
|
const originalGetNode = mutableGraph.nodes.get
|
|
|
|
let callCount = 0
|
|
// Mock getNode to return undefined for certain calls to trigger the recursive edge case
|
|
mutableGraph.nodes.get = function(key: any) {
|
|
callCount++
|
|
// On specific call, return undefined to trigger the Option.isNone path
|
|
if (callCount === 2) {
|
|
return undefined
|
|
}
|
|
return originalGetNode.call(this, key)
|
|
}
|
|
|
|
const iterator = Graph.topo(graph)
|
|
const results = Array.from(iterator)
|
|
|
|
// Restore original method
|
|
mutableGraph.nodes.get = originalGetNode
|
|
|
|
// Should complete without crashing
|
|
expect(results.length).toBeGreaterThanOrEqual(0)
|
|
})
|
|
|
|
it("should provide values() method for DfsPostOrder iterator", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
Graph.addEdge(mutable, b, c, 2)
|
|
})
|
|
|
|
const dfsPostIterator = Graph.dfsPostOrder(graph, { start: [0] })
|
|
const values = Array.from(Graph.values(dfsPostIterator))
|
|
|
|
expect(values).toEqual(["C", "B", "A"]) // Postorder: children before parents
|
|
})
|
|
|
|
it("should provide entries() method for DfsPostOrder iterator", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
Graph.addEdge(mutable, b, c, 2)
|
|
})
|
|
|
|
const dfsPostIterator = Graph.dfsPostOrder(graph, { start: [0] })
|
|
const entries = Array.from(Graph.entries(dfsPostIterator))
|
|
|
|
expect(entries).toEqual([[2, "C"], [1, "B"], [0, "A"]]) // Postorder: children before parents
|
|
})
|
|
|
|
it("should traverse undirected edges in reverse storage direction", () => {
|
|
const graph = makeReversedUndirectedPath()
|
|
|
|
expect(Array.from(Graph.indices(Graph.dfs(graph, { start: [0] })))).toEqual([0, 1, 2])
|
|
expect(Array.from(Graph.indices(Graph.dfs(graph, { start: [0], direction: "incoming" })))).toEqual([0, 1, 2])
|
|
expect(Array.from(Graph.indices(Graph.bfs(graph, { start: [0] })))).toEqual([0, 1, 2])
|
|
expect(Array.from(Graph.indices(Graph.dfsPostOrder(graph, { start: [0] })))).toEqual([2, 1, 0])
|
|
})
|
|
})
|
|
|
|
describe("DfsPostOrder Iterator", () => {
|
|
it("should traverse in postorder for simple chain", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
Graph.addEdge(mutable, b, c, 2)
|
|
})
|
|
|
|
const postOrder = Array.from(Graph.indices(Graph.dfsPostOrder(graph, { start: [0] })))
|
|
expect(postOrder).toEqual([2, 1, 0]) // Children before parents
|
|
})
|
|
|
|
it("should traverse in postorder for branching tree", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const root = Graph.addNode(mutable, "root") // 0
|
|
const left = Graph.addNode(mutable, "left") // 1
|
|
const right = Graph.addNode(mutable, "right") // 2
|
|
const leaf1 = Graph.addNode(mutable, "leaf1") // 3
|
|
const leaf2 = Graph.addNode(mutable, "leaf2") // 4
|
|
|
|
Graph.addEdge(mutable, root, left, 1)
|
|
Graph.addEdge(mutable, root, right, 2)
|
|
Graph.addEdge(mutable, left, leaf1, 3)
|
|
Graph.addEdge(mutable, right, leaf2, 4)
|
|
})
|
|
|
|
const postOrder = Array.from(Graph.indices(Graph.dfsPostOrder(graph, { start: [0] })))
|
|
// Should visit leaves first, then parents
|
|
expect(postOrder).toEqual([3, 1, 4, 2, 0])
|
|
})
|
|
|
|
it("should handle empty start nodes", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
Graph.addNode(mutable, "A")
|
|
})
|
|
|
|
const postOrder = Array.from(Graph.dfsPostOrder(graph, { start: [] }))
|
|
expect(postOrder).toEqual([])
|
|
})
|
|
|
|
it("should handle disconnected components with multiple start nodes", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
const d = Graph.addNode(mutable, "D")
|
|
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
Graph.addEdge(mutable, c, d, 2)
|
|
// No connection between (A,B) and (C,D)
|
|
})
|
|
|
|
const postOrder = Array.from(Graph.indices(Graph.dfsPostOrder(graph, { start: [0, 2] })))
|
|
expect(postOrder).toEqual([1, 0, 3, 2]) // Each component in postorder
|
|
})
|
|
|
|
it("should support incoming direction", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
Graph.addEdge(mutable, b, c, 2)
|
|
})
|
|
|
|
// Starting from C, going backwards
|
|
const postOrder = Array.from(
|
|
Graph.indices(Graph.dfsPostOrder(graph, {
|
|
start: [2],
|
|
direction: "incoming"
|
|
}))
|
|
)
|
|
expect(postOrder).toEqual([0, 1, 2]) // A, B, C in reverse postorder
|
|
})
|
|
|
|
it("should handle cycles correctly", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
Graph.addEdge(mutable, b, c, 2)
|
|
Graph.addEdge(mutable, c, a, 3) // Creates cycle
|
|
})
|
|
|
|
const postOrder = Array.from(Graph.indices(Graph.dfsPostOrder(graph, { start: [0] })))
|
|
// Should handle cycle without infinite loop, visiting each node once
|
|
expect(postOrder.length).toBe(3)
|
|
expect(new Set(postOrder)).toEqual(new Set([0, 1, 2]))
|
|
})
|
|
|
|
it("should throw error for non-existent start node", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
Graph.addNode(mutable, "A")
|
|
})
|
|
|
|
expect(() => Graph.dfsPostOrder(graph, { start: [99] }))
|
|
.toThrow("Node 99 does not exist")
|
|
})
|
|
|
|
it("should be iterable multiple times with fresh state", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
})
|
|
|
|
const iterator = Graph.dfsPostOrder(graph, { start: [0] })
|
|
|
|
const firstRun = Array.from(Graph.indices(iterator))
|
|
const secondRun = Array.from(Graph.indices(iterator))
|
|
|
|
expect(firstRun).toEqual([1, 0])
|
|
expect(secondRun).toEqual([1, 0])
|
|
expect(firstRun).toEqual(secondRun)
|
|
})
|
|
|
|
it("should handle corrupted graph state during iteration", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
})
|
|
|
|
// Test edge case by corrupting graph internals during iteration
|
|
const mutableGraph = graph as any
|
|
const originalGetNode = mutableGraph.nodes.get
|
|
|
|
let callCount = 0
|
|
// Mock getNode to return undefined for certain calls to trigger the recursive edge case
|
|
mutableGraph.nodes.get = function(key: any) {
|
|
callCount++
|
|
// On specific call, return undefined to trigger the Option.isNone path
|
|
if (callCount === 3) {
|
|
return undefined
|
|
}
|
|
return originalGetNode.call(this, key)
|
|
}
|
|
|
|
const iterator = Graph.dfsPostOrder(graph, { start: [0] })
|
|
const results = Array.from(iterator)
|
|
|
|
// Restore original method
|
|
mutableGraph.nodes.get = originalGetNode
|
|
|
|
// Should complete without crashing
|
|
expect(results.length).toBeGreaterThanOrEqual(0)
|
|
})
|
|
})
|
|
|
|
describe("Graph Element Iterators", () => {
|
|
describe("nodes", () => {
|
|
it("should iterate over all node indices", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
Graph.addNode(mutable, "A")
|
|
Graph.addNode(mutable, "B")
|
|
Graph.addNode(mutable, "C")
|
|
})
|
|
|
|
const indices = Array.from(Graph.indices(Graph.nodes(graph)))
|
|
expect(indices).toEqual([0, 1, 2])
|
|
})
|
|
|
|
it("should work with manual iterator control", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
Graph.addNode(mutable, "A")
|
|
Graph.addNode(mutable, "B")
|
|
})
|
|
|
|
const iterator = Graph.indices(Graph.nodes(graph))[Symbol.iterator]()
|
|
expect(iterator.next().value).toBe(0)
|
|
expect(iterator.next().value).toBe(1)
|
|
expect(iterator.next().done).toBe(true)
|
|
})
|
|
})
|
|
|
|
describe("edges", () => {
|
|
it("should iterate over all edge indices", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
Graph.addEdge(mutable, b, c, 2)
|
|
Graph.addEdge(mutable, c, a, 3)
|
|
})
|
|
|
|
const indices = Array.from(Graph.indices(Graph.edges(graph)))
|
|
expect(indices).toEqual([0, 1, 2])
|
|
})
|
|
|
|
it("should handle graph with no edges", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
Graph.addNode(mutable, "A")
|
|
Graph.addNode(mutable, "B")
|
|
})
|
|
|
|
const indices = Array.from(Graph.indices(Graph.edges(graph)))
|
|
expect(indices).toEqual([])
|
|
})
|
|
})
|
|
|
|
describe("externals", () => {
|
|
it("should find nodes with no outgoing edges (sinks)", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const source = Graph.addNode(mutable, "source") // 0
|
|
const middle = Graph.addNode(mutable, "middle") // 1
|
|
const sink = Graph.addNode(mutable, "sink") // 2
|
|
Graph.addNode(mutable, "isolated") // 3
|
|
|
|
Graph.addEdge(mutable, source, middle, 1)
|
|
Graph.addEdge(mutable, middle, sink, 2)
|
|
// No outgoing edges from sink (2) or isolated (3)
|
|
})
|
|
|
|
const sinks = Array.from(Graph.indices(Graph.externals(graph, { direction: "outgoing" })))
|
|
expect(sinks.sort()).toEqual([2, 3])
|
|
})
|
|
|
|
it("should find nodes with no incoming edges (sources)", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const source = Graph.addNode(mutable, "source") // 0
|
|
const middle = Graph.addNode(mutable, "middle") // 1
|
|
const sink = Graph.addNode(mutable, "sink") // 2
|
|
Graph.addNode(mutable, "isolated") // 3
|
|
|
|
Graph.addEdge(mutable, source, middle, 1)
|
|
Graph.addEdge(mutable, middle, sink, 2)
|
|
// No incoming edges to source (0) or isolated (3)
|
|
})
|
|
|
|
const sources = Array.from(Graph.indices(Graph.externals(graph, { direction: "incoming" })))
|
|
expect(sources.sort()).toEqual([0, 3])
|
|
})
|
|
|
|
it("should default to outgoing direction", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
// b has no outgoing edges
|
|
})
|
|
|
|
const externalsDefault = Array.from(Graph.indices(Graph.externals(graph)))
|
|
const externalsExplicit = Array.from(Graph.indices(Graph.externals(graph, { direction: "outgoing" })))
|
|
|
|
expect(externalsDefault).toEqual(externalsExplicit)
|
|
expect(externalsDefault).toEqual([1])
|
|
})
|
|
|
|
it("should handle fully connected components", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
Graph.addEdge(mutable, b, c, 2)
|
|
Graph.addEdge(mutable, c, a, 3) // Creates cycle
|
|
})
|
|
|
|
const outgoingExternals = Array.from(Graph.indices(Graph.externals(graph, { direction: "outgoing" })))
|
|
const incomingExternals = Array.from(Graph.indices(Graph.externals(graph, { direction: "incoming" })))
|
|
|
|
expect(outgoingExternals).toEqual([]) // All nodes have outgoing edges
|
|
expect(incomingExternals).toEqual([]) // All nodes have incoming edges
|
|
})
|
|
|
|
it("should work with manual iterator control", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
// b and c have no outgoing edges
|
|
})
|
|
|
|
const iterator = Graph.indices(Graph.externals(graph, { direction: "outgoing" }))[Symbol.iterator]()
|
|
|
|
const first = iterator.next().value
|
|
const second = iterator.next().value
|
|
const third = iterator.next()
|
|
|
|
expect([first, second].sort()).toEqual([1, 2])
|
|
expect(third.done).toBe(true)
|
|
})
|
|
})
|
|
|
|
it("should allow combining different element iterators", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
Graph.addEdge(mutable, a, b, 100)
|
|
})
|
|
|
|
// Combine different iterators
|
|
const nodeCount = Array.from(Graph.indices(Graph.nodes(graph))).length
|
|
const edgeCount = Array.from(Graph.indices(Graph.edges(graph))).length
|
|
const nodeData = Array.from(Graph.values(Graph.nodes(graph)))
|
|
const edge = Array.from(Graph.values(Graph.edges(graph)))
|
|
|
|
expect(nodeCount).toBe(2)
|
|
expect(edgeCount).toBe(1)
|
|
expect(nodeData).toEqual(["A", "B"])
|
|
expect(edge).toEqual([{ source: 0, target: 1, data: 100 }])
|
|
})
|
|
})
|
|
|
|
describe("GraphIterable abstraction", () => {
|
|
it("should enable iteration over different types", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
Graph.addEdge(mutable, b, c, 2)
|
|
})
|
|
|
|
// Should work with different iterator types
|
|
const dfsIterable = Graph.dfs(graph, { start: [0] })
|
|
const nodesIterable = Graph.nodes(graph)
|
|
const externalsIterable = Graph.externals(graph)
|
|
|
|
// All should be iterable and have expected structure
|
|
expect(Array.from(dfsIterable)).toHaveLength(3)
|
|
expect(Array.from(nodesIterable)).toHaveLength(3)
|
|
expect(Array.from(externalsIterable)).toHaveLength(1) // Only one node with no outgoing edges
|
|
})
|
|
})
|
|
|
|
describe("NodeIterable abstraction", () => {
|
|
it("should provide common interface for node index iterables", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
Graph.addEdge(mutable, b, c, 2)
|
|
})
|
|
|
|
// Utility function that works with any NodeWalker
|
|
function collectNodes<N>(
|
|
nodeIterable: Graph.NodeWalker<N>
|
|
): Array<number> {
|
|
return Array.from(Graph.indices(nodeIterable)).sort()
|
|
}
|
|
|
|
// Both traversal and element iterators implement NodeWalker
|
|
const dfsNodes = Graph.dfs(graph, { start: [0] })
|
|
const allNodes = Graph.nodes(graph)
|
|
const externalNodes = Graph.externals(graph, { direction: "outgoing" })
|
|
|
|
// All should work with the same utility function
|
|
expect(collectNodes(dfsNodes)).toEqual([0, 1, 2])
|
|
expect(collectNodes(allNodes)).toEqual([0, 1, 2])
|
|
expect(collectNodes(externalNodes)).toEqual([2]) // Only node 2 has no outgoing edges
|
|
})
|
|
|
|
it("should allow type-safe node iterable operations", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
})
|
|
|
|
const nodeIterable: Graph.NodeWalker<string> = Graph.nodes(graph)
|
|
const traversalIterable: Graph.NodeWalker<string> = Graph.dfs(graph, {
|
|
start: [0]
|
|
})
|
|
|
|
expect(Array.from(Graph.indices(nodeIterable))).toEqual([0, 1])
|
|
expect(Array.from(Graph.indices(traversalIterable))).toEqual([0, 1])
|
|
})
|
|
})
|
|
|
|
describe("Standalone utility functions", () => {
|
|
it("should work with values() function on any NodeIterable", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
const c = Graph.addNode(mutable, "C")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
Graph.addEdge(mutable, b, c, 2)
|
|
})
|
|
|
|
// Test with traversal iterators
|
|
const dfsIterable = Graph.dfs(graph, { start: [0] })
|
|
const dfsValues = Array.from(Graph.values(dfsIterable))
|
|
expect(dfsValues).toEqual(["A", "B", "C"])
|
|
|
|
// Test with element iterators
|
|
const nodesIterable = Graph.nodes(graph)
|
|
const nodeValues = Array.from(Graph.values(nodesIterable))
|
|
expect(nodeValues.sort()).toEqual(["A", "B", "C"])
|
|
|
|
// Test with externals iterator
|
|
const externalsIterable = Graph.externals(graph, { direction: "outgoing" })
|
|
const externalValues = Array.from(Graph.values(externalsIterable))
|
|
expect(externalValues).toEqual(["C"]) // Only C has no outgoing edges
|
|
})
|
|
|
|
it("should work with entries() function on any NodeIterable", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
})
|
|
|
|
// Test with traversal iterator
|
|
const dfsIterable = Graph.dfs(graph, { start: [0] })
|
|
const dfsEntries = Array.from(Graph.entries(dfsIterable))
|
|
expect(dfsEntries).toEqual([[0, "A"], [1, "B"]])
|
|
|
|
// Test with element iterator
|
|
const nodesIterable = Graph.nodes(graph)
|
|
const nodeEntries = Array.from(Graph.entries(nodesIterable))
|
|
expect(nodeEntries.sort()).toEqual([[0, "A"], [1, "B"]])
|
|
|
|
// Test with externals iterator
|
|
const externalsIterable = Graph.externals(graph, { direction: "outgoing" })
|
|
const externalEntries = Array.from(Graph.entries(externalsIterable))
|
|
expect(externalEntries).toEqual([[1, "B"]]) // Only B has no outgoing edges
|
|
})
|
|
|
|
it("should work with instance methods", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
})
|
|
|
|
const dfs = Graph.dfs(graph, { start: [0] })
|
|
|
|
// Instance methods should work
|
|
const instanceValues = Array.from(Graph.values(dfs))
|
|
const instanceEntries = Array.from(Graph.entries(dfs))
|
|
|
|
expect(instanceValues).toEqual(["A", "B"])
|
|
expect(instanceEntries).toEqual([[0, "A"], [1, "B"]])
|
|
})
|
|
|
|
it("should work with mapEntry for NodeIterable", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
Graph.addEdge(mutable, a, b, 1)
|
|
})
|
|
|
|
const dfs = Graph.dfs(graph, { start: [0] })
|
|
|
|
// Test mapEntry with custom mapping
|
|
const custom = Array.from(dfs.visit((index, data) => ({ id: index, name: data })))
|
|
expect(custom).toEqual([{ id: 0, name: "A" }, { id: 1, name: "B" }])
|
|
|
|
// Test that values() is implemented using mapEntry
|
|
const values = Array.from(Graph.values(dfs))
|
|
expect(values).toEqual(["A", "B"])
|
|
|
|
// Test that entries() is implemented using mapEntry
|
|
const entries = Array.from(Graph.entries(dfs))
|
|
expect(entries).toEqual([[0, "A"], [1, "B"]])
|
|
})
|
|
|
|
it("should work with mapEntry for EdgeIterable", () => {
|
|
const graph = Graph.directed<string, number>((mutable) => {
|
|
const a = Graph.addNode(mutable, "A")
|
|
const b = Graph.addNode(mutable, "B")
|
|
Graph.addEdge(mutable, a, b, 42)
|
|
})
|
|
|
|
const edgesIterable = Graph.edges(graph)
|
|
|
|
// Test mapEntry with custom mapping
|
|
const connections = Array.from(edgesIterable.visit((index, edge) => ({
|
|
id: index,
|
|
from: edge.source,
|
|
to: edge.target,
|
|
weight: edge.data
|
|
})))
|
|
expect(connections).toEqual([{ id: 0, from: 0, to: 1, weight: 42 }])
|
|
|
|
// Test that values() is implemented using mapEntry
|
|
const weights = Array.from(edgesIterable.visit((_, edge) => edge.data))
|
|
expect(weights).toEqual([42])
|
|
|
|
// Test that entries() is implemented using mapEntry
|
|
const entries = Array.from(Graph.entries(edgesIterable))
|
|
expect(entries).toEqual([[0, { source: 0, target: 1, data: 42 }]])
|
|
})
|
|
})
|
|
})
|