Project 7 — Model and Traverse a Network

“Two are better than one, because they have a good reward for their toil. For if they fall, one will lift up his fellow. But woe to him who is alone when he falls and has not another to lift him up!” — Ecclesiastes 4:9–10

Chapter: 7 — Graphs and the Shape of Connection Due: End of Week 7 Submit: A link to your code — a public GitHub repository — containing your source, the dataset, and MEMO.docx. See Appendix A for the Python/git toolchain setup and the repo workflow. Allowed tools: Python 3, the standard library (collections.deque, heapq, sys, tracemalloc), a non-AI editor, the textbook. Phase 1 (wk 1–8): AI is OFF. No assistants of any kind — not for the modeling, not for the traversals, not for the memo. The whole point of building these by hand is so that in Phase 2 you can direct an agent to choose a representation, having once paid the price of choosing badly yourself. (Phase 2 projects, wk 9–16, will require an agent-log.txt; this one forbids the agent entirely.)

The Setup

A growing church has a problem it doesn’t yet know how to name. It runs forty small groups, a dozen serving teams, and a prayer-chain, and people overlap across all of them — Maya is in a small group with Marcus, serves on the welcome team with Esther, and prays with Hannah. The pastor’s quiet worry is the one Ecclesiastes names: woe to him who is alone when he falls. Who, in this web of relationships, is actually connected to the body — and who is quietly an island, showing up but bound to no one who would notice if they fell away?

Nobody can answer that by reading a spreadsheet. The relationships are a graph, and the questions the pastor is really asking are graph questions: How many introductions apart are any two members? Is everyone reachable from the core, or are there isolated pockets? How many distinct fellowships are there, really?

You are the architect they called. You will take the relationship data they hand you — an edge list, the most common real-world graph format — and you will do the three things this chapter taught: model it (decide, in writing, what a vertex and an edge are), store it (choose a representation and pay for it on purpose), and traverse it (answer the pastor’s questions with BFS and DFS). And you will end, as every Phase 1 project ends, with a memo: not just the answers, but the honest accounting of which representation this dataset deserved and why.

The dataset is small on purpose. The discipline — see the graph, name the model, choose the representation, walk it correctly — is identical whether the body is fourteen people or fourteen thousand. You’re learning the move at a scale where you can hold all of it in your head at once.

Setup

A starter is provided in this chapter’s code/ folder:

• code/small_group_edges.csv — the dataset: an undirected edge list, person_a,person_b per line, 14 people and 17 edges. Comment lines start with #. Don’t edit it by hand.
• code/graph_representations.py — both representations (list and matrix) with a runnable space-measurement demo. Read it; the Medium tier extends its idea.
• code/traversal.py — reference BFS and DFS on an adjacency list. Study it, but for the project you build your own from the starter.
• code/p7_starter.py — the scaffold you will finish. It has a working load_edges (do not change it) and stubbed function shapes with TODOs for every tier.

You will write:

• network.py — your finished program (start from p7_starter.py).
• MEMO.docx — the report. This is the architect’s half of the grade.

Learning Targets

By completing this project, you will demonstrate that you can:

• Model a real dataset as a graph — naming vertices, edges, direction, and weight in writing before coding.
• Load an edge-list CSV into an adjacency list with the modeling decisions baked into the loader.
• Implement BFS with a queue to answer shortest-number-of-hops, and recover the actual path.
• Implement DFS (recursive and/or iterative) to answer reachability and connectivity.
• (Medium) Build the adjacency-matrix representation and measure the space cost on sparse vs. dense graphs.
• (Hard) Answer a real query the dataset makes interesting — connected components or weighted shortest path (Dijkstra) — and write the representation-choice memo with measured numbers.

Normal Tier

Goal: Model the dataset, store it as an adjacency list, and answer the pastor’s three questions with BFS and DFS.

Required features

1. Written model, first. At the top of MEMO.docx, before any results, write your four modeling decisions (§7.8): what is a vertex; what is an edge; is it directed or undirected, weighted or unweighted; which queries you must answer. Commit to them. The rest of the project must be consistent with what you wrote here.
2. Load into an adjacency list. Read small_group_edges.csv into a dict mapping each person to the set of their neighbors. Skip blank and # lines. Because the relationship is undirected, record each edge in both directions.
3. Shortest hops (BFS). Implement shortest_hops(adj, start, goal) using collections.deque. Return the fewest number of hops, or None if unreachable. Mark vertices visited on enqueue, not dequeue.
4. The actual path (BFS). Implement shortest_path(adj, start, goal) that returns the list of people on a shortest path (e.g. ['Maya', 'Priya', 'Esther', 'Hannah']), or None.
5. Connectivity (DFS). Implement reachable_from(adj, start) (DFS, recursive or iterative — your call, document which) and are_connected(adj, a, b) on top of it.
6. Answer the pastor. Your main must print, clearly labeled: (a) shortest hops and the path from Maya to Tobias, (b) whether Maya is connected to Silas, and (c) the size of the group reachable from Maya.

