Day 63 — DAGs & topological order

Day 63 — DAGs & topological order

Stage VI · concept day
Goal: Characterize DAGs; prove topological orders exist iff the digraph is a DAG; understand Kahn and DFS-based topo ideas; longest path in a DAG via DP; scheduling / critical path lite.

Why this matters

Build systems, package managers, spreadsheets, course prerequisites, and make/cmake dependency graphs are DAGs when well-formed—and cyclic when you have a bug. Topological order is the legal execution/install order. Longest paths in DAGs give critical paths in project scheduling—polynomial, unlike general graphs.

Theory

Directed acyclic graph

A DAG is a directed graph with no directed cycles.

Equivalent / related facts:

1. \(G\) is a DAG.
   
2. \(G\) has a topological order (see below).
   
3. DFS on \(G\) produces no back edges.
   
4. Strongly connected components are all single vertices (condensation of any digraph is a DAG).

Topological order

A topological ordering of a digraph is a listing \(v_1,\ldots,v_n\) of all vertices such that every arc \(v_i\to v_j\) has \(i<j\) (all edges point forward in the list).

Theorem. A finite digraph has a topological order if and only if it is a DAG.

Proof sketch.

• \((\Rightarrow)\) If a cycle exists, vertices on the cycle cannot be ordered with all arcs forward.
  
• \((\Leftarrow)\) Every finite DAG has a vertex of in-degree 0 (else walking backward forever yields a cycle). Place it first; delete it; repeat (induction). This is Kahn’s algorithm idea.

Non-uniqueness: many topos if incomparable vertices (e.g. two sources).

Kahn’s algorithm (idea)

1. Compute in-degrees; enqueue all in-degree 0.
   
2. While queue nonempty: pop \(u\), append to order; for each out-neighbor \(v\), decrement in-degree; if 0, enqueue.
   
3. If output size \(<n\), a cycle exists (not a DAG).

Hand-simulate with a table of in-degrees over time.

DFS-based topological sort (idea)

Run DFS; list vertices in decreasing finish time.
On a DAG, this is a topological order.
Why: for arc \(u\to v\), \(v\) finishes before \(u\) (cannot be back edge), so \(u\) appears later in decreasing-finish listing… actually: decreasing finish puts \(u\) before \(v\) if \(u\) finishes after \(v\)—standard CLRS argument: tree/forward/cross edges consistent with topo when no back edges.

Longest path in a DAG

In general graphs, longest path is hard (related to Hamilton). In a DAG, linear-time DP:

1. Topologically order vertices.
   
2. Let \(L(v)=\) length of longest path ending at \(v\) (or starting from sources—be consistent).
   
3. Process in topo order:

\[ L(v)=\max\{0\text{ or }L(u)+w(u,v):u\to v\}, \]

depending on node weights vs edge weights.

Node-weighted critical path: \(L(v)=w(v)+\max_{u\to v}L(u)\) with \(L=w\) at sources.

Scheduling / critical path lite

Tasks = vertices; precedence \(u\to v\) means \(u\) before \(v\); duration \(w(v)\).
Critical path = longest path in this DAG (minimum project time if infinite parallelism subject to precedence).
Slack = how much a task can slip without delaying project—optional awareness.

Sources and sinks

Source: in-degree 0. Sink: out-degree 0.
DAG with ≥1 vertex has ≥1 source and ≥1 sink.

Transitive closure (lite)

Reachability matrix; can be computed via DFS from each vertex or Floyd–Warshall culture—\(O(n^3)\) or better with structure.

Worked examples

Example 1 — Topo

Vertices \(A,B,C,D\); arcs \(A\to C,B\to C,C\to D,A\to D\).
Sources initially: \(A,B\). One topo: \(A,B,C,D\); also \(B,A,C,D\).
Not topo: \(A,C,B,D\) (\(B\to C\) points backward).

Example 2 — Cycle

Add \(D\to A\): no topo; Kahn stuck after processing some vertices.

Example 3 — Kahn table

Order step	Queue (alpha)	In-deg \(A,B,C,D\)	Emit
start	\(A,B\)	0,0,2,2
1	\(B\)	0,0,1,1	\(A\)
2	\(C?\) wait	after \(B\): C:0,D:1	\(B\)
…			\(C,D\)

Work carefully on paper.

Example 4 — DFS finish

On Example 1, DFS from \(A\) then \(B\) may finish \(D,C,A,B\)—decreasing finish: \(B,A,C,D\) or similar topo.

Example 5 — Longest path edges weight 1

Same graph unweighted hops: longest path length 2 (\(A\to C\to D\) or \(B\to C\to D\)).

