Skip to content
Python
7.7 KB
Raw Blame
import type {
  MemoryGraphEdge,
  MemoryGraphNode,
  MemoryGraphResponse,
} from "@one-memory/contracts";
import * as THREE from "three";
import { describe, expect, it } from "vitest";
import { createRelationLayout } from "./MemoryGraph3D";

const NODE_TYPES: MemoryGraphNode["node_type"][] = [
  "memory",
  "source",
  "schema",
  "topic",
];

function makeGraph(nodeCount: number): MemoryGraphResponse {
  const nodes: MemoryGraphNode[] = Array.from(
    { length: nodeCount },
    (_, index) => ({
      node_id: `node-${index}`,
      node_type: NODE_TYPES[index % NODE_TYPES.length],
      label: `节点 ${index}`,
      memory_id: index % 2 === 0 ? `mem-${index}` : null,
      source_id: index % 3 === 0 ? `src-${index}` : null,
      kind: null,
      status: index % 5 === 0 ? "candidate" : "active",
      confidence: 0.8,
    }),
  );
  const edges: MemoryGraphEdge[] = [];
  for (let index = 1; index < nodeCount; index += 1) {
    edges.push({
      edge_id: `edge-${index}`,
      source_node_id: `node-${Math.floor(index / 3)}`,
      target_node_id: `node-${index}`,
      // 两种 relation 的目标弹簧长度不同,必须都覆盖
      relation: index % 4 === 0 ? "evidence_source" : "derived_from",
      weight: null,
      origin: "provenance",
    });
  }
  return {
    total_memories: nodeCount,
    projected_memories: nodeCount,
    nodes,
    edges,
    hy_graph_available: true,
  };
}

/**
 * 重构前的原始算法,逐字复刻自改动前的 relationLayout:
 * 每次迭代新建 force Map、每对节点 clone 一个 Vector3。
 * 用它当基准,验证分帧重构没有改变布局语义。
 */
function legacyLayout(graph: MemoryGraphResponse): Map<string, THREE.Vector3> {
  const positions = new Map(
    graph.nodes.map((node, index) => {
      const angle = seededUnit(node.node_id, 0) * Math.PI * 2;
      const elevation = (seededUnit(node.node_id, 1) - 0.5) * Math.PI;
      const radius = 3.2 + (index % 5) * 0.24;
      return [
        node.node_id,
        new THREE.Vector3(
          Math.cos(angle) * Math.cos(elevation) * radius,
          Math.sin(elevation) * radius,
          Math.sin(angle) * Math.cos(elevation) * radius,
        ),
      ] as const;
    }),
  );

  for (let iteration = 0; iteration < 90; iteration += 1) {
    const force = new Map(
      graph.nodes.map((node) => [node.node_id, new THREE.Vector3()]),
    );
    for (let left = 0; left < graph.nodes.length; left += 1) {
      for (let right = left + 1; right < graph.nodes.length; right += 1) {
        const a = graph.nodes[left];
        const b = graph.nodes[right];
        const aPosition = positions.get(a.node_id);
        const bPosition = positions.get(b.node_id);
        const aForce = force.get(a.node_id);
        const bForce = force.get(b.node_id);
        if (!aPosition || !bPosition || !aForce || !bForce) continue;
        const delta = aPosition.clone().sub(bPosition);
        const distanceSq = Math.max(0.12, delta.lengthSq());
        const repulsion = delta.normalize().multiplyScalar(0.035 / distanceSq);
        aForce.add(repulsion);
        bForce.sub(repulsion);
      }
    }
    for (const edge of graph.edges) {
      const a = positions.get(edge.source_node_id);
      const b = positions.get(edge.target_node_id);
      if (!a || !b) continue;
      const delta = b.clone().sub(a);
      const distance = delta.length();
      const target = edge.relation === "evidence_source" ? 2.5 : 1.35;
      const spring = delta
        .normalize()
        .multiplyScalar((distance - target) * 0.018);
      force.get(edge.source_node_id)?.add(spring);
      force.get(edge.target_node_id)?.sub(spring);
    }
    for (const node of graph.nodes) {
      const position = positions.get(node.node_id);
      const nodeForce = force.get(node.node_id);
      if (position && nodeForce) {
        position.add(nodeForce).multiplyScalar(0.995);
      }
    }
  }
  return positions;
}

