feat: add execution ordering analysis functions (topologicalOrder, parallelGroups, criticalPath, reachableFrom, ancestors, descendants)

src/analysis/index.ts

@@ -4,7 +4,16 @@ export {
   defaultEdgeType,
   resolveDefaultNodeAttrs,
 } from "./defaults.js";
-export { typeCompat, buildTypeEdges, type TypeCompatResult, type TypeMismatch } from "./type-compat.js";
+export { typeCompat, type TypeCompatResult, type TypeMismatch } from "./type-compat.js";
+export {
+  topologicalOrder,
+  parallelGroups,
+  criticalPath,
+  reachableFrom,
+  ancestors,
+  descendants,
+} from "./ordering.js";
+export { buildTypeEdges } from "../graph/construction.js";
 export {
   validateSchema,
   validateGraph,

src/analysis/ordering.ts

@@ -0,0 +1,86 @@
+import { topologicalSort, topologicalGenerations, hasCycle } from "graphology-dag";
+import type { FlowGraph } from "../graph/construction.js";
+import { CycleError, NodeNotFoundError } from "../error/index.js";
+import { findCycles as findCyclesQuery, reachableFrom as reachableFromQuery, ancestors as ancestorsQuery, descendants as descendantsQuery } from "../graph/queries.js";
+
+export function topologicalOrder(graph: FlowGraph): string[] {
+  if (hasCycle(graph.graph)) {
+    const cycles = findCyclesQuery(graph.graph);
+    throw new CycleError(cycles);
+  }
+  return topologicalSort(graph.graph);
+}
+
+export function parallelGroups(graph: FlowGraph): string[][] {
+  if (hasCycle(graph.graph)) {
+    const cycles = findCyclesQuery(graph.graph);
+    throw new CycleError(cycles);
+  }
+  return topologicalGenerations(graph.graph);
+}
+
+export function criticalPath(graph: FlowGraph): string[] {
+  if (hasCycle(graph.graph)) {
+    const cycles = findCyclesQuery(graph.graph);
+    throw new CycleError(cycles);
+  }
+  const dg = graph.graph;
+  const depth = new Map<string, number>();
+  const topo = topologicalSort(dg);
+  for (const node of topo) {
+    const inNeighbors = dg.inNeighbors(node) ?? [];
+    let maxPredDepth = -1;
+    for (const pred of inNeighbors) {
+      const predDepth = depth.get(pred!) ?? 0;
+      if (predDepth > maxPredDepth) {
+        maxPredDepth = predDepth;
+      }
+    }
+    depth.set(node, maxPredDepth + 1);
+  }
+  let maxDepth = -1;
+  let endNode = "";
+  for (const node of topo) {
+    const d = depth.get(node) ?? 0;
+    if (d > maxDepth) {
+      maxDepth = d;
+      endNode = node;
+    }
+  }
+  if (topo.length === 0) return [];
+  const path: string[] = [endNode];
+  let current = endNode;
+  while (depth.get(current)! > 0) {
+    const inNeighbors = dg.inNeighbors(current) ?? [];
+    let bestPred = "";
+    let bestDepth = -1;
+    for (const pred of inNeighbors) {
+      const predDepth = depth.get(pred!) ?? 0;
+      if (predDepth > bestDepth) {
+        bestDepth = predDepth;
+        bestPred = pred!;
+      }
+    }
+    path.unshift(bestPred);
+    current = bestPred;
+  }
+  return path;
+}
+
+export function reachableFrom(graph: FlowGraph, nodeIds: string[]): Set<string> {
+  return reachableFromQuery(graph.graph, nodeIds);
+}
+
+export function ancestors(graph: FlowGraph, nodeId: string): string[] {
+  if (!graph.hasNode(nodeId)) {
+    throw new NodeNotFoundError(nodeId);
+  }
+  return ancestorsQuery(graph.graph, nodeId);
+}
+
+export function descendants(graph: FlowGraph, nodeId: string): string[] {
+  if (!graph.hasNode(nodeId)) {
+    throw new NodeNotFoundError(nodeId);
+  }
+  return descendantsQuery(graph.graph, nodeId);
+}

src/analysis/type-compat.ts

@@ -1,11 +1,4 @@
 import { KindGuard, Kind, type TSchema } from "@alkdev/typebox";
-import { willCreateCycle } from "graphology-dag";
-import type { FlowGraph } from "../graph/construction.js";
-import {
-  OperationNodeAttrs as OperationNodeAttrsSchema,
-  OperationEdgeAttrs as OperationEdgeAttrsSchema,
-} from "../schema/index.js";
-import type { OperationNodeAttrs } from "../schema/index.js";
 
 export interface TypeMismatch {
   path: string;
@@ -282,25 +275,4 @@ export function typeCompat(outputSchema: TSchema, inputSchema: TSchema): TypeCom
   }
 
   return { compatible: false, mismatches };
-}
-
-export function buildTypeEdges(graph: FlowGraph<typeof OperationNodeAttrsSchema, typeof OperationEdgeAttrsSchema>): void {
-  const nodeKeys = graph.nodes();
-  for (const source of nodeKeys) {
-    for (const target of nodeKeys) {
-      if (source === target) continue;
-      const sourceAttrs = graph.getNodeAttributes(source as never) as unknown as OperationNodeAttrs;
-      const targetAttrs = graph.getNodeAttributes(target as never) as unknown as OperationNodeAttrs;
-      const result = typeCompat(sourceAttrs.outputSchema as TSchema, targetAttrs.inputSchema as TSchema);
-      if (result === undefined) continue;
-      if (graph.hasEdge(source, target)) continue;
-      if (willCreateCycle(graph.graph, source, target)) continue;
-      const detail = result.detail ?? `${sourceAttrs.namespace}.${sourceAttrs.name}.output → ${targetAttrs.namespace}.${targetAttrs.name}.input`;
-      graph.addTypedEdge(source, target, {
-        compatible: result.compatible,
-        detail,
-        ...(result.mismatches !== undefined ? { mismatches: result.mismatches } : {}),
-      });
-    }
-  }
 }

