078: Topological Sort — DAG Ordering

Difficulty: Advanced Category: Graphs Concept: DFS-based topological ordering of directed acyclic graphs Key Insight: OCaml threads immutable state (visited, order) through recursion; Rust uses mutable references with explicit lifetime annotations.

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

/// Topological sort using DFS
///
/// Ownership insight: edges are borrowed as slices of string slices.
/// The visited set and result vector are owned locally.
pub fn topo_sort(edges: &[(&str, &str)]) -> Vec<String> {
    let mut all_nodes = HashSet::new();
    let mut adj: HashMap<&str, Vec<&str>> = HashMap::new();
    for &(a, b) in edges {
        all_nodes.insert(a);
        all_nodes.insert(b);
        adj.entry(a).or_default().push(b);
    }

    let mut visited = HashSet::new();
    let mut order = Vec::new();

    fn visit<'a>(
        node: &'a str,
        adj: &HashMap<&str, Vec<&'a str>>,
        visited: &mut HashSet<&'a str>,
        order: &mut Vec<String>,
    ) {
        if visited.contains(node) {
            return;
        }
        visited.insert(node);
        if let Some(neighbors) = adj.get(node) {
            for &n in neighbors {
                visit(n, adj, visited, order);
            }
        }
        order.push(node.to_string());
    }

    for &node in &all_nodes {
        visit(node, &adj, &mut visited, &mut order);
    }
    order
}

/// Version using owned Strings
pub fn topo_sort_owned(edges: Vec<(String, String)>) -> Vec<String> {
    let str_edges: Vec<(&str, &str)> = edges.iter().map(|(a, b)| (a.as_str(), b.as_str())).collect();
    topo_sort(&str_edges)
}

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

    #[test]
    fn test_linear_chain() {
        let edges = vec![("a", "b"), ("b", "c"), ("c", "d")];
        let result = topo_sort(&edges);
        // d should come before c, c before b, b before a
        let pos = |s: &str| result.iter().position(|x| x == s).unwrap();
        assert!(pos("d") < pos("c"));
        assert!(pos("c") < pos("b"));
    }

    #[test]
    fn test_diamond() {
        let edges = vec![("a", "b"), ("a", "c"), ("b", "d"), ("c", "d")];
        let result = topo_sort(&edges);
        let pos = |s: &str| result.iter().position(|x| x == s).unwrap();
        assert!(pos("d") < pos("b"));
        assert!(pos("d") < pos("c"));
    }

    #[test]
    fn test_empty() {
        let result = topo_sort(&[]);
        assert!(result.is_empty());
    }

    #[test]
    fn test_single_edge() {
        let result = topo_sort(&[("x", "y")]);
        assert_eq!(result.len(), 2);
    }

    #[test]
    fn test_owned_version() {
        let edges = vec![("a".into(), "b".into()), ("b".into(), "c".into())];
        let result = topo_sort_owned(edges);
        assert_eq!(result.len(), 3);
    }
}

fn main() {
    println!("{:?}", pos("d") < pos("c"));
    println!("{:?}", pos("c") < pos("b"));
    println!("{:?}", pos("d") < pos("b"));
}

(* Topological Sort — DAG Ordering *)
module SS = Set.Make(String)

(* Version 1: DFS-based topological sort *)
let topo_sort edges =
  let neighbors node =
    List.filter_map (fun (a, b) -> if a = node then Some b else None) edges in
  let all_nodes = List.fold_left (fun s (a, b) -> SS.add a (SS.add b s)) SS.empty edges in
  let rec visit node (visited, order) =
    if SS.mem node visited then (visited, order)
    else
      let visited = SS.add node visited in
      let visited, order = List.fold_left (fun acc n ->
        visit n acc) (visited, order) (neighbors node) in
      (visited, node :: order)
  in
  let _, order = SS.fold (fun node acc -> visit node acc) all_nodes (SS.empty, []) in
  order

let () =
  let edges = [("a","b");("a","c");("b","d");("c","d");("d","e")] in
  let result = topo_sort edges in
  assert (List.mem "e" result);
  List.iter (Printf.printf "%s ") result

📊 Detailed Comparison

Topological Sort — Comparison

Core Insight

Topological sort highlights how OCaml and Rust handle mutable state differently. OCaml passes immutable tuples `(visited, order)` through recursive calls. Rust uses `&mut` references, requiring lifetime annotations when the recursive helper borrows string slices.

OCaml Approach

`Set.Make(String)` for visited nodes — persistent/immutable set
State threaded as `(visited, order)` tuple through fold
`SS.fold` iterates all nodes; inner `visit` recurses on neighbors
No mutation — each recursive call returns updated state

Rust Approach

`HashSet` and `HashMap` — mutable, efficient hash-based collections
`&mut visited` and `&mut order` passed to recursive helper
Lifetime `'a` needed on `visit` to link borrowed `&str` to input edges
`to_string()` at collection point to own the results

Comparison Table

Aspect	OCaml	Rust
Set type	`Set.Make(String)`	`HashSet<&str>`
State passing	Immutable tuple	`&mut` references
Lifetimes	Implicit (GC)	Explicit `'a` annotations
String handling	`string` (GC)	`&str` borrowed, `String` owned
Adjacency	`List.filter_map`	`HashMap<&str, Vec<&str>>`

Learner Notes

Rust lifetime annotations on recursive functions can be tricky
`HashMap::entry().or_default()` is idiomatic for building adjacency lists
OCaml threading immutable state is elegant but can be harder to optimize
Rust mutable approach is more imperative but avoids allocation per recursive call