24833433462

Committed 23 Apr 2026 11:47AM UTC coverage: 78.535% (+0.1%) from 78.391%

Build # 24833433462

Build Type

Pull #1893

github

Committed by

web-flow

Commit Message

Merge 9b995e587 into 715603479

Pull Request Pull Request #1893: Error Handling and Stringify Changes

Coverage Stats

3126 of 4197 branches covered (74.48%)

Branch coverage included in aggregate %.

801 of 976 new or added lines in 76 files covered. (82.07%)

20 existing lines in 11 files now uncovered.

7056 of 8768 relevant lines covered (80.47%)

179672.42 hits per line

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

90.65

/src/modules/preprocessor/directedGraph.ts

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

source-academy / js-slang / 24833433462

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