Day 68 — Graphs in CS

Updated

July 30, 2026

Day 68 — Graphs in CS

Stage VI · concept day
Goal: Map common CS structures to graphs; use a modeling checklist; choose the right question (path, color, topo, matching, MST, short path); complexity culture (P vs NP names where Hamilton-relevant).

Why this matters

Stage VI tools only pay off when you recognize a graph in the wild and ask a precise question. Today is a pattern catalog: dependency graphs, call graphs, CFGs, social graphs, routing nets, state-transition systems—and a disciplined modeling checklist for Day 69 workshop and Gate VI.

Theory

Modeling checklist

When a word problem appears:

  1. What are the vertices? (Be concrete: packages, functions, basic blocks, people, routers, states.)
  2. What are the edges? Directed? Weighted? Multi?
  3. What property matters? Connectivity, cycles, order, distance, cut, matching, coloring, Euler/Hamilton…
  4. Which algorithm/theorem applies? BFS/DFS, topo, Dijkstra, Hall, Euler degrees, greedy color…
  5. Complexity reality: is the question poly-time solvable on this class, or hard (Hamilton/TSP/coloring general)?
  6. Sanity: tiny instance; does the model over/under-fit semantics?

Catalog of CS graphs

Dependency graphs

  • Vertices: packages, modules, tasks, build targets.
  • Arcs: “\(A\) depends on \(B\)” (orient \(A\to B\) or \(B\to A\) consistently—state convention: often “must build \(B\) before \(A\)” as \(B\to A\)).
  • Questions: cycle? (circular depends); topological install/build order; longest path = critical compile chain.
  • Tools: DAG check, Kahn/DFS topo, longest path DP.

Call graphs

  • Vertices: functions/methods.
  • Arcs: \(f\to g\) if \(f\) may call \(g\).
  • Questions: reachability (dead code?); strongly connected components (mutual recursion clusters); dominating entry points.
  • Tools: DFS/BFS, SCC condensation DAG.

Control-flow graphs (CFG)

  • Vertices: basic blocks.
  • Arcs: possible control transfers.
  • Questions: dominators; loops (back edges in DFS); reachability; path-sensitive analysis limits.
  • Tools: DFS edge types; dominator trees (awareness); not all paths feasible (semantics).

Social / trust graphs

  • Vertices: users.
  • Edges: friendship undirected; follow directed.
  • Questions: distance (degrees of separation); communities; influencers (degree/centrality); bridges.
  • Tools: BFS distance; cut vertices; bipartite user–content for recommendations.

Routing / computer networks

  • Vertices: routers/hosts.
  • Edges: links with latency/bandwidth weights.
  • Questions: shortest path; MST for broadcast trees; connectivity/fault tolerance (bridges).
  • Tools: Dijkstra/BFS; Kruskal/Prim; edge connectivity culture.

State-transition systems

  • Vertices: states of a protocol/FSM.
  • Arcs: labeled transitions.
  • Questions: reachable states; cycles (livelock/loops); shortest event sequence to a goal.
  • Tools: BFS on state graph; exponential state spaces (Day 53 counting!).

Interference / conflict graphs

  • Vertices: variables, exams, frequencies.
  • Edges: conflict.
  • Questions: chromatic number / coloring; clique lower bound.
  • Tools: greedy color; exact hard in general; special graph classes.

Bipartite incidence graphs

  • Parts: jobs/machines, clients/servers, documents/terms.
  • Questions: matching assignment; Hall feasibility.
  • Tools: matching algorithms; Hall check small cases.

Choosing a question (quick table)

English ask Graph question
Can X affect Y? Path / reachability
Circular dependency? Directed cycle
Valid order? Topological order
Fewest hops? BFS distance
Fastest with weights? Dijkstra/BF
Wire all sites cheaply? MST
Assign without conflict? Coloring / matching
Tour every road? Euler
Tour every city? Hamilton/TSP (hard)
Bottleneck person? Cut vertex

Complexity culture (names only where useful)