function seededUnit(value: string, salt: number): number {
  let hash = 2166136261 + salt;
  for (const character of value) {
    hash ^= character.charCodeAt(0);
    hash = Math.imul(hash, 16777619);
  }
  return (hash >>> 0) / 4294967295;
}

function snapshot(positions: Map<string, THREE.Vector3>): [string, number[]][] {
  return [...positions.entries()]
    .map(
      ([id, vector]) =>
        [id, [vector.x, vector.y, vector.z]] as [string, number[]],
    )
    .sort((left, right) => left[0].localeCompare(right[0]));
}

describe("createRelationLayout", () => {
  it("分帧推进与一次算完结果完全一致", () => {
    const graph = makeGraph(14);

    const stepped = createRelationLayout(graph);
    let guard = 0;
    while (stepped.step()) {
      guard += 1;
      if (guard > 500) throw new Error("step 未在预期迭代数内收尾");
    }

    const settled = createRelationLayout(graph);
    settled.settle();

    expect(snapshot(stepped.positions)).toEqual(snapshot(settled.positions));
    expect(stepped.done()).toBe(true);
    expect(settled.done()).toBe(true);
  });

  it("与重构前的原算法逐坐标一致,布局语义未变", () => {
    const graph = makeGraph(14);
    const next = createRelationLayout(graph);
    next.settle();
    const legacy = legacyLayout(graph);

    const a = snapshot(next.positions);
    const b = snapshot(legacy);
    expect(a).toHaveLength(b.length);
    for (let index = 0; index < a.length; index += 1) {
      expect(a[index][0]).toBe(b[index][0]);
      for (let axis = 0; axis < 3; axis += 1) {
        // 完全相同的运算顺序,允许的只有浮点表示误差
        expect(a[index][1][axis]).toBeCloseTo(b[index][1][axis], 10);
      }
    }
  });

  it("同一张图布局可复现,不会每次乱跳", () => {
    const graph = makeGraph(11);
    const first = createRelationLayout(graph);
    first.settle();
    const second = createRelationLayout(graph);
    second.settle();
    expect(snapshot(first.positions)).toEqual(snapshot(second.positions));
  });

  it("step 在任意中途打断时坐标都是有限值", () => {
    const graph = makeGraph(20);
    const layout = createRelationLayout(graph);
    for (let taken = 0; taken < 30; taken += 1) {
      layout.step();
      for (const vector of layout.positions.values()) {
        expect(Number.isFinite(vector.x)).toBe(true);
        expect(Number.isFinite(vector.y)).toBe(true);
        expect(Number.isFinite(vector.z)).toBe(true);
      }
    }
  });

  it("收敛后节点不会飞出可视范围,也不会互相重合", () => {
    const graph = makeGraph(16);
    const layout = createRelationLayout(graph);
    layout.settle();
    const vectors = [...layout.positions.values()];
    for (const vector of vectors) {
      expect(vector.length()).toBeLessThan(20);
    }
    let minimum = Number.POSITIVE_INFINITY;
    for (let left = 0; left < vectors.length; left += 1) {
      for (let right = left + 1; right < vectors.length; right += 1) {
        minimum = Math.min(minimum, vectors[left].distanceTo(vectors[right]));
      }
    }
    expect(minimum).toBeGreaterThan(0.05);
  });

  it("空图与单节点图不抛错", () => {
    const empty = createRelationLayout(makeGraph(0));
    empty.settle();
    expect(empty.positions.size).toBe(0);

    const single = createRelationLayout(makeGraph(1));
    single.settle();
    expect(single.positions.size).toBe(1);
    expect(single.done()).toBe(true);
  });

  it("边指向不存在的节点时跳过而不抛错", () => {
    const graph = makeGraph(6);
    graph.edges.push({
      edge_id: "dangling",
      source_node_id: "node-0",
      target_node_id: "missing-node",
      relation: "derived_from",
      weight: null,
      origin: "provenance",
    });
    const layout = createRelationLayout(graph);
    expect(() => layout.settle()).not.toThrow();
    expect(layout.positions.size).toBe(6);
  });
});