Graph traversals·10 min

DFS & cycle detection

0 / 1

# grade this stage (from your course directory)
npx theinference test --stage dfs-cycles --watch

Implement DFS pre-order traversal and detect whether the start node sits on a cycle. The Movies graph has a 3-node FOLLOWS cycle among reviewers — Jessica Thompson (id 56) → Angela Scope (55) → George Martin (54) → back to Jessica. DFS from id 56 over FOLLOWS OUT should report hasCycleFromStart: true and visit order [56, 55, 54].

Your task

Implement dfs

Recursive DFS producing a pre-order visit array, with a back-edge check: keep an onStack set; if a neighbor is already on the stack, you've found a cycle. Sort neighbors by id before recursing so the order is deterministic.

src/traversal.ts

export function dfs(store, startId, type, dir) {
  const order = [], visited = new Set(), onStack = new Set();
  let cycle = false;
  const go = (cur) => {
    visited.add(cur); onStack.add(cur); order.push(cur);
    for (const nb of store.neighbors(cur, type, dir)) {   // already id-sorted
      if (onStack.has(nb)) cycle = true;                  // back edge -> cycle
      if (!visited.has(nb)) go(nb);
    }
    onStack.delete(cur);
  };
  go(startId);
  return { order, hasCycleFromStart: cycle };
}

Process command

your_program.sh dfs {fixture}/fixtures/data/nodes.json {fixture}/fixtures/data/relationships.json 56 FOLLOWS OUT
# -> {"hasCycleFromStart":true,"order":[56,55,54]}

Determinism needs a tiebreak

DFS order depends on which neighbor you visit first — so always expand neighbors in ascending id order (store.neighbors already sorts them). Without a fixed tiebreak your 'correct' answer differs run-to-run and the grader can't match it.

How it's graded

Process mode, stdout_json_match against the exact order array and boolean. Compare with a director over DIRECTED (an acyclic region) and you'd get hasCycleFromStart: false.

Breadth-first search Unweighted shortest path