Example output (your network.py should print something like)

Modeling: vertices = people, edges = 'shares a group', undirected, unweighted.
Loaded 14 people, 17 relationships.

Q1  shortest hops Maya -> Tobias: 6
    path: Maya -> Priya -> Esther -> Hannah -> Ruth -> Samuel -> Tobias
Q2  Maya connected to Silas? False
Q3  reachable from Maya: 12 of 14 people

Normal-tier rubric (out of 100)

Medium Tier (+up to 25% extra credit)

M1. The adjacency-matrix representation

Add to_adjacency_matrix(adj) returning (labels, matrix) where labels[i] is the vertex for row/column i and matrix[i][j] == 1 iff there is an edge. Verify it agrees with your adjacency list: for several pairs, matrix[index[a]][index[b]] == (b in adj[a]). Implement has_edge on the matrix in O(1) and note in the memo why the list’s edge-check is not O(1).

M2. Measure the space cost on sparse vs. dense

Build two synthetic graphs at the same vertex count V (say V = 200): a sparse one (a chain, E = V−1) and a dense one (complete, every pair connected). Store each in both representations and measure the bytes (use sys.getsizeof per the chapter demo, or tracemalloc for a fuller picture). Produce a small table — representation × density × bytes — and add it to MEMO.docx. Confirm the §7.3 rule of thumb: list wins sparse, matrix wins dense, and the matrix’s byte count is flat across densities.

Hard Tier (+up to 25% additional extra credit)

Pick at least one of H1 / H2. Then do H3 (the memo) regardless — it is the architect’s deliverable and the soul of the project.

H1. Connected components (count the islands)

Implement connected_components(adj) returning a list of sets, one per component. Report how many fellowships the dataset actually contains and who is in each. Then answer the pastor’s real question in the memo: which members are isolated from the body, and what single relationship (one edge) would connect everyone? Name the edge and justify it.

H2. Weighted shortest path (a simple Dijkstra)

Extend the model: give each edge a weight (e.g., “weeks since these two last met” — a higher number means a weaker tie). Load a weighted edge list (person_a,person_b,weight) and implement dijkstra(weighted_adj, start) using heapq to find the least-total-weight path from one person to another. Show a case where the fewest-hops path (BFS) and the lowest-weight path (Dijkstra) differ, and explain in the memo why the weighting changed the answer.

H3. The representation memo (required for any Hard credit)

This is the architect’s paragraph. In MEMO.docx, with your measured numbers from M2 in hand, answer:

• For this dataset (its real V, E, and density), which representation is right — list or matrix — and why?
• Which query drove your choice (neighbor-walking, which favors the list, or edge-lookup, which favors the matrix)?
• What would have to change about the dataset — how much denser, how many vertices, which dominant query — to flip your recommendation to the other representation? Give a concrete threshold, not a vibe.

Cite your own numbers. “The list is usually better” earns nothing. “At density 9% (17 edges of 91 possible) the list uses N bytes vs. the matrix’s M, and the dominant query is neighbor-walking for BFS/DFS, so the list is right; I would switch to a matrix only if density rose past ~50% and edge-lookup became the hot query, because [your numbers]” earns the credit. That sentence — the measured, conditional, committed recommendation — is the entire skill of the book at the smallest scale.

Submission

Submit one URL: a public GitHub repository (see Appendix A for setup).

What the repo must contain

1. network.py — your finished program (the provided load_edges unchanged).
2. small_group_edges.csv — the dataset, unchanged (plus any weighted variant you made for H2).
3. MEMO.docx — the report, in this shape:

# Project 7 — Model and Traverse a Network

**Tier targeted:**  Normal / Medium / Hard
**Machine:**  (CPU, RAM, OS, Python version — space measurements depend on it)

## Model (written BEFORE coding)
- A vertex is: ____
- An edge is: ____  (directed/undirected, weighted/unweighted)
- Queries I must answer: ____

## Results
- Q1 shortest hops Maya -> Tobias: ____ (path: ____)
- Q2 Maya connected to Silas? ____
- Q3 reachable from Maya: ____ of ____

## Space measurement (Medium)
(table: representation × sparse/dense × bytes; confirm the rule of thumb)

## Components / weighted path (Hard H1 / H2)

