1import { assert, describe, it } from "@effect/vitest"
2import { throws } from "@effect/vitest/utils"
3import { Effect, Equivalence, Graph, Option, Schema } from "effect"
4import * as Arbitrary from "effect/Arbitrary"
5
6const directedCodec = Schema.toCodecJson(Schema.Graph("directed", Schema.String, Schema.Number))
7const undirectedCodec = Schema.toCodecJson(Schema.Graph("undirected", Schema.String, Schema.Number))
8const decodeDirected = Schema.decodeUnknownSync(directedCodec)
9const encodeDirected = Schema.encodeSync(directedCodec)
10
11const empty = (type: Graph.Kind) => ({ type, nodes: [], edges: [] })
12
13const assertDecodeFailure = (input: unknown, path: string, message?: string) => {
14 throws(() => decodeDirected(input), (error) => {
15 const formatted = globalThis.String(error)
16 assert.include(formatted, path)
17 if (message !== undefined) assert.include(formatted, message)
18 })
19}
20
21describe("Schema.Graph", () => {
22 it.effect("derives productive arbitrary graphs", () =>
23 Effect.gen(function*() {
24 for (const type of ["directed", "undirected"] as const) {
25 const schema = Schema.Graph(type, Schema.String, Schema.Number)
26 const arbitrary = Arbitrary.schema(schema)
27 const values = yield* Arbitrary.sampleEffect(arbitrary, {
28 count: 100,
29 maxDiscards: 0,
30 seed: `graph-${type}`
31 })
32
33 assert.isTrue(values.every(Schema.is(schema)))
34 assert.isTrue(values.some((graph) => Array.from(graph).length > 0))
35 assert.isTrue(values.some((graph) => Array.from(Graph.edges(graph)).length > 0))
36 }
37 }))
38
39 it.effect("derives recursive graph payloads", () =>
40 Effect.gen(function*() {
41 type RecursiveGraph = Graph.Graph<RecursiveGraph, null, "directed">
42 const RecursiveGraph: Schema.Codec<RecursiveGraph> = Schema.suspend(() =>
43 Schema.Graph("directed", RecursiveGraph, Schema.Null)
44 )
45 const values = yield* Arbitrary.sampleEffect(Arbitrary.schema(RecursiveGraph), {
46 count: 30,
47 maxDiscards: 0,
48 seed: "recursive-graph",
49 size: 5
50 })
51
52 assert.isTrue(values.every(Schema.is(RecursiveGraph)))
53 assert.isTrue(values.some((graph) => Array.from(graph).length > 0))
54 }))
55
56 it("derives active-structure equivalence from payload schemas", () => {
57 const modulo = Schema.Number.annotate({
58 toEquivalence: (): Equivalence.Equivalence<number> => Equivalence.make((a, b) => a % 2 === b % 2)
59 })
60 const equivalence = Schema.toEquivalence(Schema.Graph("directed", modulo, modulo))
61 const left = Graph.directed<number, number>((mutable) => {
62 const a = Graph.addNode(mutable, 0)
63 const b = Graph.addNode(mutable, 1)
64 Graph.addEdge(mutable, a, b, 2)
65 })
66 const right = Graph.directed<number, number>((mutable) => {
67 const a = Graph.addNode(mutable, 2)
68 const b = Graph.addNode(mutable, 3)
69 Graph.addEdge(mutable, a, b, 4)
70 })
71
72 assert.strictEqual(equivalence(left, right), true)
73
74 const undirectedEquivalence = Schema.toEquivalence(Schema.Graph("undirected", Schema.Number, Schema.Number))
75 const forward = Graph.undirected<number, number>((mutable) => {
76 Graph.addNode(mutable, 0)
77 Graph.addNode(mutable, 1)
78 Graph.addEdge(mutable, 0, 1, 2)
79 })
80 const reversed = Graph.undirected<number, number>((mutable) => {
81 Graph.addNode(mutable, 0)
82 Graph.addNode(mutable, 1)
83 Graph.addEdge(mutable, 1, 0, 2)
84 })
85 assert.strictEqual(undirectedEquivalence(forward, reversed), true)
86 })
87
88 it("encodes and decodes empty directed and undirected graphs", () => {
89 assert.deepStrictEqual(encodeDirected(Graph.directed()), empty("directed"))
90 assert.deepStrictEqual(Schema.encodeSync(undirectedCodec)(Graph.undirected()), empty("undirected"))
91 assert.strictEqual(decodeDirected(empty("directed")).type, "directed")
92 assert.strictEqual(Schema.decodeUnknownSync(undirectedCodec)(empty("undirected")).type, "undirected")
93 })
94
95 it("preserves indexed directed structure, isolated nodes, loops, parallel edges, and gaps", () => {
96 const graph = Graph.directed<string, number>((mutable) => {
97 const removed = Graph.addNode(mutable, "removed")
98 const source = Graph.addNode(mutable, "source")
99 const target = Graph.addNode(mutable, "target")
100 Graph.addNode(mutable, "isolated")
101 Graph.removeNode(mutable, removed)
102 const removedEdge = Graph.addEdge(mutable, source, target, -1)
103 Graph.addEdge(mutable, source, source, 1)
104 Graph.addEdge(mutable, source, target, 2)
105 Graph.addEdge(mutable, source, target, 3)
106 Graph.removeEdge(mutable, removedEdge)
107 })
108 const encoded = {
109 type: "directed",
110 nodes: [
111 { index: 1, data: "source" },
112 { index: 2, data: "target" },
113 { index: 3, data: "isolated" }
114 ],
115 edges: [
116 { index: 1, source: 1, target: 1, data: 1 },
117 { index: 2, source: 1, target: 2, data: 2 },
118 { index: 3, source: 1, target: 2, data: 3 }
119 ]
120 } satisfies Graph.Snapshot<string, number, "directed">
121
122 assert.deepStrictEqual(encodeDirected(graph), encoded)
123 const decoded = decodeDirected(encoded)
124 assert.deepStrictEqual(Array.from(decoded), encoded.nodes.map(({ index, data }) => [index, data] as const))
125 assert.deepStrictEqual(
126 Array.from(Graph.edges(decoded), ([index, edge]) => ({ index, ...edge })),
127 encoded.edges
128 )
129 assert.deepStrictEqual(encodeDirected(decoded), encoded)
130 })
131
132 it("preserves stored orientation for undirected edges", () => {
133 const graph = Graph.undirected<string, number>((mutable) => {
134 const a = Graph.addNode(mutable, "A")
135 const b = Graph.addNode(mutable, "B")
136 Graph.addEdge(mutable, b, a, 1)
137 })
138 const encoded = Schema.encodeSync(undirectedCodec)(graph)
139
140 assert.deepStrictEqual(encoded, {
141 type: "undirected",
142 nodes: [{ index: 0, data: "A" }, { index: 1, data: "B" }],
143 edges: [{ index: 0, source: 1, target: 0, data: 1 }]
144 })
145 assert.deepStrictEqual(
146 Schema.encodeSync(undirectedCodec)(Schema.decodeUnknownSync(undirectedCodec)(encoded)),
147 encoded
148 )
149 })
150
151 it("starts a new allocation lineage after the highest active indexes", () => {
152 const decoded = decodeDirected({
153 type: "directed",
154 nodes: [{ index: 2, data: "A" }, { index: 5, data: "B" }],
155 edges: [{ index: 4, source: 2, target: 5, data: 1 }]
156 })
157 let nodeIndex: Graph.NodeIndex | undefined
158 let edgeIndex: Graph.EdgeIndex | undefined
159 Graph.mutate(decoded, (mutable) => {
160 nodeIndex = Graph.addNode(mutable, "C")
161 edgeIndex = Graph.addEdge(mutable, 5, nodeIndex, 2)
162 })
163
164 assert.strictEqual(nodeIndex, 6)
165 assert.strictEqual(edgeIndex, 5)
166 })
167
168 it("does not serialize removed trailing allocation history", () => {
169 const graph = Graph.directed<string, number>((mutable) => {
170 const a = Graph.addNode(mutable, "A")
171 const b = Graph.addNode(mutable, "B")
172 const trailing = Graph.addNode(mutable, "removed")
173 const active = Graph.addEdge(mutable, a, b, 1)
174 const removed = Graph.addEdge(mutable, a, b, 2)
175 Graph.removeEdge(mutable, removed)
176 Graph.removeNode(mutable, trailing)
177 assert.strictEqual(active, 0)
178 })
179 const decoded = decodeDirected(encodeDirected(graph))
180 let nodeIndex: Graph.NodeIndex | undefined
181 let edgeIndex: Graph.EdgeIndex | undefined
182 Graph.mutate(decoded, (mutable) => {
183 nodeIndex = Graph.addNode(mutable, "next")
184 edgeIndex = Graph.addEdge(mutable, 0, 1, 3)
185 })
186
187 assert.strictEqual(nodeIndex, 2)
188 assert.strictEqual(edgeIndex, 1)
189 })
190
191 it("rebuilds adjacency and initializes derived caches for cyclic graphs", () => {
192 const graph = decodeDirected({
193 type: "directed",
194 nodes: [{ index: 0, data: "A" }, { index: 2, data: "B" }, { index: 4, data: "C" }],
195 edges: [
196 { index: 1, source: 0, target: 2, data: 1 },
197 { index: 3, source: 2, target: 4, data: 2 },
198 { index: 5, source: 4, target: 0, data: 3 }
199 ]
200 })
201
202 assert.deepStrictEqual(Graph.neighbors(graph, 0), [2])
203 assert.deepStrictEqual(Graph.predecessors(graph, 0), [4])
204 assert.strictEqual(Graph.isAcyclic(graph), false)
205 })
206
207 it("applies node and edge payload transformations", () => {
208 const codec = Schema.toCodecJson(Schema.Graph("directed", Schema.FiniteFromString, Schema.FiniteFromString))
209 const encoded = {
210 type: "directed",
211 nodes: [{ index: 0, data: "1" }, { index: 1, data: "2" }],
212 edges: [{ index: 0, source: 0, target: 1, data: "3" }]
213 } as const
214 const graph = Schema.decodeUnknownSync(codec)(encoded)
215
216 assert.deepStrictEqual(Array.from(graph), [[0, 1], [1, 2]])
217 assert.deepStrictEqual(Option.getOrThrow(Graph.getEdge(graph, 0)).data, 3)
218 assert.deepStrictEqual(Schema.encodeSync(codec)(graph), encoded)
219 })
220
221 it("rejects mutable graphs and the wrong graph kind", () => {
222 const mutable = Graph.beginMutation(Graph.directed<string, number>())
223 assert.throws(() => encodeDirected(mutable as never), /immutable directed Graph/)
224 assert.throws(() => encodeDirected(Graph.undirected() as never), /immutable directed Graph/)
225 assertDecodeFailure(empty("undirected"), "[\"type\"]", "Expected \"directed\"")
226 })
227
228 it("rejects invalid node and edge indexes at precise paths", () => {
229 const nodeCases = [-1, 0.5, Number.MAX_SAFE_INTEGER + 1]
230 for (const index of nodeCases) {
231 assertDecodeFailure(
232 { type: "directed", nodes: [{ index, data: "A" }], edges: [] },
233 "[\"nodes\"][0][\"index\"]"
234 )
235 }
236 const edgeCases = [-1, 0.5, Number.MAX_SAFE_INTEGER + 1]
237 for (const index of edgeCases) {
238 assertDecodeFailure({
239 type: "directed",
240 nodes: [{ index: 0, data: "A" }],
241 edges: [{ index, source: 0, target: 0, data: 1 }]
242 }, "[\"edges\"][0][\"index\"]")
243 }
244 assertDecodeFailure(
245 {
246 type: "directed",
247 nodes: [{ index: 0, data: "A" }, { index: 0, data: "B" }],
248 edges: []
249 },
250 "[\"nodes\"][1][\"index\"]",
251 "strictly increasing"
252 )
253 assertDecodeFailure(
254 {
255 type: "directed",
256 nodes: [{ index: 1, data: "A" }, { index: 0, data: "B" }],
257 edges: []
258 },
259 "[\"nodes\"][1][\"index\"]",
260 "strictly increasing"
261 )
262 assertDecodeFailure(
263 {
264 type: "directed",
265 nodes: [{ index: 0, data: "A" }],
266 edges: [
267 { index: 1, source: 0, target: 0, data: 1 },
268 { index: 1, source: 0, target: 0, data: 2 }
269 ]
270 },
271 "[\"edges\"][1][\"index\"]",
272 "strictly increasing"
273 )
274 assertDecodeFailure(
275 {
276 type: "directed",
277 nodes: [{ index: 0, data: "A" }],
278 edges: [
279 { index: 2, source: 0, target: 0, data: 1 },
280 { index: 1, source: 0, target: 0, data: 2 }
281 ]
282 },
283 "[\"edges\"][1][\"index\"]",
284 "strictly increasing"
285 )
286 })
287
288 it("rejects dangling endpoints without leaking GraphError", () => {
289 assertDecodeFailure(
290 {
291 type: "directed",
292 nodes: [{ index: 1, data: "A" }],
293 edges: [{ index: 0, source: 0, target: 1, data: 1 }]
294 },
295 "[\"edges\"][0][\"source\"]",
296 "encoded node index"
297 )
298 assertDecodeFailure(
299 {
300 type: "directed",
301 nodes: [{ index: 1, data: "A" }],
302 edges: [{ index: 0, source: 1, target: 2, data: 1 }]
303 },
304 "[\"edges\"][0][\"target\"]",
305 "encoded node index"
306 )
307 })
308
309 it("reports payload failures at array and property paths", () => {
310 assertDecodeFailure(
311 {
312 type: "directed",
313 nodes: [{ index: 0, data: null }],
314 edges: []
315 },
316 "[\"nodes\"][0][\"data\"]",
317 "Expected string"
318 )
319 assertDecodeFailure(
320 {
321 type: "directed",
322 nodes: [{ index: 0, data: "A" }],
323 edges: [{ index: 0, source: 0, target: 0, data: null }]
324 },
325 "[\"edges\"][0][\"data\"]",
326 "Expected number"
327 )
328 })
329})