Chapter 7 — Reps
Conditioning, not grading. Python reps this week, all about seeing graphs, storing them two ways, and walking them with BFS and DFS.
Ground rules:
- Type every line yourself. No copy-paste. The fingers learn what the eyes skim past — and the queue-vs-stack distinction only lives in your hands once you’ve typed both loops.
- Predict, then run. Before you run a traversal, predict its output in writing — the order it visits, the path it finds, the count it returns. The gap between your guess and the machine’s answer is the lesson.
- AI stays OFF. Phase 1. You cannot direct an agent to model a graph well if you have never modeled one badly with your own hands. Build it.
- Model before you code. For every rep that involves a graph, write one sentence naming what is a vertex and what is an edge before you write a function. This is the rep that matters most.
These reps assume Python 3.10+ on your own machine (Appendix A) and the chapter’s code/ folder, especially small_group_edges.csv, graph_representations.py, and traversal.py.
Reps 1–3: Seeing the Graph
Rep 1 — Name the vertices, edges, and cell
For each problem statement below, write three things: (a) what is a vertex, (b) what is an edge, and (c) the cell in the two-by-two grid — directed or undirected, weighted or unweighted.
- “Find the fewest introductions needed for Maya to meet Tobias.”
- “Compute the cheapest flight itinerary from Chicago to Jerusalem.”
- “Determine the order in which a student can take a set of courses with prerequisites.”
- “Decide whether two believers are in the same fellowship.”
- “Detect whether a set of Python modules has a circular import.”
No code. Just the modeling. Then, for each, name which traversal or algorithm answers it (BFS / DFS / connected components / topological order / cycle detection). This rep is the chapter’s first architectural skill; do it slowly.
Rep 2 — Draw it, then write the edge list
Pick problem #1 or #4 from Rep 1. On paper, draw the small-group graph from small_group_edges.csv — dots for people, lines for edges. Then, without looking at the file, write down five edges you remember. Open the file and check. Seeing the picture and the edge-list side by side is what makes “a graph is vertices and edges” stop being abstract.
Rep 3 — Vocabulary cold
Close the book. On paper, define each term in one clause, with one example: vertex, edge, directed, undirected, weighted, unweighted, degree, path, cycle, connected, connected component. Then open §7.2 and check. Any term you got wrong, write its definition three times. You will use every one of these words for the rest of your career; own them now.
Reps 4–6: Storing the Graph Two Ways
Rep 4 — Edge list to both representations
Write two functions that take the same edge list and build the two representations:
def to_adjacency_list(edges):
"""edges: list of (a, b) pairs. Return dict: vertex -> set of neighbors."""
adj = {}
for a, b in edges:
adj.setdefault(a, set()).add(b)
adj.setdefault(b, set()).add(a) # undirected
return adj
def to_adjacency_matrix(edges):
"""Return (labels, matrix). labels[i] is the vertex for row/col i;
matrix[i][j] == 1 iff there is an edge i--j."""
# TODO: collect the distinct vertices, assign each an index,
# build a V-by-V grid of zeros, then set 1s for each edge (both directions).
...Finish to_adjacency_matrix. Test both on a tiny edge list [("A","B"), ("B","C"), ("A","C")] (a triangle). Confirm the adjacency list has three vertices each with two neighbors, and the matrix is the symmetric 3×3 all-ones-off-diagonal grid.
Rep 5 — Measure the space tradeoff yourself
Run graph_representations.py. Predict first: for the 200-vertex chain (sparse, 199 edges) and the 200-vertex complete graph (dense, 19,900 edges), which representation will use less memory, and roughly by how much? Then read the measured bytes. Write down: (a) which won in each case, (b) the matrix’s byte count for sparse vs. dense — why is it identical?, and (c) the rule of thumb in one sentence. This is the §7.3 lesson in numbers you watched the machine produce.
Rep 6 — The cost table, from memory
Close the book. On paper, reproduce the §7.3 comparison table: for adjacency list and adjacency matrix, fill in space, “who are v’s neighbors?”, “is there an edge A—B?”, and best when the graph is…. Then open the book and check. Any cell you got wrong, write three times. This is the row of your master cost table that graphs add.
Reps 7–9: Breadth-First Search (the Queue)
Rep 7 — BFS shortest hops by hand, then by code
Take the graph A--B, A--C, B--D, C--D, D--E. By hand, on paper, trace BFS from A: write the queue contents at every step and the distance you assign each vertex. Predict the shortest hops from A to E. Then implement bfs_shortest_hops(adj, start, goal) with collections.deque (start from the chapter’s version, but type it yourself) and confirm the code agrees with your hand-trace. If they disagree, your hand-trace is the bug — find it.
Rep 8 — Recover the actual path
Extend BFS to return the path, not just its length, using a parent map:
from collections import deque
def bfs_path(adj, start, goal):
if start == goal:
return [start]
visited = {start}
queue = deque([start])
parent = {start: None}
while queue:
v = queue.popleft()
for n in sorted(adj.get(v, ())):
if n not in visited:
visited.add(n)
parent[n] = v
if n == goal:
# TODO: walk parent[] backward from goal to start,
# then reverse, and return the path list.
...
queue.append(n)
return NoneFinish the path-rebuild. Test on the ministry data: bfs_path(adj, "Maya", "Hannah") should return ['Maya', 'Priya', 'Esther', 'Hannah'] (a 3-hop path). Confirm its length matches bfs_shortest_hops for the same pair.
Rep 9 — Prove the queue matters
Take the BFS from Rep 7 and replace deque with a plain list, using queue.pop(0) instead of popleft(). Confirm it still gives the correct answer — then time both versions on a graph of 50,000 vertices in a long chain. Write one sentence: the list version is correct but secretly O(V²) because each pop(0) is O(V); this is the exact quadratic trap from Chapter 2’s Common Bugs, now hiding inside a graph traversal.
Reps 10–11: Depth-First Search and Components (the Stack)
Rep 10 — Swap the queue for a stack
Write dfs_reachable(adj, start) two ways: once recursively (the call stack), once with an explicit list as a stack (stack.pop()). Run both on the ministry data from Maya and confirm they return the same set of 12 reachable people. Then, in writing, answer: structurally, what is the only difference between your iterative DFS loop and a BFS loop? (Answer: BFS pops the oldest with popleft(); DFS pops the newest with pop(). Same skeleton, opposite shape.)
Rep 11 — Count the islands
Implement connected_components(adj) that returns a list of sets, one per component (start from §7.6). Run it on the ministry data. Predict first: how many components, and who is in each? Confirm you get two — the twelve around Maya, and {Phoebe, Silas}. Then write two sentences: why does the same DFS that answers “is A connected to B?” also let you count islands? (Answer: each DFS run from an unseen vertex reaches exactly one whole island; counting the runs counts the islands.) Finally: what one edge would you add to make the whole body connected? Name it.
Done? One Last Thing.
From scratch, no looking — build the whole pipeline cold:
# 1. Model: vertices are people, edges are 'shares a small group',
# undirected, unweighted. (Write this sentence in a comment.)
# 2. Load small_group_edges.csv into an adjacency list.
# 3. Answer all three, printing each:
# - shortest hops from Maya to Tobias (BFS)
# - is Maya connected to Silas? (DFS)
# - how many connected components? (DFS over all vertices)You may look at the CSV format and at collections.deque’s name — nothing else. Write the loader, bfs_shortest_hops, dfs_reachable, and connected_components from memory. Run it. If you get 6 hops, False, and 2 components, you have the move — seeing the graph, storing it, and walking it both ways — and the project’s Normal tier is already in your hands.
Up next: Project 7 — Project 7: Model and Traverse a Network.