《移动游戏产品的架构·网络、资源与热更新》8.1 资源依赖图与循环检测

// file: src/resource/dependency-graph.ts
// tier: L1
// verify: node --test test/resource/dependency-graph.test.ts

export type ResourceKind =
  | "texture"
  | "model"
  | "animation"
  | "audio"
  | "config"
  | "other";

export interface ResourceNode {
  readonly id: string;
  readonly kind: ResourceKind;
  readonly deps: readonly string[];
}

export interface DependencyGraph {
  readonly nodes: ReadonlyMap<string, ResourceNode>;
  readonly order: readonly string[];
}

export interface GraphStats {
  readonly nodes: number;
  readonly edges: number;
  readonly roots: number;
  readonly leaves: number;
  readonly avgOutDegree: number;
  readonly maxDepth: number;
  readonly maxDepthRoot: string;
}

export type GraphErrorCode = "duplicate" | "unknown" | "cycle" | "empty";

export class GraphError extends Error {
  readonly code: GraphErrorCode;

  constructor(code: GraphErrorCode, message: string) {
    super(message);
    this.name = "GraphError";
    this.code = code;
  }
}

function canonicalCycle(cycle: readonly string[]): string {
  const body = cycle.slice(0, -1);
  let best = 0;
  for (let i = 1; i < body.length; i += 1) {
    if (body[i] < body[best]) best = i;
  }
  const rotated = [...body.slice(best), ...body.slice(0, best)];
  return [...rotated, rotated[0]].join(" -> ");
}

export function buildGraph(nodes: readonly ResourceNode[]): DependencyGraph {
  const map = new Map<string, ResourceNode>();
  for (const node of nodes) {
    if (node.id.length === 0) {
      throw new GraphError("empty", "resource id must not be empty");
    }
    if (map.has(node.id)) {
      throw new GraphError("duplicate", `duplicate resource: ${node.id}`);
    }
    map.set(node.id, node);
  }
  for (const node of nodes) {
    for (const dep of node.deps) {
      if (!map.has(dep)) {
        throw new GraphError("unknown", `unknown dependency: ${node.id} -> ${dep}`);
      }
    }
  }
  return { nodes: map, order: [...map.keys()].sort() };
}

export function detectCycles(graph: DependencyGraph): string[][] {
  const color = new Map<string, number>();
  const stack: string[] = [];
  const cycles: string[][] = [];
  const seen = new Set<string>();

  const visit = (id: string): void => {
    color.set(id, 1);
    stack.push(id);
    const node = graph.nodes.get(id);
    if (node === undefined) {
      throw new GraphError("unknown", `unknown resource: ${id}`);
    }
    for (const dep of node.deps) {
      const state = color.get(dep) ?? 0;
      if (state === 0) {
        visit(dep);
      } else if (state === 1) {
        const start = stack.indexOf(dep);
        const cycle = [...stack.slice(start), dep];
        const key = canonicalCycle(cycle);
        if (!seen.has(key)) {
          seen.add(key);
          cycles.push(cycle);
        }
      }
    }
    stack.pop();
    color.set(id, 2);
  };

  for (const id of graph.order) {
    if ((color.get(id) ?? 0) === 0) visit(id);
  }
  return cycles;
}

export function topoOrder(graph: DependencyGraph): string[] {
  const cycles = detectCycles(graph);
  if (cycles.length > 0) {
    throw new GraphError("cycle", `cycle detected: ${canonicalCycle(cycles[0])}`);
  }
  const done = new Set<string>();
  const result: string[] = [];

  const visit = (id: string): void => {
    if (done.has(id)) return;
    const node = graph.nodes.get(id);
    if (node === undefined) {
      throw new GraphError("unknown", `unknown resource: ${id}`);
    }
    for (const dep of [...node.deps].sort()) visit(dep);
    done.add(id);
    result.push(id);
  };

  for (const id of graph.order) visit(id);
  return result;
}

export function analyzeGraph(graph: DependencyGraph): GraphStats {
  if (detectCycles(graph).length > 0) {
    throw new GraphError("cycle", "cannot analyze a cyclic graph");
  }
  const incoming = new Map<string, number>();
  for (const id of graph.order) incoming.set(id, 0);

  let edges = 0;
  for (const id of graph.order) {
    const node = graph.nodes.get(id);
    if (node === undefined) {
      throw new GraphError("unknown", `unknown resource: ${id}`);
    }
    edges += node.deps.length;
    for (const dep of node.deps) {
      incoming.set(dep, (incoming.get(dep) ?? 0) + 1);
    }
  }

  const depth = new Map<string, number>();
  const depthOf = (id: string): number => {
    const cached = depth.get(id);
    if (cached !== undefined) return cached;
    const node = graph.nodes.get(id);
    if (node === undefined) {
      throw new GraphError("unknown", `unknown resource: ${id}`);
    }
    let best = 0;
    for (const dep of node.deps) {
      best = Math.max(best, 1 + depthOf(dep));
    }
    depth.set(id, best);
    return best;
  };

  let roots = 0;
  let leaves = 0;
  let maxDepth = 0;
  let maxDepthRoot = "";
  for (const id of graph.order) {
    const node = graph.nodes.get(id);
    if (node === undefined) {
      throw new GraphError("unknown", `unknown resource: ${id}`);
    }
    if ((incoming.get(id) ?? 0) === 0) roots += 1;
    if (node.deps.length === 0) leaves += 1;
    const value = depthOf(id);
    if (value > maxDepth || (value === maxDepth && (maxDepthRoot === "" || id < maxDepthRoot))) {
      maxDepth = value;
      maxDepthRoot = id;
    }
  }

  const nodes = graph.order.length;
  const avgOutDegree = nodes === 0 ? 0 : Math.round((edges / nodes) * 100) / 100;
  return { nodes, edges, roots, leaves, avgOutDegree, maxDepth, maxDepthRoot };
}

export function expandClosure(
  graph: DependencyGraph,
  roots: readonly string[],
): string[] {
  const seen = new Set<string>();
  const stack = [...roots].sort().reverse();
  while (stack.length > 0) {
    const id = stack.pop() as string;
    if (seen.has(id)) continue;
    const node = graph.nodes.get(id);
    if (node === undefined) {
      throw new GraphError("unknown", `unknown resource: ${id}`);
    }
    seen.add(id);
    for (const dep of [...node.deps].sort().reverse()) {
      if (!seen.has(dep)) stack.push(dep);
    }
  }
  return [...seen].sort();
}

export function formatGraphReport(stats: GraphStats, cycleCount = 0): string {
  return [
    "metric\tvalue",
    `nodes\t${stats.nodes}`,
    `edges\t${stats.edges}`,
    `avgOutDegree\t${stats.avgOutDegree.toFixed(2)}`,
    `maxDepth\t${stats.maxDepth}`,
    `maxDepthRoot\t${stats.maxDepthRoot}`,
    `roots\t${stats.roots}`,
    `leaves\t${stats.leaves}`,
    `cycles\t${cycleCount}`,
  ].join("\n");
}

metric  value
nodes   5
edges   5
avgOutDegree  1.00
maxDepth  2
maxDepthRoot  a
roots   2
leaves  1
cycles  0