Index-free adjacency·15 min

Build the adjacency lists

0 / 1

# grade this stage (from your course directory)
npx theinference test --stage build-adjacency --watch

Precompute the relationship chains. For every node, gather the relationships where it is the start (outgoing) and where it is the end (incoming). One pass over all relationships does it — appending each rel's id to outgoing[startNode] and incoming[endNode]. This O(E) one-time build buys O(1) hops forever.

Your task

Build the adjacency map

In the constructor, build a Map<nodeId, {outgoing:number[], incoming:number[]}>. Then implement adjacency(nodeId) to return that node's two id arrays, each sorted ascending (the grader compares them as sorted sets). The adjacency CLI command prints them for The Matrix (id 66).

src/store.ts

// in the constructor, after seeding nodeById:
for (const n of nodes) this.adj.set(n.id, { outgoing: [], incoming: [] });
for (const r of rels) {
  this.adj.get(r.startNode)?.outgoing.push(r.id);
  this.adj.get(r.endNode)?.incoming.push(r.id);
}

adjacency(nodeId: number): { outgoing: number[]; incoming: number[] } {
  const a = this.adj.get(nodeId) ?? { outgoing: [], incoming: [] };
  return {
    outgoing: a.outgoing.slice().sort((x, y) => x - y),
    incoming: a.incoming.slice().sort((x, y) => x - y),
  };
}

Process command

your_program.sh adjacency {fixture}/fixtures/data/nodes.json {fixture}/fixtures/data/relationships.json 66
# The Matrix has NO outgoing rels (movies are always the end node) and 7 incoming:
# -> {"incoming":[51,52,53,54,55,56,57],"outgoing":[]}

Build once, at load time

Build the adjacency map once, in the constructor — O(E). If you rebuild it per query you've reinvented the table scan and thrown the whole point away. The trade is a little memory + insert cost for O(1) reads forever.

How it's graded

Process mode, stdout_json_match. The Matrix is the end node of every ACTED_IN/DIRECTED/PRODUCED touching it, so all of its relationships are incoming and outgoing is []. Sort each id array ascending so set-equality is exact.

What index-free adjacency means O(1) neighbor lookup