Problem Typical complexity culture
Connectivity, BFS/DFS, Dijkstra (nonneg), MST, Euler, bipartite matching, topo on DAG Polynomial (efficient)
Hamilton path/cycle, TSP, general coloring \(\chi\le k\) (\(k\ge 3\)), longest path general NP-hard / NP-complete decide
Planarity testing Polynomial (surprising historically)
4-color planar Always yes (theorem)—not a search for \(k=4\) decision on planar

Moral: model carefully—if you reduced your product feature to Hamilton, expect pain; if to BFS, ship it.

Weighted vs unweighted; directed vs undirected

Mis-orienting edges or forgetting weights is the #1 modeling bug. Write \(G=(V,E)\) explicitly once.

Multi-layer models

Sometimes you need two graphs (e.g. physical network + logical overlay). Don’t smash them without labeling.

Worked examples

Example 1 — Package manager

\(V=\) packages; arc \(A\to B\) if \(A\) requires \(B\) built first… Use topo for install; cycle = error.

Example 2 — Makefile

Targets and prerequisites: DAG ideally; make walks dependency graph.

Example 3 — Dead function

Call graph: functions not reachable from main / exports—DFS mark.

Example 4 — Infinite loop structure

CFG back edge to ancestor ⇒ loop in flowgraph (semantic nontermination needs more).

Example 5 — Friend recommendations

Undirected social: distance-2 vertices as candidates.

Example 6 — Network outage

Bridge edge: link whose failure disconnects—identify cut edges.

Example 7 — Protocol reachability

State machine 12 states: BFS from init; count reachable ≤12.

Example 8 — Exam schedule

Courses vertices; edge if shared student; \(\chi\) = min slots.

Example 9 — Job assignment

Bipartite workers–jobs; max matching.

Example 10 — Delivery

City graph weights travel time; Dijkstra warehouse to client.

Example 11 — Fiber backbone

Connect sites min cable: MST.

Example 12 — Garbage truck

Street edges must be traversed: Chinese Postman / Euler if even degrees.

Example 13 — Travel itinerary all cities

Hamilton/TSP—hard; use heuristics.

Example 14 — Register allocation

Interference graph coloring (Day 67).

Example 15 — Type of mistake

Using undirected graph for one-way streets: wrong reachability.

Exercises

  1. Write the modeling checklist from memory.
  2. Model npm/pip dependencies; what does a cycle mean?
  3. Model a CFG for a for loop with break—vertices/edges.
  4. Call graph vs CFG: one sentence difference.
  5. Social: define diameter of a friend graph.
  6. Network: when BFS vs Dijkstra.
  7. FSM: why state graph can be huge (product of variables).
  8. Exam coloring: construct conflict graph from a small table of student enrollments.
  9. Matching: 3 jobs 3 machines constraints—Hall check.
  10. Classify: “visit every city once” vs “traverse every road once.”
  11. Name a poly-time problem and an NP-hard problem from the table.
  12. Orient package depends two ways; show how topo meaning flips.
  13. MST vs shortest path tree: different goals—example.
  14. SCC in call graphs: mutual recursion cluster meaning.
  15. CS security: attack graph awareness (vertices states/privileges).
  16. Data lineage graph: path = provenance.
  17. Git commits DAG: merge parents—not a tree.
  18. True/false: every web link graph is a DAG.
  19. Choose tools for “critical path of project tasks.”
  20. Choose tools for “assign radio channels without interference.”
  21. Invent a CS scenario for bipartite matching.
  22. Invent a CS scenario that is wrongly modeled as Hamilton.
  23. Complexity: why 2-coloring easy but 3-coloring hard (culture).
  24. Multi-model: physical + logical network—what edges differ?
  25. One-page map: Stage VI algorithm → CS use case (fill table).

CS connection

This day is the CS connection. Capstone modeling (later) should reuse this catalog.

Common pitfalls

Pitfall What to do instead
Vague vertices (“the system”) Name atomic entities
Wrong direction on depends Write English for each arc
Asking Hamilton when Euler fits Edges vs vertices tours
Ignoring weights State unweighted hops vs cost
Exponential state spaces surprise Count first (Day 53)

