812 Intermediate

812-graph-coloring — Graph Coloring

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "812-graph-coloring — Graph Coloring" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Graph coloring assigns colors to vertices so no two adjacent vertices share a color, using at most k colors. Key difference from OCaml: 1. **Backtracking structure**: Identical in both languages — assign, recurse, undo. The algorithm is language

Tutorial

The Problem

Graph coloring assigns colors to vertices so no two adjacent vertices share a color, using at most k colors. The four-color theorem (every planar map is 4-colorable) is famous; the general k-coloring decision problem is NP-complete for k ≥ 3. Applications: register allocation in compilers (variables with conflicting lifetimes need different registers), exam scheduling (conflicting exams need different time slots), frequency assignment in cellular networks.

🎯 Learning Outcomes

• Implement backtracking k-coloring: assign colors 1..=k to vertices, backtrack when stuck

• Apply the safety check: is_safe(v, c) — no adjacent vertex has color c

• Understand why 2-coloring = bipartite check (polynomial) but 3-coloring is NP-complete

• Know the greedy coloring algorithm (not optimal but fast) and its chromatic number approximation

• See the connection to register allocation in LLVM's coloring algorithm

Code Example

#![allow(clippy::all)]
//! # Graph Coloring
pub fn graph_coloring(n: usize, edges: &[(usize, usize)], m: usize) -> Option<Vec<usize>> {
    let mut adj = vec![vec![]; n];
    for &(u, v) in edges {
        adj[u].push(v);
        adj[v].push(u);
    }
    let mut colors = vec![0; n];
    fn is_safe(v: usize, c: usize, adj: &[Vec<usize>], colors: &[usize]) -> bool {
        adj[v].iter().all(|&u| colors[u] != c)
    }
    fn solve(v: usize, n: usize, m: usize, adj: &[Vec<usize>], colors: &mut [usize]) -> bool {
        if v == n {
            return true;
        }
        for c in 1..=m {
            if is_safe(v, c, adj, colors) {
                colors[v] = c;
                if solve(v + 1, n, m, adj, colors) {
                    return true;
                }
                colors[v] = 0;
            }
        }
        false
    }
    if solve(0, n, m, &adj, &mut colors) {
        Some(colors)
    } else {
        None
    }
}
#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_color() {
        let c = graph_coloring(4, &[(0, 1), (1, 2), (2, 3), (3, 0), (0, 2)], 3);
        assert!(c.is_some());
    }
}

(* Graph m-Colouring — backtracking O(m^V) *)

let graph_color adj n m =
  let color = Array.make n (-1) in

  let is_safe v c =
    List.for_all (fun u -> color.(u) <> c) adj.(v)
  in

  let rec solve v =
    if v = n then true
    else
      let rec try_color c =
        if c >= m then false
        else if is_safe v c then begin
          color.(v) <- c;
          if solve (v + 1) then true
          else begin color.(v) <- -1; try_color (c + 1) end
        end
        else try_color (c + 1)
      in
      try_color 0
  in
  if solve 0 then Some (Array.copy color) else None

let chromatic_number adj n =
  let rec try_m m =
    if m > n then n
    else match graph_color adj n m with
      | Some _ -> m
      | None   -> try_m (m + 1)
  in
  try_m 1

let () =
  (* Petersen graph — chromatic number = 3 *)
  let n   = 10 in
  let adj = Array.make n [] in
  let add u v = adj.(u) <- v :: adj.(u); adj.(v) <- u :: adj.(v) in
  (* Outer 5-cycle *)
  add 0 1; add 1 2; add 2 3; add 3 4; add 4 0;
  (* Inner pentagram *)
  add 5 7; add 7 9; add 9 6; add 6 8; add 8 5;
  (* Spokes *)
  add 0 5; add 1 6; add 2 7; add 3 8; add 4 9;

  let chi = chromatic_number adj n in
  Printf.printf "Petersen graph chromatic number: %d  (expected 3)\n" chi;
  (match graph_color adj n 3 with
   | None   -> Printf.printf "No 3-colouring found\n"
   | Some c -> Printf.printf "3-colouring: [%s]\n"
       (String.concat "," (Array.to_list (Array.map string_of_int c))))

Key Differences

Backtracking structure: Identical in both languages — assign, recurse, undo. The algorithm is language-independent.

