Chapter 2 — Discrete mathematics
Lesson map
Lesson 02 published. Map, example, EX004.
flowchart TD
N0["Learning outcomes"]
N1["2.1 Graphs"]
N2["2.2 Transitive closure"]
N3["Lab — Lab — reaching dependencies"]
N4["2.3 Lab result"]
N5["2.4 Why it matters"]
N6["2.5 Cycles"]
N7["Counting paths"]
N0 --> N1 --> N2 --> N3 --> N4 --> N5 --> N6 --> N7
N7 --> EX["Worked example"]
EX --> Q["Exercise EX004"]
Logical drawing
flowchart LR
N0["Learning outcomes"]
N1["2.1 Graphs"]
N2["2.2 Transitive closure"]
N3["Lab — Lab — reaching dependencies"]
N4["2.3 Lab result"]
N5["2.4 Why it matters"]
N6["2.5 Cycles"]
N7["Counting paths"]
N0 --> N1 --> N2 --> N3 --> N4 --> N5 --> N6 --> N7 --> Q["EX004"]
[Learning outcomes]
|
v
[2.1 Graphs]
|
v
[2.2 Transitive closure]
|
v
[Lab — Lab — reaching dependencies]
|
v
[2.3 Lab result]
|
v
[2.4 Why it matters]
|
v
[2.5 Cycles]
|
v
[Counting paths]
|
v
[Worked example] --> [Exercise EX004]
Learning outcomes
You will (1) model software dependencies as directed graphs; (2) compute transitive dependencies with breadth-first search; (3) recognise shared nodes and cycles; (4) relate graph structure to supply-chain risk.
2.1 Graphs
A directed graph has nodes and arrows. Each package is a node; an arrow from A to B means A depends on B. ticket-web depends directly on three packages, which depend on others.
The direction of each arrow matters. If A depends on B, a flaw in B can affect A, but not the other way round. Drawing ticket-web this way shows at a glance which packages its own code calls and which arrive only because another package needs them.
2.2 Transitive closure
The set of all nodes reachable from ticket-web is its transitive dependency set. Every node in it is code that runs inside ticket-web, even if no Coastline developer chose it.
That last point changes how teams think about risk. Choosing three trusted packages does not mean trusting only three sets of maintainers; it means trusting everyone whose code those packages bring in. Kwame lists the transitive set alongside the direct one in every review, because advisories arrive for both, and the indirect ones are more likely to surprise the team.
Lab — Lab — reaching dependencies
"""Transitive dependencies of a synthetic ticketing app by breadth-first search."""
from collections import deque
deps = {"ticket-web": ["webfw", "fare-calc", "qr-make"], "webfw": ["router", "tmpl"], "fare-calc": ["decimal-x"],
"qr-make": ["imgkit", "zipx"], "imgkit": ["zipx"], "router": [], "tmpl": ["escape-html"], "decimal-x": [],
"zipx": [], "escape-html": []}
seen, q = set(), deque(["ticket-web"])
while q:
for d in deps[q.popleft()]:
if d not in seen:
seen.add(d); q.append(d)
print("direct:", len(deps["ticket-web"]), "transitive total:", len(seen))
print("reached via more than one path: zipx" if sum("zipx" in v for v in deps.values()) > 1 else "")
Run with python3 lab_graph.py. Verified output:
direct: 3 transitive total: 9
reached via more than one path: zipx
2.3 Lab result
ticket-web has 3 direct dependencies but 9 in total. zipx is reached by more than one path (from qr-make and from imgkit), so updating it may require coordinating two parents.
The breadth-first search visits each package once, using the seen set, so zipx is counted once even though two arrows lead to it. The work grows only in proportion to the number of packages and arrows, which is why tools can compute closures for real applications with hundreds of packages in moments. Six of the nine arrive only indirectly.
2.4 Why it matters
Decan, Mens and Constantinou (2018) measured how vulnerabilities in npm spread through such transitive links; Zimmermann et al. (2019) showed that a few packages and maintainers reach a large share of an ecosystem. Graph structure explains why one flaw can affect thousands of applications.
For Coastline, the practical lesson is that watching only direct dependencies misses most of the code that runs. Advisory monitoring must cover the whole transitive set, and upgrade plans must consider who else depends on a shared package.
2.5 Cycles
Some ecosystems allow cycles; search must track visited nodes, as the lab's "seen" set does, or it will loop forever.
Without tracking, a search entering A → B → A would revisit the same nodes endlessly. With a visited set, each node is processed once, cycles or not. Cycles also complicate upgrades, since the packages in a cycle may need to move together, so Kwame's tooling reports any cycle it finds as a note for the team rather than silently handling it.
Counting paths
Discrete mathematics also counts. If each of ticket-web's three direct dependencies brings two more, and each of those one more, the tree has up to 3 + 6 + 6 = 15 nodes before sharing is removed. Shared nodes such as zipx reduce the total but increase coupling: one upgrade decision affects several parents. Kwame keeps both numbers, unique nodes and paths, because the first measures how much code runs and the second how hard upgrades are to coordinate.
Worked example
Kwame draws the graph on the whiteboard for Ingrid's team. The template library tmpl, which had the flaw, is not a direct dependency: it arrives through the web framework. The team had not known it was there, which is why its advisory surprised them.
Synthetic case. The graph is synthetic.
Errors and limits
Real graphs include optional and development-only dependencies, which may not run in production.
Exercises
- EX004 — Lab counts. How many direct and total dependencies does the lab find? Rubric: 3 = 3 direct, 9 total; 2 = one; 1 = vague; 0 = none.
- EX005 — Shared node. Why is zipx notable? Rubric: 3 = reached by two paths; coordinate parents; 2 = partial; 1 = vague; 0 = none.
- EX006 — tmpl surprise. Why did the tmpl advisory surprise the team? Rubric: 3 = transitive via framework; unknown; 2 = partial; 1 = vague; 0 = none.
Synthesis
Dependencies form graphs; the transitive set is what really runs.
Continue studying — chapter 02 of 50
← Chapter 01 (draft) · Course chapter index · Chapter 03 (draft) →