DAGs and Topological Order

A Directed Acyclic Graph (DAG) (Definition 6.2.4, notes p. 92) is exactly what
it sounds like: a directed graph with no cycles. This single restriction gives
DAGs a remarkable property — they can be topologically sorted.

Topological sort: arrange the vertices in a linear order
$v_{\pi(1)}, v_{\pi(2)}, \dots, v_{\pi(n)}$ such that every edge points
forward: if $(u, v) \in E$, then $u$ comes before $v$ in the ordering.

Why this is possible in every DAG: every DAG has at least one source (vertex
with $\text{indeg} = 0$) and at least one sink (vertex with $\text{outdeg} = 0$).
This is provable by induction on the number of vertices (you can always strip off
a source, then argue on the smaller DAG).

Algorithm sketch (Kahn's algorithm):
1. Collect all sources (indegree 0) into a queue.
2. Output one source; delete its outgoing edges.
3. Any new source goes into the queue.
4. Repeat until all vertices are output.

DAGs are everywhere in symbolic AI:
- Task scheduling: a task $v$ depends on tasks $u_1, \dots, u_k$ that must
finish first. Encode as a DAG.
- Bayesian networks: variables are nodes; conditional dependencies are edges.
DAGs guarantee no circular causation.
- Causal inference: "X causes Y" is a directed edge; cycles would mean X causes
itself, which is ill-defined.

Definitions 6.1.6 (notes p. 85):
- Source: $v$ with $\text{indeg}(v) = 0$ (no predecessor).
- Sink: $v$ with $\text{outdeg}(v) = 0$ (no successor).