Two stores, one purpose: nodes holds the metadata dict per id, and edges holds a src -> {dst: rel} map so each edge has a typed relationship. The cost of the metadata dict is one extra hash lookup per node access, which is negligible compared to having to denormalize node data into every edge. The add_edge checks both endpoints; that single line has caught dozens of typos in production. The neighbors method returns a list (not the underlying dict view) so the caller can safely mutate the graph during iteration, which the next accordion needs.

The bug I have shipped most often in graph code is forgetting step 3, the incoming-edge sweep. Without it, removing node a leaves c -> a and d -> a references pointing at a node that no longer exists in self.nodes, and the next traversal raises KeyError. Because incoming edges are not indexed, the sweep is O(E), which is why a real production graph keeps a reverse index when deletions are common. The if not dsts: del self.edges[src] cleanup is cosmetic but keeps the structure honest: empty entries are surprising during debugging.

Two design choices make BFS safe under mutation: snapshotting neighbors into a list at visit time, and re-checking nb in self.nodes before enqueueing. The snapshot prevents RuntimeError: dictionary changed size during iteration when the caller deletes an edge as a side effect of visiting a node. The membership re-check makes the traversal forgiving when a downstream node is removed mid-walk; we just skip it rather than crashing. I use this exact pattern in a content-graph crawler where visiting an article can delete it (because it is now flagged spam); the traversal needs to stay correct even though the underlying graph is moving.