GetUp - Loops

allLoopsBack.ts

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]]