## Representation recommendation (Hard H3)
(measured, conditional, committed: which rep, which query drove it,
 what would flip the decision — with numbers)

**AI usage:**  NONE — Phase 1.  Signed: <your name>

4. README.txt — how to run network.py, what it prints, and the AI honesty line.

Hints (Read Before You Begin)

• Write the model first and don’t go back and “fix” it. If you decide mid-project that edges should have been directed, say so in the memo — the honest reasoning is the deliverable, not a clean-looking after-the-fact story. The gap between your first model and what you learned is the lesson.
• deque, never list.pop(0), for the BFS queue. from collections import deque, then popleft(). The list version is correct but secretly O(V²) — the Chapter 2 quadratic trap, now inside a traversal. The grader will check.
• Mark visited on enqueue. Add a vertex to visited the instant you push it onto the queue, not when you pop it. Otherwise a popular vertex gets enqueued many times and both your answer and your speed suffer.
• DFS needs a visited set or it loops forever. Unlike a tree, a graph has cycles. The membership check before recursing is the one line that separates graph DFS from tree traversal — do not omit it.
• For the space measurement, measure the same V at two densities. Comparing a tiny sparse graph to a huge dense one proves nothing. Hold V fixed (the chapter demo uses 200) and vary only the edge count, so the only thing changing is density.
• The matrix’s byte count should be identical sparse vs. dense. If it isn’t, you’re not measuring the matrix — you’re measuring something that secretly skips empty cells. The matrix pays V² no matter what; that flatness is the point.

What Mastery Looks Like (Beyond the Rubric)

A great Project 7 is not a great pile of traversal code — BFS and DFS are each a dozen lines, and you can find them in any reference. A great Project 7 is a great model and a great memo. The model names the vertices and edges in one crisp sentence each and gets the directed/weighted cell right. The traversals are correct because the model was right, not in spite of a fuzzy one. And the memo reads like an architect thinking out loud with numbers in hand: “this graph is 9% dense, the hot query is neighbor-walking, the list uses a fifth the memory of the matrix here — list it is; I’d flip to a matrix only past ~50% density with edge-lookup as the dominant query, and here’s the byte math that says so.”

A great Hard tier turns the algorithm into a finding. Connected components isn’t “I got two sets” — it’s “Phoebe and Silas are an island; one edge from Silas to Samuel would make the body fully connected, and here’s why that pair is the right bridge.” The Dijkstra variant isn’t “I implemented it” — it’s “the fewest-hops path and the strongest-ties path disagree for Maya→Ruth, and the disagreement is exactly what the weighting was meant to capture.” The algorithm is the easy part. Making it answer a real human question — who is alone when they fall? — is the architect’s part.

Coach’s Note — Students rush this project because BFS and DFS are “just a dozen lines.” Those students hand in correct traversals on a graph they never actually modeled, and a memo that says “the list is better” with no numbers. They learned nothing, because the learning was never in the dozen lines — it was in committing to a model, choosing a representation on purpose, and defending the choice with measurements you made yourself. Slow down. Write the model. Measure both representations. Make the conditional, numbered recommendation. That loop — see, model, choose, justify — repeated for sixteen weeks at growing scale, is how a coder becomes an architect.

When You’re Done

1. Run network.py. Confirm it prints the model line and answers all three questions with the right values (6, False, 12 of 14).
2. Re-read your model. Is every later decision — undirected loading, the queries you ran — consistent with what you wrote first? If not, fix the code, or explain the change in the memo.
3. For Medium: read your space table. Is the matrix’s byte count flat across densities? Does the list win sparse and lose dense? If not, your measurement is lying — find out why.
4. Read MEMO.docx aloud. Could the pastor — not an engineer — read your Hard-tier finding and act on it (go connect the isolated pair)? If not, rewrite for him.
5. Push to GitHub. Submit the URL.
6. Read Chapter 8. Concurrency next — and the Phase 1 midterm — where many hands learn to work as one without chaos, and where the queue you used for BFS becomes the thread-safe queue that lets producers and consumers hand work to one another without losing a single item.

A theological footnote. Ecclesiastes does not say the strong need no one; it says the one who falls needs another to lift him, and that the one who is alone when he falls has no one. The Preacher is describing, without the vocabulary, a connected graph — a body in which every member has a path to another who would notice the fall. When you ran connected components and found the pair no path reached, you found, in the smallest possible key, the thing the church has always watched for: the member who, if they fell, has no one. The graph did not invent that concern; it made it visible and addressable. That is what good tools do for love — they turn a vague, anxious “is anyone slipping away?” into a precise “these two, here, need a bridge.” The architect’s measurement and the pastor’s care, the same shape. Go build the bridge.

See you next week.