Checkpoint

  • Checklist cold
  • 6 catalog types with vertex/edge/question
  • Poly vs NP-hard examples
  • Exercises 1–15
  • One original model written fully
  • Ready for modeling workshop

Two personal takeaways:

  1. …
  2. …

Selected mini-solutions

  1. Call graph: functions; CFG: basic blocks within/between.
  2. Hamilton vs Euler.
  3. BFS poly; Hamilton NP-complete.
  4. False—cycles everywhere.
  5. DAG longest path.
  6. Graph coloring.

Deepening notes

One-page algorithm→use map (fill)

Algorithm/theorem CS use
BFS
DFS / topo
Dijkstra
Kruskal/Prim
Matching/Hall
Coloring
Euler
Hamilton/TSP

Anti-catalog (wrong tools)

Ask Wrong tool Right tool
Min hops Dijkstra with random weights BFS
Build order Undirected connected DAG topo
Assign one job each Coloring Matching
Street sweep Hamilton Euler

Extra scenario drills

D1. Kubernetes service mesh latency—shortest path.
D2. Monorepo package graph—cycle CI fail.
D3. Classroom seating conflicts—coloring.
D4. Bike share stations rebalance—transport, not pure graph.
D5. Privilege escalation paths—attack graph reachability.
D6. CDN cache hierarchy—tree.
D7. Microservices rate-limit dependency—DAG critical.
D8. P2P overlay vs underlay—two graphs.

Flash checklist

V? E directed/weight? Question? Tool? Complexity? Sanity?

Exam drill block

E1. Model “courses with prerequisites” as a digraph; name the cycle question and the linearization question.
E2. Model “servers and latency links” for min-delay routing—weighted shortest path.
E3. Model “jobs and machines, each job one machine” as bipartite matching.
E4. Model “register interference” as coloring; \(\chi\) = min registers.
E5. Model “street sweeping” vs “visit each landmark once”—Euler vs Hamilton.
E6. Call graph vs control-flow graph: different \(V\) definitions.
E7. Poly-time: BFS connectivity; hard: Hamilton cycle—one sentence each.
E8. Package lockfile: DAG check fails ⇒ circular dependency error.
E9. True/false: (i) every CS graph problem is poly-time (ii) undirected topo order (iii) matching ≠ coloring.
E10. Write \(V\), \(E\), directed?, weighted?, question for a social “friend suggestion via common neighbors.”

Mini solutions

E1. \(V=\) courses; arc \(A\to B\) if \(A\) prereq of \(B\); cycle = impossible plan; topo = valid term order.
E5. Euler: edges (streets); Hamilton: vertices (landmarks).
E9. F; F (needs DAG/directed); T.
E10. \(V=\) users; undirected edges = friendship; question e.g. score common neighbors for non-adjacent pairs.

Complexity postcard

Easy (poly, typical) Hard (NP-complete classically)
Connectivity, BFS/DFS Hamilton path/cycle
Shortest path \(w\ge 0\) Longest path (general)
MST TSP
2-color / bipartite \(k\)-color \(k\ge 3\)
Matching bipartite …

Synthesis

CS graph work is model then ask. Wrong \(V\)/\(E\) choice is the usual bug—not the algorithm. Match the question to BFS, Dijkstra, topo, MST, matching, coloring, Euler, or “this is Hamilton/TSP hard.” Count state spaces when the graph is implicit (Day 53). Day 69 practices full writeups.

S1. Three original systems → full \(G=(V,E)\) + question + tool.
S2. One anti-model: show a wrong graph that invites the wrong algorithm.
S3. Cold: checklist six items without notes.
S4. Implicit graph: configuration space of a puzzle—when is BFS feasible?
S5. Pick one hard problem (TSP / Hamilton) and state the honest poly-time relaxation you would ship.

Tomorrow

Day 69 — Modeling workshop: 8–12 word problems → formal \(G=(V,E)\) + precise questions.