All files / src/compiler/phases/2-analyze/utils check_graph_for_cycles.js

100% Statements 46/46
100% Branches 12/12
100% Functions 2/2
100% Lines 46/46

Press n or j to go to the next uncovered block, b, p or k for the previous block.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 472x 2x 2x 2x 2x 2x 4140x 4140x 412x 412x 412x 412x 412x 4140x 4140x 4140x 4140x 4140x 4140x 4140x 4140x 4140x 4140x 4140x 606x 606x 606x 606x 412x 302x 392x 2x 2x 606x 606x 606x 606x 4140x 4140x 606x 304x 304x 4140x 4140x 4140x 4140x  
/**
 * @template T
 * @param {Array<[T, T]>} edges
 * @returns {Array<T>|undefined}
 */
export default function check_graph_for_cycles(edges) {
	/** @type {Map<T, T[]>} */
	const graph = edges.reduce((g, edge) => {
		const [u, v] = edge;
		if (!g.has(u)) g.set(u, []);
		if (!g.has(v)) g.set(v, []);
		g.get(u).push(v);
		return g;
	}, new Map());
 
	const visited = new Set();
	const on_stack = new Set();
	/** @type {Array<Array<T>>} */
	const cycles = [];
 
	/**
	 * @param {T} v
	 */
	function visit(v) {
		visited.add(v);
		on_stack.add(v);
 
		graph.get(v)?.forEach((w) => {
			if (!visited.has(w)) {
				visit(w);
			} else if (on_stack.has(w)) {
				cycles.push([...on_stack, w]);
			}
		});
 
		on_stack.delete(v);
	}
 
	graph.forEach((_, v) => {
		if (!visited.has(v)) {
			visit(v);
		}
	});
 
	return cycles[0];
}