Example 6 — Task durations

Tasks \(A(2),B(3),C(4),D(1)\); arcs as Ex. 1.
\(L(A)=2,L(B)=3\), \(L(C)=4+\max(L(A),L(B))=4+3=7\), \(L(D)=1+\max(L(C),L(A))=1+7=8\).
Project time 8; critical path \(B{-}C{-}D\).

Example 7 — Package install

Packages with dependencies form DAG if no circular depends; topo = valid install order.

Example 8 — Spreadsheet

Cell formulas referencing others: evaluation order = topo; circular ref = cycle.

Example 9 — Single vertex

DAG; topo: that vertex only.

Example 10 — Empty arcs

Any order is topological.

Example 11 — Unique topo

Hamiltonian path that includes all as only linear extension—e.g. a single directed path graph has unique topo.

Example 12 — Condensation

Any digraph’s SCCs contracted → DAG of components; topo of condensation = order of processing components.

Example 13 — Detect cycle via Kahn

If queue empties early, remaining vertices all have positive in-degree → cycle among them.

Example 14 — Longest path DP table

Process \(A,B,C,D\): fill \(L\) as Ex. 6.

Example 15 — Why general longest path hard

If you could longest-path in general graphs efficiently, you could detect Hamilton paths—NP-hard culture (Day 66).

Exercises

1. Define DAG and topological order.
   
2. Prove: cycle ⇒ no topo.
   
3. Prove: finite DAG ⇒ vertex of in-degree 0.
   
4. Find all topological orders of Ex. 1.
   
5. Kahn full trace on Ex. 1.
   
6. Add one arc to create a cycle; show Kahn fails.
   
7. DFS finish method on a 5-vertex DAG you draw.
   
8. Longest path (hop count) in a tournament that is a DAG (transitive).
   
9. Critical path with node weights on a 5-task chain.
   
10. Course prereqs: CS1→CS2→OS, CS1→DS→OS: topos and critical if equal duration.
    
11. True/false: unique topo ⇔ underlying structure is a Hamiltonian path of forced order.
    
12. CS: make dependency DAG.
    
13. Number of topos of \(n\) isolated vertices: \(n!\).
    
14. Number of topos of a directed path of \(n\): 1.
    
15. Condensation of a digraph with one 2-cycle and one extra vertex.
    
16. Prove sinks exist in finite DAGs.
    
17. Edge \(u\to v\) with both in-degree 0? Impossible unless… no, \(v\) would have in-degree ≥1.
    
18. Schedule with parallel processors lite: critical path still lower bound.
    
19. Implement? No—hand DP only.
    
20. Find longest path in DAG with negative edge weights (still OK if no cycle).
    
21. Challenge: count topological orders of a small poset (Day 40 link).
    
22. Why DFS back edge ⇔ cycle (directed).
    
23. Give two nonisomorphic DAGs on 4 verts with different # topos.
    
24. Package: A needs B,C; B needs D; C needs D—list topos.
    
25. Write a 1-page cheat sheet: Kahn + DP longest path.

CS connection

• Build systems, package managers, module loaders.
  
• Instruction scheduling / compiler dependency DAGs.
  
• Data pipelines / Airflow-style task graphs.
  
• Critical path method (CPM) in project management.
  
• Typeclass / trait resolution order culture.

Common pitfalls

Pitfall	What to do instead
Topo on undirected graphs	Need orientation / digraph
Assuming unique topo	Many DAGs have many
Longest path algorithms on cyclic graphs	NP-hard; only DAG DP
Kahn without cycle check	Compare output length to \(n\)
Confusing in-degree 0 with source after deletes	Dynamic in-degrees

Checkpoint

• DAG ⇔ has topo order
  
• Kahn hand simulation
  
• DFS finish idea
  
• Longest path DP on DAG
  
• Critical path one example
  
• Exercises 1–15
  
• Cycle detection via Kahn / back edge

Two personal takeaways:

1. …
   
2. …

Selected mini-solutions

3. If all in-degree ≥1, follow incoming arcs backward; finite ⇒ cycle.
   
4. \(A,B,C,D\) and \(B,A,C,D\) only (C before D; A,B before C).
   
5. Essentially yes for the partial order being a total order.
   
6. \(n!\).
   
8. \(D\) first; then \(B,C\) any order; then \(A\): two topos \(D,B,C,A\) and \(D,C,B,A\).

Deepening notes

Why every finite DAG has a source

If every vertex has in-degree ≥1, start anywhere and walk backward along incoming arcs; finite vertex set ⇒ repeat ⇒ directed cycle. Contradiction.

