Example 1080: Topological Sort via Kahn's Algorithm

Difficulty: ⭐⭐⭐ Category: Graphs OCaml Source: https://rosettacode.org/wiki/Topological_sort#OCaml

Problem Statement

Implement topological sorting of a directed acyclic graph using Kahn's algorithm (in-degree counting). Detect cycles and return `None` if the graph is not a DAG.

Learning Outcomes

Kahn's algorithm: iterative topological sort via in-degree tracking
`HashMap` and `VecDeque` as Rust equivalents of OCaml's `Map` module and lists
Cycle detection as a natural byproduct of Kahn's algorithm
DFS-based alternative with coloring for comparison

OCaml Approach

OCaml uses functorized `Map.Make(String)` for the in-degree map and adjacency structure. The algorithm is expressed recursively: process nodes with zero in-degree, update neighbors, recurse. Lists are used as queues (not ideal for performance but idiomatic OCaml).

Rust Approach

Rust uses `HashMap` for O(1) lookups and `VecDeque` for efficient queue operations. The iterative `while let` loop replaces OCaml's recursive processing. A DFS-based variant with coloring is also provided, showing how both algorithms detect cycles.

Key Differences

1. Map types: OCaml uses `Map.Make(String)` (balanced tree, O(log n)); Rust uses `HashMap` (hash table, O(1) amortized) 2. Queue implementation: OCaml uses lists (O(n) dequeue); Rust uses `VecDeque` (O(1) amortized) 3. Iteration: OCaml recurses with pattern matching; Rust uses `while let` loops with mutable state 4. Cycle detection: Both return incomplete results when cycles exist; Rust wraps in `Option<Vec>` for explicit error handling

use std::collections::{HashMap, VecDeque};

fn kahn_sort(nodes: &[&str], edges: &[(&str, &str)]) -> Option<Vec<String>> {
    let mut in_degree: HashMap<&str, usize> = nodes.iter().map(|&n| (n, 0)).collect();
    let mut adj: HashMap<&str, Vec<&str>> = nodes.iter().map(|&n| (n, Vec::new())).collect();

    for &(from, to) in edges {
        *in_degree.entry(to).or_insert(0) += 1;
        adj.entry(from).or_default().push(to);
    }

    let mut queue: VecDeque<&str> = {
        let mut zeros: Vec<&str> = in_degree.iter()
            .filter(|(_, &d)| d == 0).map(|(&n, _)| n).collect();
        zeros.sort();
        zeros.into_iter().collect()
    };

    let mut result = Vec::new();

    while let Some(node) = queue.pop_front() {
        result.push(node.to_string());
        if let Some(neighbors) = adj.get(node) {
            let mut next = Vec::new();
            for &nb in neighbors {
                if let Some(deg) = in_degree.get_mut(nb) {
                    *deg -= 1;
                    if *deg == 0 { next.push(nb); }
                }
            }
            next.sort();
            queue.extend(next);
        }
    }

    if result.len() == nodes.len() { Some(result) } else { None }
}

fn main() {
    let nodes = vec!["a", "b", "c", "d", "e"];
    let edges = vec![("a","b"), ("a","c"), ("b","d"), ("c","d"), ("d","e")];
    match kahn_sort(&nodes, &edges) {
        Some(order) => println!("{}", order.join(" ")),
        None => println!("Cycle detected!"),
    }
}

/* Output:
   a b c d e
*/

(* Topological Sort via Kahn's Algorithm *)

module SMap = Map.Make(String)

let kahn_sort nodes edges =
  let in_deg = List.fold_left (fun m (_, b) ->
    SMap.update b (function None -> Some 1 | Some n -> Some (n+1)) m
  ) (List.fold_left (fun m n -> SMap.add n 0 m) SMap.empty nodes) edges in
  let queue = SMap.fold (fun k v acc -> if v = 0 then k :: acc else acc) in_deg [] in
  let rec go queue in_deg result =
    match queue with
    | [] -> List.rev result
    | node :: rest ->
      let out_edges = List.filter (fun (a, _) -> a = node) edges in
      let in_deg, new_queue = List.fold_left (fun (deg, q) (_, b) ->
        let d = SMap.find b deg - 1 in
        let deg = SMap.add b d deg in
        if d = 0 then (deg, b :: q) else (deg, q)
      ) (in_deg, rest) out_edges in
      go new_queue in_deg (node :: result)
  in go queue in_deg []

let () =
  let nodes = ["a";"b";"c";"d";"e"] in
  let edges = [("a","b");("a","c");("b","d");("c","d");("d","e")] in
  let result = kahn_sort nodes edges in
  assert (List.hd result = "a");
  assert (List.nth result (List.length result - 1) = "e");
  List.iter (Printf.printf "%s ") result;
  print_newline ();
  print_endline "ok"

📊 Detailed Comparison

OCaml vs Rust: Topological Sort via Kahn's Algorithm

Side-by-Side Code

OCaml

🐪 Show OCaml equivalent

module SMap = Map.Make(String)

let kahn_sort nodes edges =
let in_deg = List.fold_left (fun m (_, b) ->
 SMap.update b (function None -> Some 1 | Some n -> Some (n+1)) m
) (List.fold_left (fun m n -> SMap.add n 0 m) SMap.empty nodes) edges in
let queue = SMap.fold (fun k v acc -> if v = 0 then k :: acc else acc) in_deg [] in
let rec go queue in_deg result =
 match queue with
 | [] -> List.rev result
 | node :: rest ->
   let out_edges = List.filter (fun (a, _) -> a = node) edges in
   let in_deg, new_queue = List.fold_left (fun (deg, q) (_, b) ->
     let d = SMap.find b deg - 1 in
     let deg = SMap.add b d deg in
     if d = 0 then (deg, b :: q) else (deg, q)
   ) (in_deg, rest) out_edges in
   go new_queue in_deg (node :: result)
in go queue in_deg []

Rust (idiomatic)

pub fn kahn_sort(nodes: &[&str], edges: &[(&str, &str)]) -> Option<Vec<String>> {
 let mut in_degree: HashMap<&str, usize> = nodes.iter().map(|&n| (n, 0)).collect();
 let mut adj: HashMap<&str, Vec<&str>> = nodes.iter().map(|&n| (n, Vec::new())).collect();

 for &(from, to) in edges {
     *in_degree.entry(to).or_insert(0) += 1;
     adj.entry(from).or_default().push(to);
 }

 let mut queue: VecDeque<&str> = in_degree.iter()
     .filter(|(_, &d)| d == 0).map(|(&n, _)| n).collect();
 let mut result = Vec::new();

 while let Some(node) = queue.pop_front() {
     result.push(node.to_string());
     // ... decrement neighbors, enqueue zeros
 }

 if result.len() == nodes.len() { Some(result) } else { None }
}

Rust (DFS-based alternative)

fn dfs_visit(node: &str, adj: &HashMap<&str, Vec<&str>>,
          color: &mut HashMap<&str, Color>, result: &mut Vec<String>) -> bool {
 color.insert(node, Color::Gray);
 for &neighbor in adj.get(node).unwrap_or(&vec![]) {
     match color.get(neighbor) {
         Some(Color::Gray) => return false, // cycle!
         Some(Color::White) => if !dfs_visit(neighbor, adj, color, result) { return false; }
         _ => {}
     }
 }
 color.insert(node, Color::Black);
 result.push(node.to_string());
 true
}

Type Signatures

Concept	OCaml	Rust
Map type	`SMap.t` (balanced BST)	`HashMap<&str, usize>` (hash table)
Return type	`string list` (always returns)	`Option<Vec<String>>` (None = cycle)
Edge type	`(string * string) list`	`&[(&str, &str)]`
Queue	`string list`	`VecDeque<&str>`

Key Insights

1. OCaml's `Map.Make` functor vs Rust's `HashMap` — OCaml uses a balanced tree (ordered, O(log n)), Rust uses a hash table (unordered, O(1)). For topological sort, order doesn't matter, so HashMap is faster. 2. Immutable vs mutable state — OCaml's `go` function threads `in_deg` immutably through recursion. Rust mutates `in_degree` in place. Both are correct; OCaml's is more functional, Rust's is more efficient. 3. Cycle detection is elegant in both — Kahn's detects cycles when `result.len() < nodes.len()`. DFS detects via "gray" (in-progress) nodes. Both O(V+E). 4. OCaml's `List.fold_left` vs Rust's `for` loops — OCaml builds the in-degree map with a fold. Rust uses an imperative loop with `entry()` API. The Rust functional variant shows both styles work. 5. `Option<Vec<String>>` is more honest than `string list` — OCaml's version silently returns a partial list on cycles. Rust's `Option` forces the caller to handle the error case.

When to Use Each Style

Use Kahn's algorithm when: You need a BFS-based ordering, want to detect cycles naturally, or need to process nodes level by level (e.g., build systems, task scheduling). Use DFS-based sort when: You're already doing graph traversal, want to detect back edges explicitly, or need post-order for other algorithms (e.g., SCC detection).