379 Intermediate

379: Directed Acyclic Graph (DAG) and Topological Sort

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "379: Directed Acyclic Graph (DAG) and Topological Sort" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Many real-world problems require ordering tasks where some must precede others: build systems (compile A before B if B imports A), package managers (install dependencies before dependents), course prerequisites, and spreadsheet cell evaluation. Key difference from OCaml: 1. **Recursion style**: OCaml handles recursive DFS cleanly as a local recursive function; Rust requires an inner `fn` (not closure) for recursive calls since closures cannot call themselves.

Tutorial

The Problem

Many real-world problems require ordering tasks where some must precede others: build systems (compile A before B if B imports A), package managers (install dependencies before dependents), course prerequisites, and spreadsheet cell evaluation. A Directed Acyclic Graph (DAG) models these dependency relationships, and topological sort produces a valid linear ordering. If the graph contains a cycle, no valid ordering exists — which signals a circular dependency error.

Topological sort powers make, cargo, npm, pip, Makefiles, Apache Airflow DAG scheduling, and CPU instruction scheduling in compilers.

🎯 Learning Outcomes

• Understand why cycles make topological ordering impossible and how to detect them

• Learn Kahn's algorithm (in-degree based, BFS) vs. DFS post-order reversal

• Understand how in-degree tracking drives the BFS-based approach

• See how Option<Vec<usize>> encodes success/failure of cycle detection in Rust

• Learn why DAGs are foundational for dependency resolution systems

Code Example

#![allow(clippy::all)]
//! Directed Acyclic Graph (DAG) and Topological Sort
//!
//! Kahn's algorithm for topological ordering.

use std::collections::VecDeque;

/// Topological sort using Kahn's algorithm
/// Returns None if graph has a cycle
pub fn topological_sort(adj: &[Vec<usize>], n: usize) -> Option<Vec<usize>> {
    let mut in_degree = vec![0usize; n];
    for u in 0..n {
        for &v in &adj[u] {
            in_degree[v] += 1;
        }
    }
    let mut queue: VecDeque<usize> = (0..n).filter(|&v| in_degree[v] == 0).collect();
    let mut result = Vec::new();
    while let Some(u) = queue.pop_front() {
        result.push(u);
        for &v in &adj[u] {
            in_degree[v] -= 1;
            if in_degree[v] == 0 {
                queue.push_back(v);
            }
        }
    }
    if result.len() == n {
        Some(result)
    } else {
        None
    }
}

/// Check if a directed graph has a cycle
pub fn has_cycle(adj: &[Vec<usize>], n: usize) -> bool {
    topological_sort(adj, n).is_none()
}

/// DFS-based topological sort (returns reverse postorder)
pub fn topological_sort_dfs(adj: &[Vec<usize>], n: usize) -> Option<Vec<usize>> {
    let mut visited = vec![0u8; n]; // 0=unvisited, 1=in progress, 2=done
    let mut result = Vec::new();

    fn dfs(u: usize, adj: &[Vec<usize>], visited: &mut [u8], result: &mut Vec<usize>) -> bool {
        if visited[u] == 1 {
            return false;
        } // cycle
        if visited[u] == 2 {
            return true;
        }
        visited[u] = 1;
        for &v in &adj[u] {
            if !dfs(v, adj, visited, result) {
                return false;
            }
        }
        visited[u] = 2;
        result.push(u);
        true
    }

    for u in 0..n {
        if visited[u] == 0 && !dfs(u, adj, &mut visited, &mut result) {
            return None;
        }
    }
    result.reverse();
    Some(result)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_topo_sort_kahn() {
        let mut adj = vec![vec![]; 4];
        adj[0].push(1);
        adj[0].push(2);
        adj[1].push(3);
        adj[2].push(3);
        let order = topological_sort(&adj, 4).unwrap();
        assert_eq!(order[0], 0);
        assert_eq!(*order.last().unwrap(), 3);
    }

    #[test]
    fn test_cycle_detection() {
        let mut adj = vec![vec![]; 3];
        adj[0].push(1);
        adj[1].push(2);
        adj[2].push(0);
        assert!(has_cycle(&adj, 3));
    }

    #[test]
    fn test_no_cycle() {
        let mut adj = vec![vec![]; 3];
        adj[0].push(1);
        adj[1].push(2);
        assert!(!has_cycle(&adj, 3));
    }

    #[test]
    fn test_dfs_sort() {
        let mut adj = vec![vec![]; 4];
        adj[0].push(1);
        adj[0].push(2);
        adj[1].push(3);
        adj[2].push(3);
        let order = topological_sort_dfs(&adj, 4).unwrap();
        assert_eq!(order[0], 0);
    }

    #[test]
    fn test_empty_graph() {
        let adj: Vec<Vec<usize>> = vec![vec![]; 3];
        let order = topological_sort(&adj, 3).unwrap();
        assert_eq!(order.len(), 3);
    }
}

(* DAG and Topological Sort in OCaml using Kahn's algorithm *)

let topological_sort adj n =
  let in_degree = Array.make n 0 in
  Array.iter (fun neighbors ->
    List.iter (fun v -> in_degree.(v) <- in_degree.(v) + 1) neighbors
  ) adj;
  let queue = Queue.create () in
  Array.iteri (fun v d -> if d = 0 then Queue.add v queue) in_degree;
  let result = ref [] in
  while not (Queue.is_empty queue) do
    let u = Queue.pop queue in
    result := u :: !result;
    List.iter (fun v ->
      in_degree.(v) <- in_degree.(v) - 1;
      if in_degree.(v) = 0 then Queue.add v queue
    ) adj.(u)
  done;
  if List.length !result = n then Some (List.rev !result)
  else None  (* cycle detected *)

let () =
  (* Build graph: 5 -> 2 -> 0 -> 1, 5 -> 0, 4 -> 0, 4 -> 1, 2 -> 3, 3 -> 1 *)
  let n = 6 in
  let adj = Array.make n [] in
  let edges = [(5,2);(5,0);(4,0);(4,1);(2,0);(2,3);(3,1)] in
  List.iter (fun (u,v) -> adj.(u) <- v :: adj.(u)) edges;
  match topological_sort adj n with
  | Some order ->
    Printf.printf "Topological order: ";
    List.iter (fun v -> Printf.printf "%d " v) order;
    print_newline ()
  | None ->
    Printf.printf "Graph has a cycle!\n"

Key Differences

Recursion style: OCaml handles recursive DFS cleanly as a local recursive function; Rust requires an inner fn (not closure) for recursive calls since closures cannot call themselves.

Result encoding: Rust uses Option<Vec<usize>> where None means cycle detected; OCaml returns ('a list, unit) result or raises an exception.

Mutability: Rust's in-degree array is mut with explicit &mut references; OCaml uses a mutable int array with direct assignment.

Visited marking: Rust uses u8 array with constants (0/1/2); OCaml typically uses Hashtbl with variant values like type color = White | Gray | Black.

OCaml Approach

OCaml's functional style handles topological sort with recursive DFS naturally. The visited state is a mutable integer array or a Hashtbl. The DFS post-order collects into an accumulator list, then reverses it. OCaml's pattern matching handles the three-state visited array cleanly. Kahn's algorithm uses Queue.t for the BFS frontier.

Full Source

#![allow(clippy::all)]
//! Directed Acyclic Graph (DAG) and Topological Sort
//!
//! Kahn's algorithm for topological ordering.

use std::collections::VecDeque;

/// Topological sort using Kahn's algorithm
/// Returns None if graph has a cycle
pub fn topological_sort(adj: &[Vec<usize>], n: usize) -> Option<Vec<usize>> {
    let mut in_degree = vec![0usize; n];
    for u in 0..n {
        for &v in &adj[u] {
            in_degree[v] += 1;
        }
    }
    let mut queue: VecDeque<usize> = (0..n).filter(|&v| in_degree[v] == 0).collect();
    let mut result = Vec::new();
    while let Some(u) = queue.pop_front() {
        result.push(u);
        for &v in &adj[u] {
            in_degree[v] -= 1;
            if in_degree[v] == 0 {
                queue.push_back(v);
            }
        }
    }
    if result.len() == n {
        Some(result)
    } else {
        None
    }
}

/// Check if a directed graph has a cycle
pub fn has_cycle(adj: &[Vec<usize>], n: usize) -> bool {
    topological_sort(adj, n).is_none()
}

/// DFS-based topological sort (returns reverse postorder)
pub fn topological_sort_dfs(adj: &[Vec<usize>], n: usize) -> Option<Vec<usize>> {
    let mut visited = vec![0u8; n]; // 0=unvisited, 1=in progress, 2=done
    let mut result = Vec::new();

    fn dfs(u: usize, adj: &[Vec<usize>], visited: &mut [u8], result: &mut Vec<usize>) -> bool {
        if visited[u] == 1 {
            return false;
        } // cycle
        if visited[u] == 2 {
            return true;
        }
        visited[u] = 1;
        for &v in &adj[u] {
            if !dfs(v, adj, visited, result) {
                return false;
            }
        }
        visited[u] = 2;
        result.push(u);
        true
    }

    for u in 0..n {
        if visited[u] == 0 && !dfs(u, adj, &mut visited, &mut result) {
            return None;
        }
    }
    result.reverse();
    Some(result)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_topo_sort_kahn() {
        let mut adj = vec![vec![]; 4];
        adj[0].push(1);
        adj[0].push(2);
        adj[1].push(3);
        adj[2].push(3);
        let order = topological_sort(&adj, 4).unwrap();
        assert_eq!(order[0], 0);
        assert_eq!(*order.last().unwrap(), 3);
    }

    #[test]
    fn test_cycle_detection() {
        let mut adj = vec![vec![]; 3];
        adj[0].push(1);
        adj[1].push(2);
        adj[2].push(0);
        assert!(has_cycle(&adj, 3));
    }

    #[test]
    fn test_no_cycle() {
        let mut adj = vec![vec![]; 3];
        adj[0].push(1);
        adj[1].push(2);
        assert!(!has_cycle(&adj, 3));
    }

    #[test]
    fn test_dfs_sort() {
        let mut adj = vec![vec![]; 4];
        adj[0].push(1);
        adj[0].push(2);
        adj[1].push(3);
        adj[2].push(3);
        let order = topological_sort_dfs(&adj, 4).unwrap();
        assert_eq!(order[0], 0);
    }

    #[test]
    fn test_empty_graph() {
        let adj: Vec<Vec<usize>> = vec![vec![]; 3];
        let order = topological_sort(&adj, 3).unwrap();
        assert_eq!(order.len(), 3);
    }
}

(* DAG and Topological Sort in OCaml using Kahn's algorithm *)

let topological_sort adj n =
  let in_degree = Array.make n 0 in
  Array.iter (fun neighbors ->
    List.iter (fun v -> in_degree.(v) <- in_degree.(v) + 1) neighbors
  ) adj;
  let queue = Queue.create () in
  Array.iteri (fun v d -> if d = 0 then Queue.add v queue) in_degree;
  let result = ref [] in
  while not (Queue.is_empty queue) do
    let u = Queue.pop queue in
    result := u :: !result;
    List.iter (fun v ->
      in_degree.(v) <- in_degree.(v) - 1;
      if in_degree.(v) = 0 then Queue.add v queue
    ) adj.(u)
  done;
  if List.length !result = n then Some (List.rev !result)
  else None  (* cycle detected *)

let () =
  (* Build graph: 5 -> 2 -> 0 -> 1, 5 -> 0, 4 -> 0, 4 -> 1, 2 -> 3, 3 -> 1 *)
  let n = 6 in
  let adj = Array.make n [] in
  let edges = [(5,2);(5,0);(4,0);(4,1);(2,0);(2,3);(3,1)] in
  List.iter (fun (u,v) -> adj.(u) <- v :: adj.(u)) edges;
  match topological_sort adj n with
  | Some order ->
    Printf.printf "Topological order: ";
    List.iter (fun v -> Printf.printf "%d " v) order;
    print_newline ()
  | None ->
    Printf.printf "Graph has a cycle!\n"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_topo_sort_kahn() {
        let mut adj = vec![vec![]; 4];
        adj[0].push(1);
        adj[0].push(2);
        adj[1].push(3);
        adj[2].push(3);
        let order = topological_sort(&adj, 4).unwrap();
        assert_eq!(order[0], 0);
        assert_eq!(*order.last().unwrap(), 3);
    }

    #[test]
    fn test_cycle_detection() {
        let mut adj = vec![vec![]; 3];
        adj[0].push(1);
        adj[1].push(2);
        adj[2].push(0);
        assert!(has_cycle(&adj, 3));
    }

    #[test]
    fn test_no_cycle() {
        let mut adj = vec![vec![]; 3];
        adj[0].push(1);
        adj[1].push(2);
        assert!(!has_cycle(&adj, 3));
    }

    #[test]
    fn test_dfs_sort() {
        let mut adj = vec![vec![]; 4];
        adj[0].push(1);
        adj[0].push(2);
        adj[1].push(3);
        adj[2].push(3);
        let order = topological_sort_dfs(&adj, 4).unwrap();
        assert_eq!(order[0], 0);
    }

    #[test]
    fn test_empty_graph() {
        let adj: Vec<Vec<usize>> = vec![vec![]; 3];
        let order = topological_sort(&adj, 3).unwrap();
        assert_eq!(order.len(), 3);
    }
}

Deep Comparison

OCaml vs Rust: DAG

Both can use DFS or BFS (Kahn's) for topological sort.

Exercises

Longest path in DAG: Implement a DP algorithm using topological order to find the longest path in a weighted DAG — the critical path in project scheduling.

All topological orderings: Generate all valid topological orderings of a small DAG (backtracking over zero-in-degree choices at each step).

Dependency resolver: Model a package manager: packages have version requirements and dependencies. Build a DAG and use topological sort to produce a valid install order, returning an error message identifying any circular dependencies.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust