import { describe, expect, it } from "vitest";

import { findShortestStableCycle } from "./graph/find-shortest-stable-cycle";

describe("findShortestStableCycle", () => {
  it("chooses the cycle with the fewest edges", () => {
    type NodeId = "alpha" | "beta" | "delta" | "gamma";
    const adjacency = new Map<NodeId, ReadonlySet<NodeId>>([
      ["gamma", new Set(["alpha"])],
      ["delta", new Set(["alpha"])],
      ["beta", new Set(["delta"])],
      ["alpha", new Set(["beta", "gamma"])],
    ]);

    const cycle = findShortestStableCycle(adjacency);
    expect(cycle).toEqual(["alpha", "gamma", "alpha"]);
    expect(Object.isFrozen(cycle)).toBe(true);
  });

  it("chooses the lexical closed path for equal-length cycles", () => {
    const adjacency = new Map<string, readonly string[]>([
      ["gamma", ["alpha"]],
      ["beta", ["alpha"]],
      ["alpha", ["gamma", "beta"]],
    ]);

    expect(findShortestStableCycle(adjacency)).toEqual([
      "alpha",
      "beta",
      "alpha",
    ]);
  });

  it("normalizes and freezes a closed cycle at its smallest rotation", () => {
    const adjacency = new Map<string, readonly string[]>([
      ["gamma", ["beta"]],
      ["beta", ["alpha"]],
      ["alpha", ["gamma"]],
    ]);

    const cycle = findShortestStableCycle(adjacency);
    expect(cycle).toEqual(["alpha", "gamma", "beta", "alpha"]);
    expect(Object.isFrozen(cycle)).toBe(true);
  });

  it("returns undefined for an acyclic graph", () => {
    const adjacency = new Map<string, readonly string[]>([
      ["alpha", ["beta"]],
      ["beta", []],
    ]);

    expect(findShortestStableCycle(adjacency)).toBeUndefined();
  });
});