Dependency Resolution (Topological Sort)

1const modules = ["app", "ui", "utils"]
2const deps = [
3  ["app", "ui"],
4  ["ui", "utils"]
5]
6
7function resolveOrder(modules: string[], deps: string[][],): string[] {
8    const all = new Set<string>(modules);
9    for (const [a, b] of deps) {
10        all.add(a);
11        all.add(b);
12    }
13
14    // 2) Initialize adjacency + indeegree
15    const graph = new Map<string, Set<string>>();
16    const inDegree = new Map<string, number>();
17
18    for (const node of all) {
19        graph.set(node, new Set<string>());
20        inDegree.set(node, 0);
21    }
22
23    // 3) Build graph and indegree
24    for (const [a, b] of deps) {
25        const neighbords = graph.get(b)!;
26        if (!neighbords.has(a)) {
27            neighbords.add(a);
28            inDegree.set(a, (inDegree.get(a) || 0) + 1);
29        }
30    }
31
32    // 4) Topological sort (Kahn's algorithm)
33    const queue: string[] = [];
34    for (const node of all) {
35        if ((inDegree.get(node) ?? 0) === 0) queue.push(node);
36    }
37
38    // 5) Process queue
39    const order: string[] = [];
40    for (let i= 0; i < queue.length; i++) {
41        const node = queue[i];
42        order.push(node);
43
44        for (const next of graph.get(node)!) {
45            inDegree.set(next, (inDegree.get(next) ?? 0) - 1);
46            if ((inDegree.get(next) ?? 0) === 0) queue.push(next);
47        }
48    }
49
50    return order.length === all.size ? order : [];
51}
52
53console.log(resolveOrder(modules, deps));