Graphs — Brief ☧
Deep version → | Lab → | Flashcards →
Q: The apostle Paul traveled from Antioch to Iconium, from Iconium
to Lystra, and from Lystra to Derbe. He also traveled from Antioch
directly to Perga. If you had to draw these journeys on a map, what
would it look like?
A: You would draw a dot for each city and an arrow for each
journey — from the city Paul left to the city he arrived at. Five
dots, four arrows. That picture is a
graph: each dot is called a node
(or vertex), and each arrow is a directed edge. "Directed" because
the arrow points one way — Paul traveled from Antioch to Iconium,
not the reverse on this leg.
Q: What if we only cared that two cities were connected, not which
direction Paul traveled?
A: Then you would draw plain lines instead of arrows. That is an
undirected graph. Think of a network of roads between cities — you
can drive either way. But Paul's missionary itinerary has a clear
sequence, so directed edges capture it better.
Q: Can Paul reach Derbe starting from Antioch?
A: Follow the arrows: Antioch → Iconium → Lystra → Derbe. Yes,
there is a path — a sequence of edges connecting the start to the
destination. Finding whether such a path exists is what graph traversal
algorithms compute.
Q: What if we want the shortest path — the fewest stops?
A: Start at Antioch and visit every city exactly one hop away first.
Then visit every city two hops away. Then three. The first time you
reach Derbe, you have found the shortest path. This layer-by-layer
approach is called breadth-first search (BFS). It uses a
queue — just like a line of people
waiting: first in, first out.
There is also depth-first search (DFS), which dives as deep as it
can along one route before backtracking. DFS uses a
stack — last in, first out, like a
stack of plates.
Q: Could a graph have a loop — a path that brings you back to
where you started?
A: Yes, that is called a cycle. If Paul traveled Antioch →
Iconium → Antioch, that would be a cycle. A graph with no cycles is
called a DAG (directed acyclic graph). DAGs are special because
you can line up their nodes in order — a topological sort — so
every edge points forward.
Q: How does this connect to our FPGA?
A: The dependency graph of
miniKanren goals is a directed graph. Tarjan's SCC algorithm finds
groups of mutually recursive goals
that must be solved together — exactly what our scheduler does in
hardware. And topological sort determines the order goals are evaluated.
Paul's First Missionary Journey
Antioch
/ \
v v
Iconium Perga
|
v
Lystra
|
v
Derbe- Nodes = cities (5)
- Edges = journeys (4, directed)
- Path = sequence of edges from start to end
- Cycle = path that returns to its starting node
- DAG = a directed graph with no cycles
Why Graphs Matter
| Concept | Graph Application | FPGA Connection |
|---|---|---|
| Goal dependencies | Directed graph | Scheduler ordering |
| Mutual recursion | Strongly connected components | SCC fixpoint engine |
| Shortest path | BFS / Dijkstra | Contraction order heuristics |
| Topological sort | DAG ordering | Goal execution order |
The takeaway from this table is that graphs are not just an abstract concept you study in a textbook — they are the actual data structure that governs how the FPGA schedules its work. When miniKanren goals depend on each other (goal A needs the result of goal B), those dependencies form a directed graph. The FPGA's scheduler uses topological sort on that graph to decide which goal to evaluate first. When goals are mutually recursive (A depends on B and B depends on A), Tarjan's algorithm detects those cycles and groups them together for simultaneous fixpoint computation.
Graphs are the skeleton of computation. Every time the FPGA decides which goal to evaluate next, it is walking a graph.
Now that you understand the basic vocabulary of graphs — nodes, edges, paths, cycles, and DAGs — the deep version will show you the algorithms (BFS, DFS, Dijkstra, Tarjan) that operate on these structures, complete with implementations and their connections to FPGA scheduling.
Soli Deo Gloria