Metric closure in TypeScript

The 2-approximation: build the metric closure on terminals, take its MST, expand back into the original graph.

1. 01
   Define types for edges and graphs. TypeScript's structural typing means an "object literal that looks like a Graph" is a Graph — no class, no constructor.

   type Edge = { u: number; v: number; w: number };
   type Graph = { n: number; adj: Map<number, { to: number; w: number }[]> };
   
   function makeGraph(n: number, edges: Edge[]): Graph {
     const adj = new Map<number, { to: number; w: number }[]>();
     for (let i = 0; i < n; i++) adj.set(i, []);
     for (const e of edges) {
       adj.get(e.u)!.push({ to: e.v, w: e.w });
       adj.get(e.v)!.push({ to: e.u, w: e.w });
     }
     return { n, adj };
   }

2. 02
   Dijkstra's all-pairs shortest paths from each terminal. The "metric closure" is the complete graph on terminals where each edge weight equals shortest-path distance in the original.

   function dijkstra(g: Graph, src: number): number[] {
     const dist = new Array(g.n).fill(Infinity);
     dist[src] = 0;
     const visited = new Set<number>();
     while (visited.size < g.n) {
       let u = -1, best = Infinity;
       for (let i = 0; i < g.n; i++)
         if (!visited.has(i) && dist[i] < best) { u = i; best = dist[i]; }
       if (u < 0) break;
       visited.add(u);
       for (const { to, w } of g.adj.get(u)!)
         if (dist[u] + w < dist[to]) dist[to] = dist[u] + w;
     }
     return dist;
   }

3. 03
   MST on the metric closure (Kruskal with union-find). The result is a tree on terminals; each "metric-closure edge" expands back to a real shortest path in G.

   function steinerApprox(g: Graph, terminals: number[]): Edge[] {
     const dist = terminals.map(t => dijkstra(g, t));
     const closureEdges: Edge[] = [];
     for (let i = 0; i < terminals.length; i++)
       for (let j = i + 1; j < terminals.length; j++)
         closureEdges.push({ u: i, v: j, w: dist[i][terminals[j]] });
     closureEdges.sort((a, b) => a.w - b.w);
   
     const parent = terminals.map((_, i) => i);
     const find = (x: number): number => parent[x] === x ? x : (parent[x] = find(parent[x]));
     const tree: Edge[] = [];
     for (const e of closureEdges) {
       const ru = find(e.u), rv = find(e.v);
       if (ru !== rv) { parent[ru] = rv; tree.push(e); }
     }
     return tree;
   }

4. 04
   Run on a five-node ring with three terminals. The 2-approximation gives a tree of weight at most twice the optimum, which on real-world inputs lands within ~10–20% of optimal.

   const g = makeGraph(5, [
     { u: 0, v: 1, w: 1 }, { u: 1, v: 2, w: 1 }, { u: 2, v: 3, w: 1 },
     { u: 3, v: 4, w: 1 }, { u: 4, v: 0, w: 1 }
   ]);
   console.log(steinerApprox(g, [0, 2, 4]));