805 Fundamental

805-kosaraju-scc — Kosaraju's Strongly Connected Components

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "805-kosaraju-scc — Kosaraju's Strongly Connected Components" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. Kosaraju's algorithm (1978, independently by Sharir 1981) finds SCCs using two DFS passes: first on the original graph to compute finish-time order, then on the reversed graph in reverse finish order. Key difference from OCaml: 1. **Code simplicity**: Kosaraju's two

Tutorial

The Problem

Kosaraju's algorithm (1978, independently by Sharir 1981) finds SCCs using two DFS passes: first on the original graph to compute finish-time order, then on the reversed graph in reverse finish order. Each DFS tree in the second pass is exactly one SCC. While Tarjan's uses one pass, Kosaraju's is conceptually simpler and easier to implement correctly. Both run in O(V+E) time.

🎯 Learning Outcomes

• Understand the two-pass approach: finish order DFS + reversed graph DFS

• Build the reversed graph radj by swapping edge directions

• Use a finish_order: Vec<usize> stack populated during the first DFS

• Each dfs2 call on an unvisited vertex in reverse finish order yields exactly one SCC

• Compare with Tarjan's: same asymptotic complexity, different implementation approach

Code Example

#![allow(clippy::all)]
//! # Kosaraju's SCC Algorithm
pub fn kosaraju(n: usize, edges: &[(usize, usize)]) -> Vec<Vec<usize>> {
    let mut adj = vec![vec![]; n];
    let mut radj = vec![vec![]; n];
    for &(u, v) in edges {
        adj[u].push(v);
        radj[v].push(u);
    }
    let mut visited = vec![false; n];
    let mut order = vec![];
    fn dfs1(v: usize, adj: &[Vec<usize>], vis: &mut [bool], ord: &mut Vec<usize>) {
        vis[v] = true;
        for &u in &adj[v] {
            if !vis[u] {
                dfs1(u, adj, vis, ord);
            }
        }
        ord.push(v);
    }
    fn dfs2(v: usize, radj: &[Vec<usize>], vis: &mut [bool], comp: &mut Vec<usize>) {
        vis[v] = true;
        comp.push(v);
        for &u in &radj[v] {
            if !vis[u] {
                dfs2(u, radj, vis, comp);
            }
        }
    }
    for v in 0..n {
        if !visited[v] {
            dfs1(v, &adj, &mut visited, &mut order);
        }
    }
    visited.fill(false);
    let mut sccs = vec![];
    for &v in order.iter().rev() {
        if !visited[v] {
            let mut comp = vec![];
            dfs2(v, &radj, &mut visited, &mut comp);
            sccs.push(comp);
        }
    }
    sccs
}
#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_kosaraju() {
        let sccs = kosaraju(5, &[(0, 1), (1, 2), (2, 0), (1, 3), (3, 4)]);
        assert!(!sccs.is_empty());
    }
}

