Created
December 12, 2023 01:46
-
-
Save SpareShade/71fb0a25be42ebd51c661b741ebaaca8 to your computer and use it in GitHub Desktop.
GetUp - Loops
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
type Edge = [number, number]; | |
function allLoopsBack(node: number, edges: Edge[]): number[][] { | |
const loops: number[][] = []; | |
const visited: boolean[] = new Array(edges.length).fill(false); | |
function findPaths(inNode: number, path: number[]): void { | |
const inNodeIdx = edges.findIndex((e) => e[0] === inNode); | |
// must exist as an `in` node | |
if (inNodeIdx >= 0) { | |
// add it the `path` | |
path.push(inNode); | |
// console.log("path start", path); | |
// mark it as `visited` | |
visited[inNodeIdx] = true; | |
// find the linked `out` nodes | |
const linkedNodes = edges | |
.filter((edge) => edge[0] === inNode) | |
.map((edge) => edge[1]); | |
// console.log("linkedNodes", linkedNodes) | |
for (const outNode of linkedNodes) { | |
// console.log("outNode", outNode) | |
if (outNode === node) { | |
// console.log("loop complete"); | |
// `loop` complete | |
path.push(outNode); | |
loops.push([...path]); | |
} else if (!visited[edges.findIndex((e) => e[0] === outNode)]) { | |
// console.log("run again"); | |
findPaths(outNode, path); | |
} | |
} | |
// Backtrack to prev node so that we can explore its branch | |
visited[inNodeIdx] = false; | |
path.pop(); | |
} | |
} | |
findPaths(node, []); | |
return loops; | |
} | |
const edges: Edge[] = [ | |
[1, 2], | |
[2, 3], | |
[1, 3], | |
[3, 4], | |
[3, 5], | |
[2, 5], | |
[2, 4], | |
[2, 6], | |
[6, 7], | |
[6, 9], | |
[6, 11], | |
[4, 2], | |
[5, 3], | |
[3, 9], | |
]; | |
// Example usage: | |
const result: number[][] = allLoopsBack(2, edges); | |
console.log("result", result); // Output: "result", [[2, 3, 4, 2], [2, 3, 5, 3, 4, 2], [2, 3, 5, 4, 2]] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment