Variable-length paths & isomorphism
# grade this stage (from your course directory)
npx theinference test --stage variable-length --watchEnumerate all paths between two nodes within a hop range — the engine behind Cypher's *min..max. Get the isomorphism rule right or you'll loop forever. A DFS that extends a path up to max hops, emits a path when its length is in [min, max] and the endpoint is the target, and never reuses a relationship within the same path.
Implement varLengthPaths
Carry a per-path set of used relationship ids. The fixture finds all ACTED_IN *1..2 paths (BOTH) between Kevin Bacon (id 0) and Tom Hanks (id 10) — exactly one, the 2-hop bridge through Apollo 13.
export function varLengthPaths(store, fromId, toId, type, dir, min, max) {
const results = [], nodes = [fromId], rels = [], used = new Set();
const extend = (cur, depth) => {
if (depth >= min && depth <= max && depth > 0 && cur === toId)
results.push({ nodes: nodes.slice(), rels: rels.slice() });
if (depth >= max) return;
for (const { rel, node } of store.neighborEdges(cur, type, dir)) {
if (used.has(rel)) continue; // isomorphism: each rel once per path
used.add(rel); nodes.push(node); rels.push(rel);
extend(node, depth + 1);
used.delete(rel); nodes.pop(); rels.pop();
}
};
extend(fromId, 0);
return results; // sort canonically (length, then node sequence) before returning
}
your_program.sh varlen {fixture}/fixtures/data/nodes.json {fixture}/fixtures/data/relationships.json 0 10 ACTED_IN BOTH 1 2
# -> [{"nodes":[0,65,10],"rels":[46,45]}]
Cypher's default forbids traversing the same relationship twice in one path (relationship isomorphism / DIFFERENT_RELATIONSHIPS). Drop that rule and *1..4 over any cycle produces infinitely many — or wildly too many — paths, and your output won't match. Track used relationship ids per path, not a global visited set: a node can be revisited via a different relationship.
Process mode, stdout_json_match as a canonical set: paths sorted by length then node sequence, so set-equality is exact-equality. The Bacon↔Hanks bridge has exactly one *1..2 path; longer ranges expose the isomorphism rule.