(* Kosaraju's SCC — two-pass DFS, O(V+E) *)

let kosaraju adj n =
  let visited = Array.make n false in
  let finish  = ref [] in  (* finish-time stack *)

  (* Pass 1: DFS on original graph, record finish order *)
  let rec dfs1 u =
    if not visited.(u) then begin
      visited.(u) <- true;
      List.iter dfs1 adj.(u);
      finish := u :: !finish
    end
  in
  for v = 0 to n - 1 do dfs1 v done;

  (* Build transposed graph *)
  let radj = Array.make n [] in
  for u = 0 to n - 1 do
    List.iter (fun v -> radj.(v) <- u :: radj.(v)) adj.(u)
  done;

  (* Pass 2: DFS on transposed graph in reverse finish order *)
  let visited2 = Array.make n false in
  let sccs     = ref [] in

  let rec dfs2 u scc =
    if not visited2.(u) then begin
      visited2.(u) <- true;
      let scc' = u :: scc in
      List.fold_left (fun acc v -> dfs2 v acc) scc' radj.(u)
    end else scc
  in
  List.iter (fun u ->
    if not visited2.(u) then
      sccs := List.sort compare (dfs2 u []) :: !sccs
  ) !finish;
  !sccs

let () =
  let n   = 8 in
  let adj = Array.make n [] in
  let add u v = adj.(u) <- v :: adj.(u) in
  add 0 1; add 1 2; add 2 0; add 2 3;
  add 3 4; add 4 5; add 5 3;
  add 6 5; add 6 7; add 7 6;
  let sccs = kosaraju adj n in
  Printf.printf "SCCs (%d total):\n" (List.length sccs);
  List.iteri (fun i scc ->
    Printf.printf "  SCC %d: [%s]\n" (i+1)
      (String.concat "," (List.map string_of_int scc))
  ) sccs

Key Differences

Code simplicity: Kosaraju's two-pass DFS is more straightforward to reason about than Tarjan's single-pass with low-link values.

Memory: Kosaraju's requires storing the reversed graph; Tarjan's uses only the original graph with additional O(V) arrays.

Cache behavior: Kosaraju's second DFS on the reversed graph has worse cache behavior than Tarjan's single pass; in practice the difference is small.

Correctness proof: Kosaraju's correctness is easier to prove: finish order captures the "reachability hierarchy" of SCCs.

OCaml Approach

OCaml's two-function pattern mirrors the two-pass algorithm naturally. let rec dfs1 v = ... order := v :: !order and let rec dfs2 v = comp := v :: !comp. The reversed graph uses Hashtbl for edge storage. OCaml's List.iter (fun v -> if not vis.(v) then ...) (List.rev !order) drives the second pass. The Ocamlgraph library offers Kosaraju's as an alternative to Tarjan's.

Full Source

#![allow(clippy::all)]
//! # Kosaraju's SCC Algorithm
pub fn kosaraju(n: usize, edges: &[(usize, usize)]) -> Vec<Vec<usize>> {
    let mut adj = vec![vec![]; n];
    let mut radj = vec![vec![]; n];
    for &(u, v) in edges {
        adj[u].push(v);
        radj[v].push(u);
    }
    let mut visited = vec![false; n];
    let mut order = vec![];
    fn dfs1(v: usize, adj: &[Vec<usize>], vis: &mut [bool], ord: &mut Vec<usize>) {
        vis[v] = true;
        for &u in &adj[v] {
            if !vis[u] {
                dfs1(u, adj, vis, ord);
            }
        }
        ord.push(v);
    }
    fn dfs2(v: usize, radj: &[Vec<usize>], vis: &mut [bool], comp: &mut Vec<usize>) {
        vis[v] = true;
        comp.push(v);
        for &u in &radj[v] {
            if !vis[u] {
                dfs2(u, radj, vis, comp);
            }
        }
    }
    for v in 0..n {
        if !visited[v] {
            dfs1(v, &adj, &mut visited, &mut order);
        }
    }
    visited.fill(false);
    let mut sccs = vec![];
    for &v in order.iter().rev() {
        if !visited[v] {
            let mut comp = vec![];
            dfs2(v, &radj, &mut visited, &mut comp);
            sccs.push(comp);
        }
    }
    sccs
}
#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_kosaraju() {
        let sccs = kosaraju(5, &[(0, 1), (1, 2), (2, 0), (1, 3), (3, 4)]);
        assert!(!sccs.is_empty());
    }
}

(* Kosaraju's SCC — two-pass DFS, O(V+E) *)

let kosaraju adj n =
  let visited = Array.make n false in
  let finish  = ref [] in  (* finish-time stack *)

  (* Pass 1: DFS on original graph, record finish order *)
  let rec dfs1 u =
    if not visited.(u) then begin
      visited.(u) <- true;
      List.iter dfs1 adj.(u);
      finish := u :: !finish
    end
  in
  for v = 0 to n - 1 do dfs1 v done;

  (* Build transposed graph *)
  let radj = Array.make n [] in
  for u = 0 to n - 1 do
    List.iter (fun v -> radj.(v) <- u :: radj.(v)) adj.(u)
  done;

  (* Pass 2: DFS on transposed graph in reverse finish order *)
  let visited2 = Array.make n false in
  let sccs     = ref [] in

  let rec dfs2 u scc =
    if not visited2.(u) then begin
      visited2.(u) <- true;
      let scc' = u :: scc in
      List.fold_left (fun acc v -> dfs2 v acc) scc' radj.(u)
    end else scc
  in
  List.iter (fun u ->
    if not visited2.(u) then
      sccs := List.sort compare (dfs2 u []) :: !sccs
  ) !finish;
  !sccs

let () =
  let n   = 8 in
  let adj = Array.make n [] in
  let add u v = adj.(u) <- v :: adj.(u) in
  add 0 1; add 1 2; add 2 0; add 2 3;
  add 3 4; add 4 5; add 5 3;
  add 6 5; add 6 7; add 7 6;
  let sccs = kosaraju adj n in
  Printf.printf "SCCs (%d total):\n" (List.length sccs);
  List.iteri (fun i scc ->
    Printf.printf "  SCC %d: [%s]\n" (i+1)
      (String.concat "," (List.map string_of_int scc))
  ) sccs

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_kosaraju() {
        let sccs = kosaraju(5, &[(0, 1), (1, 2), (2, 0), (1, 3), (3, 4)]);
        assert!(!sccs.is_empty());
    }
}

Deep Comparison

OCaml vs Rust: Kosaraju Scc

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 an iterative version of both DFS passes to avoid stack overflow on graphs with millions of vertices.

Time Kosaraju's vs Tarjan's on a graph with 100,000 nodes and 500,000 edges — do they produce the same SCCs (verify by comparing sorted SCC sets)?

Use Kosaraju's to identify "sink SCCs" in a dependency graph: SCCs with no outgoing edges to other SCCs are safe to process first in a topological order.

Open Source Repos

functional-rust

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

Rust