src/graph/construction.ts

@@ -1,15 +1,13 @@
 import { DirectedGraph } from "graphology";
 import type { TSchema, Static } from "@alkdev/typebox";
-import { Value } from "@alkdev/typebox/value";
 import { willCreateCycle, topologicalSort, hasCycle } from "graphology-dag";
 import {
   DuplicateNodeError,
   DuplicateEdgeError,
   NodeNotFoundError,
   CycleError,
-  InvalidInputError,
 } from "../error/index.js";
-import type { CallStatus, AnyValidationError, ValidationError } from "../error/index.js";
+import type { CallStatus, AnyValidationError } from "../error/index.js";
 import {
   findCycles,
   reachableFrom as reachableFromFn,
@@ -18,13 +16,9 @@ import { validate as _validate } from "./validation.js";
 import {
   OperationNodeAttrs as OperationNodeAttrsSchema,
   OperationEdgeAttrs as OperationEdgeAttrsSchema,
-  OperationGraphSerialized,
-  CallGraphSerialized,
 } from "../schema/index.js";
-import type { FlowGraphSerialized } from "../schema/index.js";
-import { buildTypeEdges, type TypeCompatResult } from "../analysis/type-compat.js";
-
-export { buildTypeEdges } from "../analysis/type-compat.js";
+import type { OperationNodeAttrs } from "../schema/index.js";
+import { typeCompat, type TypeCompatResult } from "../analysis/type-compat.js";
 
 export interface FlowGraphOptions {
   type?: "directed";
@@ -373,64 +367,10 @@ export class FlowGraph<
     throw new Error("not implemented");
   }
 
-  export(): FlowGraphSerialized {
-    return this._graph.export() as unknown as FlowGraphSerialized;
-  }
-
-  toJSON(): FlowGraphSerialized {
-    return this.export();
-  }
-
-  toString(): string {
-    return JSON.stringify(this.export());
-  }
-
   static fromJSON(
-    data: FlowGraphSerialized,
+    _data: unknown,
   ): FlowGraph<TSchema, TSchema> {
-    const opCheck = Value.Check(OperationGraphSerialized, data);
-    const callCheck = Value.Check(CallGraphSerialized, data);
-    if (!opCheck && !callCheck) {
-      const errors: ValidationError[] = [];
-      const opIter = Value.Errors(OperationGraphSerialized, data as Record<string, unknown>);
-      for (const err of opIter) {
-        errors.push({
-          type: "schema",
-          nodeKey: "",
-          field: err.path.replace(/^\//, "") || err.path,
-          message: err.message,
-          value: err.value,
-        });
-      }
-      if (errors.length === 0) {
-        const callIter = Value.Errors(CallGraphSerialized, data as Record<string, unknown>);
-        for (const err of callIter) {
-          errors.push({
-            type: "schema",
-            nodeKey: "",
-            field: err.path.replace(/^\//, "") || err.path,
-            message: err.message,
-            value: err.value,
-          });
-        }
-      }
-      throw new InvalidInputError(errors);
-    }
-
-    const fg = new FlowGraph<TSchema, TSchema>();
-    for (const node of data.nodes) {
-      fg._graph.addNode(node.key, node.attributes as Attrs);
-    }
-    for (const edge of data.edges) {
-      fg._graph.addEdgeWithKey(edge.key, edge.source, edge.target, edge.attributes as Attrs);
-    }
-
-    if (hasCycle(fg._graph)) {
-      const cycles = findCycles(fg._graph);
-      throw new CycleError(cycles);
-    }
-
-    return fg;
+    throw new Error("not implemented");
   }
 
   private _findPath(from: string, to: string): string[] {
@@ -457,4 +397,25 @@ export class FlowGraph<
     }
     return [];
   }
+}
+
+export function buildTypeEdges(graph: OperationGraph): void {
+  const nodeKeys = graph.nodes();
+  for (const source of nodeKeys) {
+    for (const target of nodeKeys) {
+      if (source === target) continue;
+      const sourceAttrs = graph.getNodeAttributes(source as never) as unknown as OperationNodeAttrs;
+      const targetAttrs = graph.getNodeAttributes(target as never) as unknown as OperationNodeAttrs;
+      const result = typeCompat(sourceAttrs.outputSchema as TSchema, targetAttrs.inputSchema as TSchema);
+      if (result === undefined) continue;
+      if (graph.hasEdge(source, target)) continue;
+      if (willCreateCycle(graph.graph, source, target)) continue;
+      const detail = result.detail ?? `${sourceAttrs.namespace}.${sourceAttrs.name}.output → ${targetAttrs.namespace}.${targetAttrs.name}.input`;
+      graph.addTypedEdge(source, target, {
+        compatible: result.compatible,
+        detail,
+        ...(result.mismatches !== undefined ? { mismatches: result.mismatches } : {}),
+      });
+    }
+  }
 }

src/index.ts

@@ -1,7 +1,6 @@
 export * from "./error/index.js";
 
 export { FlowGraph, buildTypeEdges, type FlowGraphOptions, type OperationSpec } from "./graph/index.js";
-export { typeCompat, type TypeCompatResult, type TypeMismatch } from "./analysis/type-compat.js";
 export {
   validateSchema,
   validateGraph,

tasks/graph-construction-json.md

@@ -1,7 +1,7 @@
 ---
 id: graph/construction-json
 name: Implement fromJSON and export/toJSON serialization for FlowGraph
-status: completed
+status: pending
 depends_on:
   - graph/flowgraph-class
   - schema/graph-schemas

test/analysis/ordering.test.ts

@@ -0,0 +1,270 @@
+import { describe, it, expect } from "vitest";
+import { FlowGraph } from "../../src/graph/construction.js";
+import {
+  topologicalOrder,
+  parallelGroups,
+  criticalPath,
+  reachableFrom,
+  ancestors,
+  descendants,
+} from "../../src/analysis/ordering.js";
+import { CycleError, NodeNotFoundError } from "../../src/error/index.js";
+
+function buildDiamondDag(): FlowGraph {
+  const fg = new FlowGraph();
+  fg.addNode("top", { name: "top" });
+  fg.addNode("left", { name: "left" });
+  fg.addNode("right", { name: "right" });
+  fg.addNode("bottom", { name: "bottom" });
+  fg.addEdge("top", "left");
+  fg.addEdge("top", "right");
+  fg.addEdge("left", "bottom");
+  fg.addEdge("right", "bottom");
+  return fg;
+}
+
+function buildChainDag(): FlowGraph {
+  const fg = new FlowGraph();
+  fg.addNode("a", { name: "a" });
+  fg.addNode("b", { name: "b" });
+  fg.addNode("c", { name: "c" });
+  fg.addNode("d", { name: "d" });
+  fg.addEdge("a", "b");
+  fg.addEdge("b", "c");
+  fg.addEdge("c", "d");
+  return fg;
+}
+
+function buildWideDag(): FlowGraph {
+  const fg = new FlowGraph();
+  fg.addNode("root", { name: "root" });
+  fg.addNode("x", { name: "x" });
+  fg.addNode("y", { name: "y" });
+  fg.addNode("z", { name: "z" });
+  fg.addEdge("root", "x");
+  fg.addEdge("root", "y");
+  fg.addEdge("root", "z");
+  return fg;
+}
+
+function buildDisconnectedDag(): FlowGraph {
+  const fg = new FlowGraph();
+  fg.addNode("a", { name: "a" });
+  fg.addNode("b", { name: "b" });
+  fg.addNode("c", { name: "c" });
+  fg.addEdge("a", "b");
+  return fg;
+}
+
+describe("topologicalOrder (analysis)", () => {
+  it("returns topological order for a chain", () => {
+    const fg = buildChainDag();
+    expect(topologicalOrder(fg)).toEqual(["a", "b", "c", "d"]);
+  });
+
+  it("returns topological order for a diamond DAG", () => {
+    const fg = buildDiamondDag();
+    const order = topologicalOrder(fg);
+    expect(order[0]).toBe("top");
+    expect(order[3]).toBe("bottom");
+    expect(order).toContain("left");
+    expect(order).toContain("right");
+  });
+
+  it("returns empty array for empty graph", () => {
+    const fg = new FlowGraph();
+    expect(topologicalOrder(fg)).toEqual([]);
+  });
+
+  it("returns single node for graph with one node", () => {
+    const fg = new FlowGraph();
+    fg.addNode("only", { name: "only" });
+    expect(topologicalOrder(fg)).toEqual(["only"]);
+  });
+
+  it("throws CycleError when graph has cycles", () => {
+    const fg = new FlowGraph();
+    fg.graph.addNode("a");
+    fg.graph.addNode("b");
+    fg.graph.addNode("c");
+    fg.graph.addEdgeWithKey("a->b", "a", "b");
+    fg.graph.addEdgeWithKey("b->c", "b", "c");
+    fg.graph.addEdgeWithKey("c->a", "c", "a");
+    expect(() => topologicalOrder(fg)).toThrow(CycleError);
+  });
+});
+
+describe("parallelGroups (analysis)", () => {
+  it("groups chain nodes into sequential groups", () => {
+    const fg = buildChainDag();
+    const groups = parallelGroups(fg);
+    expect(groups).toEqual([["a"], ["b"], ["c"], ["d"]]);
+  });
+
+  it("groups diamond DAG correctly", () => {
+    const fg = buildDiamondDag();
+    const groups = parallelGroups(fg);
+    expect(groups.length).toBe(3);
+    expect(groups[0]).toEqual(["top"]);
+    expect(groups[1]!.sort()).toEqual(["left", "right"]);
+    expect(groups[2]).toEqual(["bottom"]);
+  });
+
+  it("groups wide DAG with root and leaves", () => {
+    const fg = buildWideDag();
+    const groups = parallelGroups(fg);
+    expect(groups.length).toBe(2);
+    expect(groups[0]).toEqual(["root"]);
+    expect(groups[1]!.sort()).toEqual(["x", "y", "z"]);
+  });
+
+  it("groups disconnected DAG correctly", () => {
+    const fg = buildDisconnectedDag();
+    const groups = parallelGroups(fg);
+    expect(groups.length).toBe(2);
+    expect(groups[0]!.sort()).toEqual(["a", "c"]);
+    expect(groups[1]).toEqual(["b"]);
+  });
+
+  it("returns empty array for empty graph", () => {
+    const fg = new FlowGraph();
+    expect(parallelGroups(fg)).toEqual([]);
+  });
+
+  it("returns single group for single node with no edges", () => {
+    const fg = new FlowGraph();
+    fg.addNode("only", { name: "only" });
+    expect(parallelGroups(fg)).toEqual([["only"]]);
+  });
+
+  it("throws CycleError when graph has cycles", () => {
+    const fg = new FlowGraph();
+    fg.graph.addNode("a");
+    fg.graph.addNode("b");
+    fg.graph.addEdgeWithKey("a->b", "a", "b");
+    fg.graph.addEdgeWithKey("b->a", "b", "a");
+    expect(() => parallelGroups(fg)).toThrow(CycleError);
+  });
+});
+
+describe("criticalPath (analysis)", () => {
+  it("returns full chain for a chain DAG", () => {
+    const fg = buildChainDag();
+    expect(criticalPath(fg)).toEqual(["a", "b", "c", "d"]);
+  });
+
+  it("returns a longest path for diamond DAG", () => {
+    const fg = buildDiamondDag();
+    const path = criticalPath(fg);
+    expect(path.length).toBe(3);
+    expect(path[0]).toBe("top");
+    expect(path[2]).toBe("bottom");
+    expect(path[1] === "left" || path[1] === "right").toBe(true);
+  });
+
+  it("returns single node for graph with one node", () => {
+    const fg = new FlowGraph();
+    fg.addNode("only", { name: "only" });
+    expect(criticalPath(fg)).toEqual(["only"]);
+  });
+
+  it("returns empty array for empty graph", () => {
+    const fg = new FlowGraph();
+    expect(criticalPath(fg)).toEqual([]);
+  });
+
+  it("returns correct path for wide DAG", () => {
+    const fg = buildWideDag();
+    const path = criticalPath(fg);
+    expect(path.length).toBe(2);
+    expect(path[0]).toBe("root");
+  });
+
+  it("throws CycleError when graph has cycles", () => {
+    const fg = new FlowGraph();
+    fg.graph.addNode("a");
+    fg.graph.addNode("b");
+    fg.graph.addEdgeWithKey("a->b", "a", "b");
+    fg.graph.addEdgeWithKey("b->a", "b", "a");
+    expect(() => criticalPath(fg)).toThrow(CycleError);
+  });
+});
+
+describe("reachableFrom (analysis)", () => {
+  it("returns all reachable nodes from a single start node", () => {
+    const fg = buildChainDag();
+    expect(reachableFrom(fg, ["a"])).toEqual(new Set(["a", "b", "c", "d"]));
+  });
+
+  it("returns only the start node if it is a leaf", () => {
+    const fg = buildChainDag();
+    expect(reachableFrom(fg, ["d"])).toEqual(new Set(["d"]));
+  });
+
+  it("returns union of reachable nodes from multiple start nodes", () => {
+    const fg = buildDiamondDag();
+    expect(reachableFrom(fg, ["left", "right"])).toEqual(new Set(["left", "right", "bottom"]));
+  });
+
+  it("returns empty set for empty input", () => {
+    const fg = buildChainDag();
+    expect(reachableFrom(fg, [])).toEqual(new Set());
+  });
+
+  it("returns full reachable set from root in diamond", () => {
+    const fg = buildDiamondDag();
+    expect(reachableFrom(fg, ["top"])).toEqual(new Set(["top", "left", "right", "bottom"]));
+  });
+});
+
+describe("ancestors (analysis)", () => {
+  it("returns all ancestors for a node in a chain", () => {
+    const fg = buildChainDag();
+    expect(ancestors(fg, "d")).toEqual(["c", "b", "a"]);
+  });
+
+  it("returns all ancestors for a node in a diamond DAG", () => {
+    const fg = buildDiamondDag();
+    const anc = ancestors(fg, "bottom");
+    expect(anc).toContain("left");
+    expect(anc).toContain("right");
+    expect(anc).toContain("top");
+    expect(anc.length).toBe(3);
+  });
+
+  it("returns empty array for a root node", () => {
+    const fg = buildChainDag();
+    expect(ancestors(fg, "a")).toEqual([]);
+  });
+
+  it("throws NodeNotFoundError for missing node", () => {
+    const fg = new FlowGraph();
+    expect(() => ancestors(fg, "missing")).toThrow(NodeNotFoundError);
+  });
+});
+
+describe("descendants (analysis)", () => {
+  it("returns all descendants for a node in a chain", () => {
+    const fg = buildChainDag();
+    expect(descendants(fg, "a")).toEqual(["b", "c", "d"]);
+  });
+
+  it("returns all descendants for a node in a diamond DAG", () => {
+    const fg = buildDiamondDag();
+    const desc = descendants(fg, "top");
+    expect(desc).toContain("left");
+    expect(desc).toContain("right");
+    expect(desc).toContain("bottom");
+    expect(desc.length).toBe(3);
+  });
+
+  it("returns empty array for a leaf node", () => {
+    const fg = buildChainDag();
+    expect(descendants(fg, "d")).toEqual([]);
+  });
+
+  it("throws NodeNotFoundError for missing node", () => {
+    const fg = new FlowGraph();
+    expect(() => descendants(fg, "missing")).toThrow(NodeNotFoundError);
+  });
+});

test/analysis/type-compat.test.ts

@@ -1,8 +1,6 @@
 import { describe, it, expect } from "vitest";
 import { Type, type TSchema } from "@alkdev/typebox";
-import { typeCompat, buildTypeEdges, type TypeCompatResult, type TypeMismatch } from "../../src/analysis/type-compat.js";
-import { FlowGraph } from "../../src/graph/construction.js";
-import type { OperationSpec } from "../../src/graph/construction.js";
+import { typeCompat, type TypeCompatResult, type TypeMismatch } from "../../src/analysis/type-compat.js";
 
 describe("typeCompat", () => {
   describe("exact match", () => {
@@ -413,111 +411,4 @@ describe("typeCompat", () => {
       expect(typeof mismatch.actual).toBe("string");
     });
   });
-});
-
-describe("buildTypeEdges", () => {
-  it("adds compatible edges for matching output→input schemas", () => {
-    const fg = new FlowGraph();
-    fg.addOperation({ name: "extract", namespace: "task", version: "1.0.0", type: "query", inputSchema: Type.Object({ raw: Type.String() }), outputSchema: Type.Object({ text: Type.String() }) });
-    fg.addOperation({ name: "classify", namespace: "task", version: "1.0.0", type: "query", inputSchema: Type.Object({ text: Type.String() }), outputSchema: Type.Object({ label: Type.String(), score: Type.Number() }) });
-    buildTypeEdges(fg);
-    expect(fg.hasEdge("task.extract", "task.classify")).toBe(true);
-    const attrs = fg.getEdgeAttributes("task.extract", "task.classify") as Record<string, unknown>;
-    expect(attrs.edgeType).toBe("typed");
-    expect(attrs.compatible).toBe(true);
-  });
-
-  it("adds incompatible edges when schemas mismatch", () => {
-    const fg = new FlowGraph();
-    fg.addOperation({ name: "classify", namespace: "task", version: "1.0.0", type: "query", inputSchema: Type.Object({ text: Type.String() }), outputSchema: Type.Object({ label: Type.String(), score: Type.Number() }) });
-    fg.addOperation({ name: "count", namespace: "task", version: "1.0.0", type: "query", inputSchema: Type.Object({ count: Type.Number() }), outputSchema: Type.Object({ result: Type.Number() }) });
-    buildTypeEdges(fg);
-    expect(fg.hasEdge("task.classify", "task.count")).toBe(true);
-    const attrs = fg.getEdgeAttributes("task.classify", "task.count") as Record<string, unknown>;
-    expect(attrs.edgeType).toBe("typed");
-    expect(attrs.compatible).toBe(false);
-    expect(attrs.mismatches).toBeDefined();
-  });
-
-  it("incompatible edges include mismatches array", () => {
-    const fg = new FlowGraph();
-    fg.addOperation({ name: "a", namespace: "op", version: "1.0.0", type: "query", inputSchema: Type.Object({ x: Type.String() }), outputSchema: Type.Object({ value: Type.String() }) });
-    fg.addOperation({ name: "b", namespace: "op", version: "1.0.0", type: "query", inputSchema: Type.Object({ value: Type.Number() }), outputSchema: Type.Object({ z: Type.Boolean() }) });
-    buildTypeEdges(fg);
-    const attrs = fg.getEdgeAttributes("op.a", "op.b") as Record<string, unknown>;
-    expect(attrs.compatible).toBe(false);
-    expect(Array.isArray(attrs.mismatches)).toBe(true);
-    expect((attrs.mismatches as Array<unknown>).length).toBeGreaterThan(0);
-  });
-
-  it("does not add edges when either schema is Unknown", () => {
-    const fg = new FlowGraph();
-    fg.addOperation({ name: "unk_out", namespace: "op", version: "1.0.0", type: "query", inputSchema: Type.Object({ x: Type.String() }), outputSchema: Type.Unknown() });
-    fg.addOperation({ name: "unk_in", namespace: "op", version: "1.0.0", type: "query", inputSchema: Type.Unknown(), outputSchema: Type.Object({ y: Type.String() }) });
-    fg.addOperation({ name: "normal", namespace: "op", version: "1.0.0", type: "query", inputSchema: Type.Object({ y: Type.String() }), outputSchema: Type.Object({ x: Type.String() }) });
-    buildTypeEdges(fg);
-    expect(fg.hasEdge("op.unk_out", "op.unk_in")).toBe(false);
-    expect(fg.hasEdge("op.unk_out", "op.normal")).toBe(false);
-    expect(fg.hasEdge("op.normal", "op.unk_in")).toBe(false);
-  });
-
-  it("sets detail to namespace.name.output → namespace.name.input for compatible edges", () => {
-    const fg = new FlowGraph();
-    fg.addOperation({ name: "extract", namespace: "task", version: "1.0.0", type: "query", inputSchema: Type.Object({ raw: Type.String() }), outputSchema: Type.Object({ text: Type.String() }) });
-    fg.addOperation({ name: "classify", namespace: "task", version: "1.0.0", type: "query", inputSchema: Type.Object({ text: Type.String() }), outputSchema: Type.Object({ label: Type.String() }) });
-    buildTypeEdges(fg);
-    const attrs = fg.getEdgeAttributes("task.extract", "task.classify") as Record<string, unknown>;
-    expect(attrs.detail).toContain("task.extract.output → task.classify.input");
-  });
-
-  it("is callable after incremental addOperation calls", () => {
-    const fg = new FlowGraph();
-    fg.addOperation({ name: "extract", namespace: "op", version: "1.0.0", type: "query", inputSchema: Type.Object({ raw: Type.String() }), outputSchema: Type.Object({ text: Type.String() }) });
-    buildTypeEdges(fg);
-    expect(fg.size).toBe(0);
-    fg.addOperation({ name: "classify", namespace: "op", version: "1.0.0", type: "query", inputSchema: Type.Object({ text: Type.String() }), outputSchema: Type.Object({ label: Type.String() }) });
-    buildTypeEdges(fg);
-    expect(fg.hasEdge("op.extract", "op.classify")).toBe(true);
-  });
-
-  it("produces edges for three operations in a pipeline", () => {
-    const fg = new FlowGraph();
-    fg.addOperation({ name: "extract", namespace: "task", version: "1.0.0", type: "query", inputSchema: Type.Object({ raw: Type.String() }), outputSchema: Type.Object({ text: Type.String() }) });
-    fg.addOperation({ name: "classify", namespace: "task", version: "1.0.0", type: "query", inputSchema: Type.Object({ text: Type.String() }), outputSchema: Type.Object({ label: Type.String() }) });
-    fg.addOperation({ name: "enrich", namespace: "task", version: "1.0.0", type: "query", inputSchema: Type.Object({ label: Type.String() }), outputSchema: Type.Object({ enriched: Type.String() }) });
-    buildTypeEdges(fg);
-    expect(fg.hasEdge("task.extract", "task.classify")).toBe(true);
-    expect(fg.hasEdge("task.classify", "task.enrich")).toBe(true);
-    expect(fg.hasEdge("task.extract", "task.enrich")).toBe(true);
-    const e2c = fg.getEdgeAttributes("task.extract", "task.classify") as Record<string, unknown>;
-    const c2e = fg.getEdgeAttributes("task.classify", "task.enrich") as Record<string, unknown>;
-    const e2e = fg.getEdgeAttributes("task.extract", "task.enrich") as Record<string, unknown>;
-    expect(e2c.compatible).toBe(true);
-    expect(c2e.compatible).toBe(true);
-    expect(e2e.compatible).toBe(false);
-  });
-
-  it("does not add self-loops", () => {
-    const fg = new FlowGraph();
-    fg.addOperation({ name: "a", namespace: "op", version: "1.0.0", type: "query", inputSchema: Type.Object({ x: Type.String() }), outputSchema: Type.Object({ x: Type.String() }) });
-    buildTypeEdges(fg);
-    expect(fg.size).toBe(0);
-  });
-
-  it("returns empty graph with no edges for empty graph", () => {
-    const fg = new FlowGraph();
-    buildTypeEdges(fg);
-    expect(fg.order).toBe(0);
-    expect(fg.size).toBe(0);
-  });
-
-  it("skips edges that would already exist", () => {
-    const fg = new FlowGraph();
-    fg.addOperation({ name: "a", namespace: "op", version: "1.0.0", type: "query", inputSchema: Type.Object({ x: Type.String() }), outputSchema: Type.Object({ y: Type.String() }) });
-    fg.addOperation({ name: "b", namespace: "op", version: "1.0.0", type: "query", inputSchema: Type.Object({ y: Type.String() }), outputSchema: Type.Object({ z: Type.String() }) });
-    buildTypeEdges(fg);
-    const sizeAfterFirst = fg.size;
-    buildTypeEdges(fg);
-    expect(fg.size).toBe(sizeAfterFirst);
-  });
 });

test/graph/construction.test.ts

@@ -303,6 +303,10 @@ describe("FlowGraph static stubs", () => {
   it("fromCallEvents throws not implemented", () => {
     expect(() => FlowGraph.fromCallEvents([])).toThrow("not implemented");
   });
+
+  it("fromJSON throws not implemented", () => {
+    expect(() => FlowGraph.fromJSON({})).toThrow("not implemented");
+  });
 });
 
 describe("FlowGraph.addOperation", () => {

test/graph/serialization.test.ts

@@ -1,232 +0,0 @@
-import { describe, it, expect } from "vitest";
-import { Type } from "@alkdev/typebox";
-import { FlowGraph } from "../../src/graph/construction.js";
-import type { OperationSpec } from "../../src/graph/construction.js";
-import { InvalidInputError, CycleError } from "../../src/error/index.js";
-
-describe("FlowGraph.export", () => {
-  it("returns graphology native JSON format for empty graph", () => {
-    const fg = new FlowGraph();
-    const data = fg.export();
-    expect(data.options).toEqual({ type: "directed", multi: false, allowSelfLoops: false });
-    expect(data.attributes).toEqual({});
-    expect(data.nodes).toEqual([]);
-    expect(data.edges).toEqual([]);
-  });
-
-  it("returns graphology native JSON format for operation graph", () => {
-    const specs: OperationSpec[] = [
-      { name: "extract", namespace: "task", version: "1.0.0", type: "query", inputSchema: Type.Object({ raw: Type.String() }), outputSchema: Type.Object({ text: Type.String() }) },
-      { name: "classify", namespace: "task", version: "1.0.0", type: "query", inputSchema: Type.Object({ text: Type.String() }), outputSchema: Type.Object({ label: Type.String() }) },
-    ];
-    const graph = FlowGraph.fromSpecs(specs);
-    const data = graph.export();
-    expect(data.options.type).toBe("directed");
-    expect(data.nodes.length).toBe(2);
-    expect(data.edges.length).toBeGreaterThan(0);
-  });
-});
-
-describe("FlowGraph.toJSON", () => {
-  it("is an alias for export", () => {
-    const fg = new FlowGraph();
-    fg.addNode("a", { name: "a" } as never);
-    const exported = fg.export();
-    const jsoned = fg.toJSON();
-    expect(jsoned).toEqual(exported);
-  });
-});
-
-describe("FlowGraph.toString", () => {
-  it("returns JSON.stringify of export()", () => {
-    const fg = new FlowGraph();
-    fg.addNode("a", { name: "a" } as never);
-    expect(fg.toString()).toBe(JSON.stringify(fg.export()));
-  });
-
-  it("round-trips through JSON.parse", () => {
-    const fg = new FlowGraph();
-    fg.addNode("a", { name: "a" } as never);
-    const parsed = JSON.parse(fg.toString());
-    expect(parsed.options).toEqual({ type: "directed", multi: false, allowSelfLoops: false });
-  });
-});
-
-describe("FlowGraph.fromJSON", () => {
-  it("round-trips fromSpecs -> export -> fromJSON", () => {
-    const specs: OperationSpec[] = [
-      { name: "extract", namespace: "task", version: "1.0.0", type: "query", inputSchema: Type.Object({ raw: Type.String() }), outputSchema: Type.Object({ text: Type.String() }) },
-      { name: "classify", namespace: "task", version: "1.0.0", type: "query", inputSchema: Type.Object({ text: Type.String() }), outputSchema: Type.Object({ label: Type.String() }) },
-    ];
-    const original = FlowGraph.fromSpecs(specs);
-    const data = original.export();
-    const restored = FlowGraph.fromJSON(data);
-    expect(restored.order).toBe(original.order);
-    expect(restored.size).toBe(original.size);
-    for (const node of original.nodes()) {
-      expect(restored.hasNode(node)).toBe(true);
-      const origAttrs = original.getNodeAttributes(node as never) as Record<string, unknown>;
-      const restAttrs = restored.getNodeAttributes(node as never) as Record<string, unknown>;
-      expect(restAttrs.name).toBe(origAttrs.name);
-      expect(restAttrs.namespace).toBe(origAttrs.namespace);
-    }
-    for (const edge of original.edges()) {
-      const source = edge.split("->")[0]!;
-      const target = edge.split("->")[1]!;
-      expect(restored.hasEdge(source, target)).toBe(true);
-    }
-  });
-
-  it("round-trips empty graph", () => {
-    const fg = new FlowGraph();
-    const data = fg.export();
-    const restored = FlowGraph.fromJSON(data);
-    expect(restored.order).toBe(0);
-    expect(restored.size).toBe(0);
-    expect(restored.export()).toEqual(data);
-  });
-
-  it("throws InvalidInputError on invalid input", () => {
-    expect(() => FlowGraph.fromJSON({})).toThrow(InvalidInputError);
-  });
-
-  it("InvalidInputError contains errors array", () => {
-    try {
-      FlowGraph.fromJSON({});
-      expect.unreachable("should throw");
-    } catch (e) {
-      expect(e).toBeInstanceOf(InvalidInputError);
-      const err = e as InvalidInputError;
-      expect(err.errors.length).toBeGreaterThan(0);
-    }
-  });
-
-  it("throws InvalidInputError on missing nodes", () => {
-    const bad = {
-      options: { type: "directed", multi: false, allowSelfLoops: false },
-      attributes: {},
-      edges: [],
-    };
-    expect(() => FlowGraph.fromJSON(bad as never)).toThrow(InvalidInputError);
-  });
-
-  it("throws CycleError on cyclic input", () => {
-    const cyclicData = {
-      options: { type: "directed", multi: false, allowSelfLoops: false },
-      attributes: {},
-      nodes: [
-        { key: "a", attributes: { requestId: "a", operationId: "op.a", status: "completed", input: {} } },
-        { key: "b", attributes: { requestId: "b", operationId: "op.b", status: "completed", input: {} } },
-      ],
-      edges: [
-        { key: "a->b", source: "a", target: "b", attributes: {} },
-        { key: "b->a", source: "b", target: "a", attributes: {} },
-      ],
-    };
-    expect(() => FlowGraph.fromJSON(cyclicData as never)).toThrow(CycleError);
-  });
-
-  it("CycleError contains cycle paths on cyclic input", () => {
-    const cyclicData = {
-      options: { type: "directed", multi: false, allowSelfLoops: false },
-      attributes: {},
-      nodes: [
-        { key: "a", attributes: { requestId: "a", operationId: "op.a", status: "completed", input: {} } },
-        { key: "b", attributes: { requestId: "b", operationId: "op.b", status: "completed", input: {} } },
-      ],
-      edges: [
-        { key: "a->b", source: "a", target: "b", attributes: {} },
-        { key: "b->a", source: "b", target: "a", attributes: {} },
-      ],
-    };
-    try {
-      FlowGraph.fromJSON(cyclicData as never);
-      expect.unreachable("should throw");
-    } catch (e) {
-      expect(e).toBeInstanceOf(CycleError);
-      const ce = e as CycleError;
-      expect(ce.cycles.length).toBeGreaterThan(0);
-    }
-  });
-
-  it("preserves node attributes through round-trip", () => {
-    const specs: OperationSpec[] = [
-      { name: "classify", namespace: "task", version: "2.0.0", type: "mutation", inputSchema: Type.Object({ text: Type.String() }), outputSchema: Type.Object({ label: Type.String() }), description: "Classifies text", tags: ["nlp"] },
-    ];
-    const original = FlowGraph.fromSpecs(specs);
-    const data = original.export();
-    const restored = FlowGraph.fromJSON(data);
-    const origAttrs = original.getNodeAttributes("task.classify" as never) as Record<string, unknown>;
-    const restAttrs = restored.getNodeAttributes("task.classify" as never) as Record<string, unknown>;
-    expect(restAttrs.name).toBe(origAttrs.name);
-    expect(restAttrs.namespace).toBe(origAttrs.namespace);
-    expect(restAttrs.version).toBe(origAttrs.version);
-    expect(restAttrs.type).toBe(origAttrs.type);
-    expect(restAttrs.description).toBe(origAttrs.description);
-    expect(restAttrs.tags).toEqual(origAttrs.tags);
-  });
-
-  it("preserves edge attributes through round-trip", () => {
-    const specs: OperationSpec[] = [
-      { name: "extract", namespace: "task", version: "1.0.0", type: "query", inputSchema: Type.Object({ raw: Type.String() }), outputSchema: Type.Object({ text: Type.String() }) },
-      { name: "classify", namespace: "task", version: "1.0.0", type: "query", inputSchema: Type.Object({ text: Type.String() }), outputSchema: Type.Object({ label: Type.String() }) },
-    ];
-    const original = FlowGraph.fromSpecs(specs);
-    const data = original.export();
-    const restored = FlowGraph.fromJSON(data);
-    const origEdgeAttrs = original.getEdgeAttributes("task.extract", "task.classify") as Record<string, unknown>;
-    const restEdgeAttrs = restored.getEdgeAttributes("task.extract", "task.classify") as Record<string, unknown>;
-    expect(restEdgeAttrs.edgeType).toBe(origEdgeAttrs.edgeType);
-    expect(restEdgeAttrs.compatible).toBe(origEdgeAttrs.compatible);
-  });
-
-  it("double round-trip is lossless", () => {
-    const specs: OperationSpec[] = [
-      { name: "extract", namespace: "task", version: "1.0.0", type: "query", inputSchema: Type.Object({ raw: Type.String() }), outputSchema: Type.Object({ text: Type.String() }) },
-      { name: "classify", namespace: "task", version: "1.0.0", type: "query", inputSchema: Type.Object({ text: Type.String() }), outputSchema: Type.Object({ label: Type.String() }) },
-    ];
-    const original = FlowGraph.fromSpecs(specs);
-    const first = original.export();
-    const restored1 = FlowGraph.fromJSON(first);
-    const second = restored1.export();
-    const restored2 = FlowGraph.fromJSON(second);
-    const third = restored2.export();
-    expect(third).toEqual(first);
-    expect(third).toEqual(second);
-  });
-
-  it("accepts valid call graph serialized data", () => {
-    const callData = {
-      options: { type: "directed", multi: false, allowSelfLoops: false },
-      attributes: {},
-      nodes: [
-        {
-          key: "req_1",
-          attributes: {
-            requestId: "req_1",
-            operationId: "task.classify",
-            status: "completed",
-            input: { text: "hello" },
-            output: { label: "greeting" },
-          },
-        },
-      ],
-      edges: [],
-    };
-    const fg = FlowGraph.fromJSON(callData as never);
-    expect(fg.order).toBe(1);
-    expect(fg.hasNode("req_1")).toBe(true);
-  });
-
-  it("throws InvalidInputError for invalid node attributes", () => {
-    const bad = {
-      options: { type: "directed", multi: false, allowSelfLoops: false },
-      attributes: {},
-      nodes: [
-        { key: "a", attributes: { invalid: true } },
-      ],
-      edges: [],
-    };
-    expect(() => FlowGraph.fromJSON(bad as never)).toThrow(InvalidInputError);
-  });
-});