@devries-cameron20 / t3code Mirror · read-only
Fork 0

The best way to control Claude Code, Codex and more from any computer or phone

Mirrored from https://github.com/Camo67/t3code.git

Synced Nov 21, 06:00 UTC

main
ts 101 lines 3.06 KB
Raw
1 /**
2 * Compute the strongly-connected components of a directed graph.
3 *
4 * Components are emitted in Tarjan completion order — the reverse
5 * topological order of the condensation, so a component appears before
6 * every component that has an edge into it.
7 *
8 * Implementation is iterative Tarjan's algorithm to avoid blowing the JS
9 * call stack on very wide graphs.
10 */
11 export const stronglyConnectedComponents = (
12 nodes: Iterable<string>,
13 successors: (node: string) => Iterable<string>,
14 ): string[][] => {
15 const output: string[][] = [];
16
17 let index = 0;
18 const indexOf = new Map<string, number>();
19 const lowlink = new Map<string, number>();
20 const onStack = new Set<string>();
21 const stack: string[] = [];
22
23 type Frame = { node: string; children: string[]; childIdx: number };
24 const callStack: Frame[] = [];
25
26 const startNode = (node: string) => {
27 indexOf.set(node, index);
28 lowlink.set(node, index);
29 index += 1;
30 stack.push(node);
31 onStack.add(node);
32 callStack.push({ node, children: [...successors(node)], childIdx: 0 });
33 };
34
35 for (const root of nodes) {
36 if (indexOf.has(root)) continue;
37 startNode(root);
38
39 while (callStack.length > 0) {
40 const frame = callStack[callStack.length - 1];
41 if (frame.childIdx < frame.children.length) {
42 const child = frame.children[frame.childIdx];
43 frame.childIdx += 1;
44 if (!indexOf.has(child)) {
45 startNode(child);
46 continue;
47 }
48 if (onStack.has(child)) {
49 lowlink.set(frame.node, Math.min(lowlink.get(frame.node)!, indexOf.get(child)!));
50 }
51 continue;
52 }
53
54 // All children processed: maybe close an SCC.
55 if (lowlink.get(frame.node) === indexOf.get(frame.node)) {
56 const scc: string[] = [];
57 for (;;) {
58 const w = stack.pop()!;
59 onStack.delete(w);
60 scc.push(w);
61 if (w === frame.node) break;
62 }
63 output.push(scc);
64 }
65
66 // Pop frame and propagate lowlink up to the parent.
67 callStack.pop();
68 const parent = callStack[callStack.length - 1];
69 if (parent) {
70 const cur = lowlink.get(parent.node)!;
71 const childLow = lowlink.get(frame.node)!;
72 if (childLow < cur) lowlink.set(parent.node, childLow);
73 }
74 }
75 }
76
77 return output;
78 };
79
80 /**
81 * Compute the set of graph nodes that participate in a dependency cycle.
82 *
83 * A node is considered "in a cycle" iff it sits in a strongly-connected
84 * component (SCC) of size > 1, or has a self-edge (size-1 SCC that loops
85 * back to itself).
86 */
87 export const findCycleMembers = (edges: Record<string, readonly string[]>): Set<string> => {
88 const cycleMembers = new Set<string>();
89 for (const scc of stronglyConnectedComponents(Object.keys(edges), (node) => edges[node] ?? [])) {
90 if (scc.length > 1) {
91 for (const fqn of scc) cycleMembers.add(fqn);
92 } else {
93 // Size-1 SCC: only counts as a cycle if it has a self-edge.
94 const only = scc[0];
95 if ((edges[only] ?? []).includes(only)) {
96 cycleMembers.add(only);
97 }
98 }
99 }
100 return cycleMembers;
101 };