23995741899

Committed 05 Apr 2026 06:14AM UTC coverage: 77.093% (+0.002%) from 77.091%

Build # 23995741899

Build Type

push

github

Committed by

web-flow

Commit Message

Upgrade to TypeScript 6 and Prettier improvements (#1936)

* Upgrade TypeScript to v6

* Fix import source

* Fix tsconfig

* Fix preexisting type errors

* Remove scm-slang

* Bump node types

* Fix tsconfig

* Fix node types specifier

* Enable trailing commas

* Enable semicolons

* Check and commit files with changed line numbers

* Update Yarn to 4.13.0

* Remove unneeded sicp package deps

Coverage Stats

3112 of 4282 branches covered (72.68%)

Branch coverage included in aggregate %.

3761 of 5218 new or added lines in 152 files covered. (72.08%)

26 existing lines in 9 files now uncovered.

7136 of 9011 relevant lines covered (79.19%)

175254.05 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

90.65

/src/modules/preprocessor/directedGraph.ts

import assert from '../../utils/assert';

/**
 * The result of attempting to find a topological ordering
 * of nodes on a DirectedGraph.
 */
export type TopologicalOrderResult =
  | {
      isValidTopologicalOrderFound: true;
      topologicalOrder: string[];
      firstCycleFound: null;
    }
  | {
      isValidTopologicalOrderFound: false;
      topologicalOrder: null;
      firstCycleFound: string[];
    };

/**
 * Represents a directed graph which disallows self-loops.
 */
export class DirectedGraph {
  private readonly adjacencyList: Map<string, Set<string>>;
  private readonly differentKeysError = new Error(
    'The keys of the adjacency list & the in-degree maps are not the same. This should never occur.',
  );

  constructor() {
    this.adjacencyList = new Map();
  }

  /**
   * Adds a directed edge to the graph from the source node to
   * the destination node. Self-loops are not allowed.
   *
   * @param sourceNode      The name of the source node.
   * @param destinationNode The name of the destination node.
   */
  public addEdge(sourceNode: string, destinationNode: string): void {
    if (sourceNode === destinationNode) {
      throw new Error('Edges that connect a node to itself are not allowed.');
    }

    const neighbours = this.adjacencyList.get(sourceNode) ?? new Set();
    neighbours.add(destinationNode);
    this.adjacencyList.set(sourceNode, neighbours);

    // Create an entry for the destination node if it does not exist
    // in the adjacency list. This is so that the set of keys of the
    // adjacency list is the same as the set of nodes in the graph.
    if (!this.adjacencyList.has(destinationNode)) {
      this.adjacencyList.set(destinationNode, new Set());
    }
  }

  /**
   * Returns whether the directed edge from the source node to the
   * destination node exists in the graph.
   *
   * @param sourceNode      The name of the source node.
   * @param destinationNode The name of the destination node.
   */
  public hasEdge(sourceNode: string, destinationNode: string): boolean {
    if (sourceNode === destinationNode) {
      throw new Error('Edges that connect a node to itself are not allowed.');
    }

    const neighbours = this.adjacencyList.get(sourceNode) ?? new Set();
    return neighbours.has(destinationNode);
  }

  /**
   * Calculates the in-degree of every node in the directed graph.
   *
   * The in-degree of a node is the number of edges coming into
   * the node.
   */
  private calculateInDegrees(): Map<string, number> {
    const inDegrees = new Map();
    for (const neighbours of this.adjacencyList.values()) {
      for (const neighbour of neighbours) {
        const inDegree = inDegrees.get(neighbour) ?? 0;
        inDegrees.set(neighbour, inDegree + 1);
      }
    }
    // Handle nodes which have an in-degree of 0.
    for (const node of this.adjacencyList.keys()) {
      if (!inDegrees.has(node)) {
        inDegrees.set(node, 0);
      }
    }
    return inDegrees;
  }

  /**
   * Finds a cycle of nodes in the directed graph. This operates on the
   * invariant that any nodes left over with a non-zero in-degree after
   * Kahn's algorithm has been run is part of a cycle.
   *
   * @param inDegrees The number of edges coming into each node after
   *                  running Kahn's algorithm.
   */
  private findCycle(inDegrees: Map<string, number>): string[] {
    // First, we pick any arbitrary node that is part of a cycle as our
    // starting node.
    let startingNodeInCycle: string | null = null;
    for (const [node, inDegree] of inDegrees) {
      if (inDegree !== 0) {
        startingNodeInCycle = node;
        break;
      }
    }
    // By the invariant stated above, it is impossible that the starting
    // node cannot be found. The lack of a starting node implies that
    // all nodes have an in-degree of 0 after running Kahn's algorithm.
    // This in turn implies that Kahn's algorithm was able to find a
    // valid topological ordering & that the graph contains no cycles.
    assert(
      startingNodeInCycle !== null,
      'There are no cycles in this graph. This should never happen.',
    );

    const cycle = [startingNodeInCycle];
    // Then, we keep picking arbitrary nodes with non-zero in-degrees until
    // we pick a node that has already been picked.
    while (true) {
      const currentNode = cycle[cycle.length - 1];

      const neighbours = this.adjacencyList.get(currentNode);
      if (neighbours === undefined) {
        throw this.differentKeysError;
      }
      // By the invariant stated above, it is impossible that any node
      // on the cycle has an in-degree of 0 after running Kahn's algorithm.
      // An in-degree of 0 implies that the node is not part of a cycle,
      // which is a contradiction since the current node was picked because
      // it is part of a cycle.
      assert(
        neighbours.size > 0,
        `Node '${currentNode}' has no incoming edges. This should never happen.`,
      );

      let nextNodeInCycle: string | null = null;
      for (const neighbour of neighbours) {
        if (inDegrees.get(neighbour) !== 0) {
          nextNodeInCycle = neighbour;
          break;
        }
      }
      // By the invariant stated above, if the current node is part of a cycle,
      // then one of its neighbours must also be part of the same cycle. This
      // is because a cycle contains at least 2 nodes.
      assert(
        nextNodeInCycle !== null,
        `None of the neighbours of node '${currentNode}' are part of the same cycle. This should never happen.`,
      );

      // If the next node we pick is already part of the cycle,
      // we drop all elements before the first instance of the
      // next node and return the cycle.
      const nextNodeIndex = cycle.indexOf(nextNodeInCycle);
      const isNodeAlreadyInCycle = nextNodeIndex !== -1;
      cycle.push(nextNodeInCycle);
      if (isNodeAlreadyInCycle) {
        return cycle.slice(nextNodeIndex);
      }
    }
  }

  /**
   * Returns a topological ordering of the nodes in the directed
   * graph if the graph is acyclic. Otherwise, returns null.
   *
   * To get the topological ordering, Kahn's algorithm is used.
   */
  public getTopologicalOrder(): TopologicalOrderResult {
    let numOfVisitedNodes = 0;
    const inDegrees = this.calculateInDegrees();
    const topologicalOrder: string[] = [];

    const queue: string[] = [];
    for (const [node, inDegree] of inDegrees) {
      if (inDegree === 0) {
        queue.push(node);
      }
    }

    while (true) {
      const node = queue.shift();
      // 'node' is 'undefined' when the queue is empty.
      if (node === undefined) {
        break;
      }

      numOfVisitedNodes++;
      topologicalOrder.push(node);

      const neighbours = this.adjacencyList.get(node);
      if (neighbours === undefined) {
        throw this.differentKeysError;
      }
      for (const neighbour of neighbours) {
        const inDegree = inDegrees.get(neighbour);
        if (inDegree === undefined) {
          throw this.differentKeysError;
        }
        inDegrees.set(neighbour, inDegree - 1);

        if (inDegrees.get(neighbour) === 0) {
          queue.push(neighbour);
        }
      }
    }

    // If not all nodes are visited, then at least one
    // cycle exists in the graph and a topological ordering
    // cannot be found.
    if (numOfVisitedNodes !== this.adjacencyList.size) {
      const firstCycleFound = this.findCycle(inDegrees);
      return {
        isValidTopologicalOrderFound: false,
        topologicalOrder: null,
        firstCycleFound,
      };
    }

    return {
      isValidTopologicalOrderFound: true,
      topologicalOrder,
      firstCycleFound: null,
    };
  }
}

1	import assert from '../../utils/assert';
2
3	/**
4	* The result of attempting to find a topological ordering
5	* of nodes on a DirectedGraph.
6	*/
7	export type TopologicalOrderResult =
8	\| {
9	isValidTopologicalOrderFound: true;
10	topologicalOrder: string[];
11	firstCycleFound: null;
12	}
13	\| {
14	isValidTopologicalOrderFound: false;
15	topologicalOrder: null;
16	firstCycleFound: string[];
17	};
18
19	/**
20	* Represents a directed graph which disallows self-loops.
21	*/
22	export class DirectedGraph {
23	private readonly adjacencyList: Map<string, Set<string>>;
24	private readonly differentKeysError = new Error(	2,309✔
25	'The keys of the adjacency list & the in-degree maps are not the same. This should never occur.',
26	);
27
28	constructor() {
29	this.adjacencyList = new Map();	2,309✔
30	}
31
32	/**
33	* Adds a directed edge to the graph from the source node to
34	* the destination node. Self-loops are not allowed.
35	*
36	* @param sourceNode The name of the source node.
37	* @param destinationNode The name of the destination node.
38	*/
39	public addEdge(sourceNode: string, destinationNode: string): void {
40	if (sourceNode === destinationNode) {	138✔
41	throw new Error('Edges that connect a node to itself are not allowed.');	1✔
42	}
43
44	const neighbours = this.adjacencyList.get(sourceNode) ?? new Set();	137✔
45	neighbours.add(destinationNode);	138✔
46	this.adjacencyList.set(sourceNode, neighbours);	138✔
47
48	// Create an entry for the destination node if it does not exist
49	// in the adjacency list. This is so that the set of keys of the
50	// adjacency list is the same as the set of nodes in the graph.
51	if (!this.adjacencyList.has(destinationNode)) {	138✔
52	this.adjacencyList.set(destinationNode, new Set());	100✔
53	}
54	}
55
56	/**
57	* Returns whether the directed edge from the source node to the
58	* destination node exists in the graph.
59	*
60	* @param sourceNode The name of the source node.
61	* @param destinationNode The name of the destination node.
62	*/
63	public hasEdge(sourceNode: string, destinationNode: string): boolean {
64	if (sourceNode === destinationNode) {	3!
NEW 65	throw new Error('Edges that connect a node to itself are not allowed.');	×
66	}
67
68	const neighbours = this.adjacencyList.get(sourceNode) ?? new Set();	3✔
69	return neighbours.has(destinationNode);	3✔
70	}
71
72	/**
73	* Calculates the in-degree of every node in the directed graph.
74	*
75	* The in-degree of a node is the number of edges coming into
76	* the node.
77	*/
78	private calculateInDegrees(): Map<string, number> {
79	const inDegrees = new Map();	2,142✔
80	for (const neighbours of this.adjacencyList.values()) {	2,142✔
81	for (const neighbour of neighbours) {	204✔
82	const inDegree = inDegrees.get(neighbour) ?? 0;	131✔
83	inDegrees.set(neighbour, inDegree + 1);	131✔
84	}
85	}
86	// Handle nodes which have an in-degree of 0.
87	for (const node of this.adjacencyList.keys()) {	2,142✔
88	if (!inDegrees.has(node)) {	204✔
89	inDegrees.set(node, 0);	77✔
90	}
91	}
92	return inDegrees;	2,142✔
93	}
94
95	/**
96	* Finds a cycle of nodes in the directed graph. This operates on the
97	* invariant that any nodes left over with a non-zero in-degree after
98	* Kahn's algorithm has been run is part of a cycle.
99	*
100	* @param inDegrees The number of edges coming into each node after
101	* running Kahn's algorithm.
102	*/
103	private findCycle(inDegrees: Map<string, number>): string[] {
104	// First, we pick any arbitrary node that is part of a cycle as our
105	// starting node.
106	let startingNodeInCycle: string \| null = null;	6✔
107	for (const [node, inDegree] of inDegrees) {	6✔
108	if (inDegree !== 0) {	6!
109	startingNodeInCycle = node;	6✔
110	break;	6✔
111	}
112	}
113	// By the invariant stated above, it is impossible that the starting
114	// node cannot be found. The lack of a starting node implies that
115	// all nodes have an in-degree of 0 after running Kahn's algorithm.
116	// This in turn implies that Kahn's algorithm was able to find a
117	// valid topological ordering & that the graph contains no cycles.
118	assert(	6✔
119	startingNodeInCycle !== null,
120	'There are no cycles in this graph. This should never happen.',
121	);
122
123	const cycle = [startingNodeInCycle];	6✔
124	// Then, we keep picking arbitrary nodes with non-zero in-degrees until
125	// we pick a node that has already been picked.
126	while (true) {	6✔
127	const currentNode = cycle[cycle.length - 1];	18✔
128
129	const neighbours = this.adjacencyList.get(currentNode);	18✔
130	if (neighbours === undefined) {	18!
NEW 131	throw this.differentKeysError;	×
132	}
133	// By the invariant stated above, it is impossible that any node
134	// on the cycle has an in-degree of 0 after running Kahn's algorithm.
135	// An in-degree of 0 implies that the node is not part of a cycle,
136	// which is a contradiction since the current node was picked because
137	// it is part of a cycle.
138	assert(	18✔
139	neighbours.size > 0,
140	`Node '${currentNode}' has no incoming edges. This should never happen.`,
141	);
142
143	let nextNodeInCycle: string \| null = null;	18✔
144	for (const neighbour of neighbours) {	18✔
145	if (inDegrees.get(neighbour) !== 0) {	18!
146	nextNodeInCycle = neighbour;	18✔
147	break;	18✔
148	}
149	}
150	// By the invariant stated above, if the current node is part of a cycle,
151	// then one of its neighbours must also be part of the same cycle. This
152	// is because a cycle contains at least 2 nodes.
153	assert(	18✔
154	nextNodeInCycle !== null,
155	`None of the neighbours of node '${currentNode}' are part of the same cycle. This should never happen.`,
156	);
157
158	// If the next node we pick is already part of the cycle,
159	// we drop all elements before the first instance of the
160	// next node and return the cycle.
161	const nextNodeIndex = cycle.indexOf(nextNodeInCycle);	18✔
162	const isNodeAlreadyInCycle = nextNodeIndex !== -1;	18✔
163	cycle.push(nextNodeInCycle);	18✔
164	if (isNodeAlreadyInCycle) {	18✔
165	return cycle.slice(nextNodeIndex);	6✔
166	}
167	}
168	}
169
170	/**
171	* Returns a topological ordering of the nodes in the directed
172	* graph if the graph is acyclic. Otherwise, returns null.
173	*
174	* To get the topological ordering, Kahn's algorithm is used.
175	*/
176	public getTopologicalOrder(): TopologicalOrderResult {
177	let numOfVisitedNodes = 0;	2,142✔
178	const inDegrees = this.calculateInDegrees();	2,142✔
179	const topologicalOrder: string[] = [];	2,142✔
180
181	const queue: string[] = [];	2,142✔
182	for (const [node, inDegree] of inDegrees) {	2,142✔
183	if (inDegree === 0) {	204✔
184	queue.push(node);	77✔
185	}
186	}
187
188	while (true) {	2,142✔
189	const node = queue.shift();	2,325✔
190	// 'node' is 'undefined' when the queue is empty.
191	if (node === undefined) {	2,325✔
192	break;	2,142✔
193	}
194
195	numOfVisitedNodes++;	183✔
196	topologicalOrder.push(node);	183✔
197
198	const neighbours = this.adjacencyList.get(node);	183✔
199	if (neighbours === undefined) {	183!
NEW 200	throw this.differentKeysError;	×
201	}
202	for (const neighbour of neighbours) {	183✔
203	const inDegree = inDegrees.get(neighbour);	108✔
204	if (inDegree === undefined) {	108!
NEW 205	throw this.differentKeysError;	×
206	}
207	inDegrees.set(neighbour, inDegree - 1);	108✔
208
209	if (inDegrees.get(neighbour) === 0) {	108✔
210	queue.push(neighbour);	106✔
211	}
212	}
213	}
214
215	// If not all nodes are visited, then at least one
216	// cycle exists in the graph and a topological ordering
217	// cannot be found.
218	if (numOfVisitedNodes !== this.adjacencyList.size) {	2,142✔
219	const firstCycleFound = this.findCycle(inDegrees);	6✔
220	return {	6✔
221	isValidTopologicalOrderFound: false,
222	topologicalOrder: null,
223	firstCycleFound,
224	};
225	}
226
227	return {	2,136✔
228	isValidTopologicalOrderFound: true,
229	topologicalOrder,
230	firstCycleFound: null,
231	};
232	}
233	}

source-academy / js-slang / 23995741899

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous