808 Advanced

808-topological-sort-dfs — Topological Sort (DFS)

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "808-topological-sort-dfs — Topological Sort (DFS)" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. Topological sort orders the vertices of a Directed Acyclic Graph (DAG) so that every edge goes from earlier to later in the order. Key difference from OCaml: 1. **Three

Tutorial

The Problem

Topological sort orders the vertices of a Directed Acyclic Graph (DAG) so that every edge goes from earlier to later in the order. It is fundamental to build systems (Makefile, Cargo, Bazel — dependency ordering), task schedulers, course prerequisite ordering, and package managers. The DFS-based algorithm by Tarjan (1976) runs in O(V+E) and also detects cycles (where topological sort is undefined).

🎯 Learning Outcomes

• Implement DFS-based topological sort using a three-color marking (0=unvisited, 1=in-progress, 2=done)

• Detect cycles: a back edge to an in-progress vertex (color=1) indicates a cycle

• Return None for cyclic graphs and Some(Vec<usize>) for DAGs

• Reverse the DFS finish order to get topological order

• Compare with Kahn's BFS algorithm (alternative approach using in-degree counts)

Code Example

#![allow(clippy::all)]
//! # Topological Sort (DFS)
pub fn topological_sort(n: usize, edges: &[(usize, usize)]) -> Option<Vec<usize>> {
    let mut adj = vec![vec![]; n];
    for &(u, v) in edges {
        adj[u].push(v);
    }
    let mut visited = vec![0u8; n];
    let mut result = vec![];
    fn dfs(v: usize, adj: &[Vec<usize>], vis: &mut [u8], res: &mut Vec<usize>) -> bool {
        vis[v] = 1;
        for &u in &adj[v] {
            if vis[u] == 1 {
                return false;
            }
            if vis[u] == 0 && !dfs(u, adj, vis, res) {
                return false;
            }
        }
        vis[v] = 2;
        res.push(v);
        true
    }
    for v in 0..n {
        if visited[v] == 0 && !dfs(v, &adj, &mut visited, &mut result) {
            return None;
        }
    }
    result.reverse();
    Some(result)
}
#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_topo() {
        let r = topological_sort(4, &[(0, 1), (0, 2), (1, 3), (2, 3)]);
        assert!(r.is_some());
    }
}

(* Topological Sort — DFS with cycle detection O(V+E) *)

let topo_sort adj n =
  let state  = Array.make n 0 in  (* 0=white,1=grey,2=black *)
  let result = ref [] in
  let has_cycle = ref false in

  let rec dfs u =
    state.(u) <- 1;
    List.iter (fun v ->
      if state.(v) = 1 then has_cycle := true
      else if state.(v) = 0 then dfs v
    ) adj.(u);
    state.(u) <- 2;
    result := u :: !result
  in
  for v = 0 to n - 1 do
    if state.(v) = 0 then dfs v
  done;
  if !has_cycle then None else Some !result

let () =
  (* DAG: build order dependencies *)
  let n   = 6 in
  let adj = Array.make n [] in
  let add u v = adj.(u) <- v :: adj.(u) in
  (* 5->2->0, 5->0, 4->0, 4->1, 2->3, 3->1 *)
  add 5 2; add 5 0; add 4 0; add 4 1; add 2 3; add 3 1;
  (match topo_sort adj n with
   | None   -> Printf.printf "Cycle detected!\n"
   | Some o -> Printf.printf "Topological order: [%s]\n"
       (String.concat " -> " (List.map string_of_int o)));

  (* Graph with cycle *)
  let adj2 = Array.make 3 [] in
  Array.set adj2 0 [1]; Array.set adj2 1 [2]; Array.set adj2 2 [0];
  (match topo_sort adj2 3 with
   | None   -> Printf.printf "Cycle detected (correct)!\n"
   | Some o -> Printf.printf "Order: [%s]\n"
       (String.concat "->" (List.map string_of_int o)))

Key Differences

Three-color DFS: Both languages use 0/1/2 coloring to detect cycles; Rust's u8 array and OCaml's int array are equivalent.

Cycle detection: Rust returns false / None; OCaml can raise an exception (exception Cycle) for a more functional early-exit.

Kahn's alternative: Kahn's algorithm (BFS + in-degree) is simpler to reason about; DFS-based is more common in compiler implementations.

Build systems: Cargo uses topological sort for compilation order; Bazel and Gradle use variants for distributed build graphs.

OCaml Approach

OCaml implements with color: int array and let rec dfs v = .... The exception Cycle can short-circuit the entire DFS cleanly. OCaml's List.rev reverses the finish order. Ocamlgraph.Topological.fold provides a functional topological traversal. Kahn's algorithm (in-degree + queue) is simpler to implement in OCaml due to its BFS nature.

Full Source

#![allow(clippy::all)]
//! # Topological Sort (DFS)
pub fn topological_sort(n: usize, edges: &[(usize, usize)]) -> Option<Vec<usize>> {
    let mut adj = vec![vec![]; n];
    for &(u, v) in edges {
        adj[u].push(v);
    }
    let mut visited = vec![0u8; n];
    let mut result = vec![];
    fn dfs(v: usize, adj: &[Vec<usize>], vis: &mut [u8], res: &mut Vec<usize>) -> bool {
        vis[v] = 1;
        for &u in &adj[v] {
            if vis[u] == 1 {
                return false;
            }
            if vis[u] == 0 && !dfs(u, adj, vis, res) {
                return false;
            }
        }
        vis[v] = 2;
        res.push(v);
        true
    }
    for v in 0..n {
        if visited[v] == 0 && !dfs(v, &adj, &mut visited, &mut result) {
            return None;
        }
    }
    result.reverse();
    Some(result)
}
#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_topo() {
        let r = topological_sort(4, &[(0, 1), (0, 2), (1, 3), (2, 3)]);
        assert!(r.is_some());
    }
}

(* Topological Sort — DFS with cycle detection O(V+E) *)

let topo_sort adj n =
  let state  = Array.make n 0 in  (* 0=white,1=grey,2=black *)
  let result = ref [] in
  let has_cycle = ref false in

  let rec dfs u =
    state.(u) <- 1;
    List.iter (fun v ->
      if state.(v) = 1 then has_cycle := true
      else if state.(v) = 0 then dfs v
    ) adj.(u);
    state.(u) <- 2;
    result := u :: !result
  in
  for v = 0 to n - 1 do
    if state.(v) = 0 then dfs v
  done;
  if !has_cycle then None else Some !result

let () =
  (* DAG: build order dependencies *)
  let n   = 6 in
  let adj = Array.make n [] in
  let add u v = adj.(u) <- v :: adj.(u) in
  (* 5->2->0, 5->0, 4->0, 4->1, 2->3, 3->1 *)
  add 5 2; add 5 0; add 4 0; add 4 1; add 2 3; add 3 1;
  (match topo_sort adj n with
   | None   -> Printf.printf "Cycle detected!\n"
   | Some o -> Printf.printf "Topological order: [%s]\n"
       (String.concat " -> " (List.map string_of_int o)));

  (* Graph with cycle *)
  let adj2 = Array.make 3 [] in
  Array.set adj2 0 [1]; Array.set adj2 1 [2]; Array.set adj2 2 [0];
  (match topo_sort adj2 3 with
   | None   -> Printf.printf "Cycle detected (correct)!\n"
   | Some o -> Printf.printf "Order: [%s]\n"
       (String.concat "->" (List.map string_of_int o)))

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_topo() {
        let r = topological_sort(4, &[(0, 1), (0, 2), (1, 3), (2, 3)]);
        assert!(r.is_some());
    }
}

Deep Comparison

OCaml vs Rust: Topological Sort Dfs

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement Kahn's BFS-based topological sort as an alternative and verify it produces a valid ordering (not necessarily the same one as DFS).

Find all valid topological orderings of a small DAG and count them — this is #P-hard in general but feasible for small graphs.

Implement a parallel topological execution scheduler: process all vertices with in-degree 0 in parallel, then decrement in-degrees and add newly freed vertices.

Open Source Repos

functional-rust

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

Rust