syntaxai/tdd.md · main · src / b32_graph_depth_polyglot.test.ts

import { describe, expect, test } from "bun:test";
import { computeGraphDepth, type Graph } from "./b32_graph_depth_polyglot.ts";

// Mirror b32_sama_v2_metrics.test.ts graphDepth cases. Same algorithm
// (longest path in import DAG with bounded cycles), same edge-cases
// (empty, single node, linear chain, cycle, branching). The polyglot
// helper is allowed to be language-agnostic but the formula and
// cycle-handling must match the TS reference.

describe("computeGraphDepth — empty + trivial", () => {
  test("empty graph → 0 (matches TS metric on an empty file map)", () => {
    const r = computeGraphDepth({ nodes: [], edges: [] });
    expect(r.depth).toBe(0);
    expect(r.nodeCount).toBe(0);
    expect(r.edgeCount).toBe(0);
  });

  test("single node, no edges → 1", () => {
    const r = computeGraphDepth({ nodes: ["a"], edges: [] });
    expect(r.depth).toBe(1);
    expect(r.nodeCount).toBe(1);
    expect(r.edgeCount).toBe(0);
  });
});

describe("computeGraphDepth — linear chains", () => {
  test("chain a → b → c → 3", () => {
    const r = computeGraphDepth({
      nodes: ["a", "b", "c"],
      edges: [["a", "b"], ["b", "c"]],
    });
    expect(r.depth).toBe(3);
    expect(r.edgeCount).toBe(2);
  });

  test("chain of 5 → 5 (matches the TS chain p3 → p2 → p1 → p0 case)", () => {
    const r = computeGraphDepth({
      nodes: ["a", "b", "c", "d", "e"],
      edges: [["a", "b"], ["b", "c"], ["c", "d"], ["d", "e"]],
    });
    expect(r.depth).toBe(5);
  });
});

describe("computeGraphDepth — cycles are bounded", () => {
  test("cycle of 2 (a → b → a) terminates with finite depth", () => {
    const r = computeGraphDepth({
      nodes: ["a", "b"],
      edges: [["a", "b"], ["b", "a"]],
    });
    expect(Number.isFinite(r.depth)).toBe(true);
    expect(r.depth).toBeGreaterThanOrEqual(1);
  });

  test("cycle of 3 (a → b → c → a) terminates with finite depth", () => {
    const r = computeGraphDepth({
      nodes: ["a", "b", "c"],
      edges: [["a", "b"], ["b", "c"], ["c", "a"]],
    });
    expect(Number.isFinite(r.depth)).toBe(true);
    expect(r.depth).toBeGreaterThanOrEqual(1);
  });

  test("self-loop is also bounded", () => {
    const r = computeGraphDepth({
      nodes: ["a"],
      edges: [["a", "a"]],
    });
    expect(Number.isFinite(r.depth)).toBe(true);
  });
});

describe("computeGraphDepth — branching → longest path, not sum", () => {
  test("a → {b, c} → d (diamond) → 3 (not 4)", () => {
    const r = computeGraphDepth({
      nodes: ["a", "b", "c", "d"],
      edges: [["a", "b"], ["a", "c"], ["b", "d"], ["c", "d"]],
    });
    expect(r.depth).toBe(3);
  });

  test("two disjoint chains; longest wins", () => {
    const r = computeGraphDepth({
      nodes: ["a", "b", "x", "y", "z"],
      edges: [["a", "b"], ["x", "y"], ["y", "z"]],
    });
    // chain a→b has length 2; chain x→y→z has length 3.
    expect(r.depth).toBe(3);
  });

  test("two paths different lengths, max picks the longer", () => {
    // a → b → c → d (4) and a → e (2). Longest path = 4.
    const r = computeGraphDepth({
      nodes: ["a", "b", "c", "d", "e"],
      edges: [["a", "b"], ["b", "c"], ["c", "d"], ["a", "e"]],
    });
    expect(r.depth).toBe(4);
  });
});

describe("computeGraphDepth — edge filtering", () => {
  test("edges referencing non-declared nodes are silently ignored", () => {
    const r = computeGraphDepth({
      nodes: ["a", "b"],
      edges: [["a", "b"], ["a", "external"], ["external", "a"]],
    });
    // Only the a → b edge is between declared nodes. Depth = 2.
    expect(r.depth).toBe(2);
    expect(r.edgeCount).toBe(1);
  });
});

describe("computeGraphDepth — reproducibility", () => {
  test("same input → identical output across two runs (deep-equal)", () => {
    const g: Graph = {
      nodes: ["a", "b", "c", "d"],
      edges: [["a", "b"], ["b", "c"], ["c", "d"]],
    };
    const r1 = computeGraphDepth(g);
    const r2 = computeGraphDepth(g);
    expect(r1).toEqual(r2);
  });

  test("edge order independence — same edges in different order → same depth", () => {
    const r1 = computeGraphDepth({
      nodes: ["a", "b", "c"],
      edges: [["a", "b"], ["b", "c"]],
    });
    const r2 = computeGraphDepth({
      nodes: ["c", "a", "b"],
      edges: [["b", "c"], ["a", "b"]],
    });
    expect(r1.depth).toBe(r2.depth);
    expect(r1.nodeCount).toBe(r2.nodeCount);
    expect(r1.edgeCount).toBe(r2.edgeCount);
  });
});