Kahn correctness sketch

Each emitted vertex had in-degree 0 in the residual graph, so all its predecessors already emitted—hence all arcs point forward in the output. If not all emitted, residual has min in-degree ≥1 ⇒ cycle.

Critical path formulas

Node weights \(w(v)\):
\(L(v)=w(v)+\max_{u\to v}L(u)\) (sources: \(L=w\)).
Project duration \(\max_v L(v)\).
Edge-weighted longest path analogous with \(L(v)=\max_{u\to v}(L(u)+w(u,v))\).

Extra drills

D1. All topos of a small V-shaped DAG.
D2. Kahn fail on a 3-cycle.
D3. DFS finish topo on 5-vertex DAG.
D4. Critical path 6 tasks.
D5. Condensation of two SCCs with arcs between.
D6. Unique topo characterization.
D7. Longest hop path in a grid DAG (only right/up).
D8. Package diamond dependency topos count.

Flash

DAG ⇔ has topo; Kahn = peel in-degree 0; longest path DP in topo order; critical path = longest path.

Exam drill block

E1. Prove finite DAG has a source.
E2. All topological orders of a diamond DAG (A→C, B→C, A→D, B→D, C→E, D→E)—list.
E3. Kahn full table on that diamond.
E4. Detect cycle with Kahn when D→A added.
E5. Node-weighted critical path: invent 6 tasks.
E6. DFS finish topo on a path digraph.
E7. Why longest path on general graphs is hard (one sentence).
E8. Condensation of a digraph with one 2-cycle.
E9. Number of topos of empty digraph on 4 verts.
E10. Package: A needs B,C; B needs D; C needs D; E needs A—topos count.

Mini solutions

E2. Orders with \(\{A,B\}\) before \(\{C,D\}\) before \(E\), and \(A,B\) free, \(C,D\) free subject to their arcs—careful enumeration.
E9. \(4!=24\).
E10. \(D\) first; \(B,C\) free; \(A\); \(E\) last: 2 topos.

Topological order cheat sheet

Method	Idea	Detects cycles?
Kahn	Peel in-degree 0; emit; reduce successors	Yes—if leftover vertices
DFS finish	Emit on finish time reverse order	Yes—back edge to gray

Equivalent for finite digraphs: acyclic ⇔ has a topological order ⇔ every walk is a path (no return) ⇔ DFS has no back edges.

Longest path DP (node weights)

Process vertices in topo order.
\(L(v)=w(v)+\max_{u\to v} L(u)\) (sources: \(L(v)=w(v)\)).
Project length \(=\max_v L(v)\). Edge weights: \(L(v)=\max_{u\to v}(L(u)+w(u,v))\).
Why DAG only: general longest path is NP-hard; topo order makes DP valid.

Condensation

Contract each SCC to a supernode: the condensation is always a DAG. Edges between SCCs induce a partial order on components—build/deploy “layers.”

Synthesis

DAGs model dependencies without circular waits. Topological order linearizes prerequisites (Kahn or DFS). Longest/shortest paths become one-pass DP in topo order—critical path analysis. Condensation reduces general digraphs to DAG-of-SCCs.

S1. Kahn full trace on a 6-task dependency digraph.
S2. Critical path with invented node weights on that digraph.
S3. Cold: prove finite DAG has a source; unique topo ⇔ Hamiltonian path in the comparability sense (tournament of forced order).

Worked Kahn sketch (diamond)

Vertices \(A,B,C,D,E\); arcs \(A\to C,B\to C,A\to D,B\to D,C\to E,D\to E\).
Initial indeg: \(A,B=0\); \(C,D=2\); \(E=2\).
Emit \(A\) then \(B\) (or \(B\) then \(A\)): after both, \(C,D\) indeg 0.
Emit \(C,D\) in either order; then \(E\).
All topos: orders with \(\{A,B\}\) before \(\{C,D\}\) before \(E\), and \(A,B\) free, \(C,D\) free—\(2\cdot 2=4\) topos.

Unique topological order

A DAG has a unique topological order iff there is a Hamiltonian path that forces every consecutive pair—equivalently, for every \(i\), the \(i\)-th vertex in the order is the unique source of the residual graph at that step (indegree-0 set always size 1).

Shortest path on DAG (preview Day 64)

Same topo DP as longest path but with \(\min\) instead of \(\max\), and \(d(\mathrm{source})=0\) (or \(w\) edges). One pass; handles negative edge weights because no cycles.

Tomorrow

Day 64 — Shortest paths: weights; Dijkstra idea + nonnegativity; Bellman-Ford awareness; triangle inequality; Dijkstra invariant sketch.