Graphs

// BFS: fewest hops between two accounts in a transfer graph
function hops(adj: Map<string, string[]>, from: string, to: string): number {
  const dist = new Map([[from, 0]]); let q = [from];
  while (q.length) { const next: string[] = [];
    for (const u of q) for (const v of adj.get(u) ?? []) if (!dist.has(v)) { dist.set(v, dist.get(u)! + 1); if (v === to) return dist.get(v)!; next.push(v); }
    q = next; }
  return -1;
}
// Kahn's topological sort: run migrations in dependency order, or report a cycle
function topo(deps: Map<string, string[]>): string[] {
  const indeg = new Map<string, number>(); for (const [n, ds] of deps) { indeg.set(n, indeg.get(n) ?? 0); for (const d of ds) { indeg.set(d, indeg.get(d) ?? 0); } }
  for (const [n, ds] of deps) indeg.set(n, ds.length);
  const order: string[] = [], q = [...indeg].filter(([, k]) => k === 0).map(([n]) => n);
  const users = new Map<string, string[]>(); for (const [n, ds] of deps) for (const d of ds) users.set(d, [...(users.get(d) ?? []), n]);
  while (q.length) { const n = q.shift()!; order.push(n); for (const u of users.get(n) ?? []) { indeg.set(u, indeg.get(u)! - 1); if (indeg.get(u) === 0) q.push(u); } }
  if (order.length !== indeg.size) throw new Error('cycle');
  return order;
}