NP-completeness: 3-coloring is NP-complete; Rust and OCaml face the same exponential worst case; only small graphs are solvable exactly.

Register allocation: LLVM and GCC use graph coloring for register allocation (variables as vertices, conflicting lifetimes as edges); Rust's rustc uses a similar approach in its codegen.

Chromatic number: The minimum k for which a graph is k-colorable; computing it exactly is NP-hard; approximations use greedy algorithms.

OCaml Approach

OCaml implements with colors: int array initialized to 0 (uncolored). The is_safe function uses List.for_all (fun u -> colors.(u) <> c) adj.(v). The recursive backtracking is a natural OCaml pattern. The exception Found can terminate early. OCaml's Graph_coloring in academic libraries implements both exact and approximation algorithms.

Full Source

#![allow(clippy::all)]
//! # Graph Coloring
pub fn graph_coloring(n: usize, edges: &[(usize, usize)], m: usize) -> Option<Vec<usize>> {
    let mut adj = vec![vec![]; n];
    for &(u, v) in edges {
        adj[u].push(v);
        adj[v].push(u);
    }
    let mut colors = vec![0; n];
    fn is_safe(v: usize, c: usize, adj: &[Vec<usize>], colors: &[usize]) -> bool {
        adj[v].iter().all(|&u| colors[u] != c)
    }
    fn solve(v: usize, n: usize, m: usize, adj: &[Vec<usize>], colors: &mut [usize]) -> bool {
        if v == n {
            return true;
        }
        for c in 1..=m {
            if is_safe(v, c, adj, colors) {
                colors[v] = c;
                if solve(v + 1, n, m, adj, colors) {
                    return true;
                }
                colors[v] = 0;
            }
        }
        false
    }
    if solve(0, n, m, &adj, &mut colors) {
        Some(colors)
    } else {
        None
    }
}
#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_color() {
        let c = graph_coloring(4, &[(0, 1), (1, 2), (2, 3), (3, 0), (0, 2)], 3);
        assert!(c.is_some());
    }
}

(* Graph m-Colouring — backtracking O(m^V) *)

let graph_color adj n m =
  let color = Array.make n (-1) in

  let is_safe v c =
    List.for_all (fun u -> color.(u) <> c) adj.(v)
  in

  let rec solve v =
    if v = n then true
    else
      let rec try_color c =
        if c >= m then false
        else if is_safe v c then begin
          color.(v) <- c;
          if solve (v + 1) then true
          else begin color.(v) <- -1; try_color (c + 1) end
        end
        else try_color (c + 1)
      in
      try_color 0
  in
  if solve 0 then Some (Array.copy color) else None

let chromatic_number adj n =
  let rec try_m m =
    if m > n then n
    else match graph_color adj n m with
      | Some _ -> m
      | None   -> try_m (m + 1)
  in
  try_m 1

let () =
  (* Petersen graph — chromatic number = 3 *)
  let n   = 10 in
  let adj = Array.make n [] in
  let add u v = adj.(u) <- v :: adj.(u); adj.(v) <- u :: adj.(v) in
  (* Outer 5-cycle *)
  add 0 1; add 1 2; add 2 3; add 3 4; add 4 0;
  (* Inner pentagram *)
  add 5 7; add 7 9; add 9 6; add 6 8; add 8 5;
  (* Spokes *)
  add 0 5; add 1 6; add 2 7; add 3 8; add 4 9;

  let chi = chromatic_number adj n in
  Printf.printf "Petersen graph chromatic number: %d  (expected 3)\n" chi;
  (match graph_color adj n 3 with
   | None   -> Printf.printf "No 3-colouring found\n"
   | Some c -> Printf.printf "3-colouring: [%s]\n"
       (String.concat "," (Array.to_list (Array.map string_of_int c))))

✓ Tests Rust test suite

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

Deep Comparison

OCaml vs Rust: Graph Coloring

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 greedy coloring: assign the smallest available color to each vertex in a fixed order. Prove it uses at most Δ+1 colors where Δ is the maximum degree.

Implement Welsh-Powell ordering: sort vertices by degree (descending) before greedy coloring. Verify it often uses fewer colors than arbitrary ordering.

Apply graph coloring to exam scheduling: given a set of exams and students enrolled in each, build a conflict graph and find the minimum number of time slots needed.

Open Source Repos

functional-rust

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

Rust