1069 Intermediate

1069-graph-coloring — Graph Coloring

Functional Programming

Tutorial

The Problem

Graph coloring assigns colors to vertices such that no two adjacent vertices share a color, using at most k colors. It models register allocation in compilers (colors = registers, vertices = variables, edges = interference), exam scheduling (colors = time slots, vertices = exams, edges = shared students), and map coloring.

Graph coloring is NP-complete in general but tractable for small k or special graph families. The backtracking approach tries each color and backtracks when a conflict is found.

🎯 Learning Outcomes

• Implement graph coloring via backtracking with constraint checking

• Understand the is_safe predicate that checks all neighbors

• Find the minimum chromatic number by trying k = 1, 2, 3, ...

• Connect to compiler register allocation (chordal graph coloring)

• Understand the Four Color Theorem for planar graphs

Code Example

#![allow(clippy::all)]
// 1069: Graph Coloring — Backtracking

// Approach 1: Adjacency matrix
fn graph_coloring(adj: &[Vec<i32>], num_colors: usize) -> Option<Vec<usize>> {
    let n = adj.len();
    let mut colors = vec![0usize; n];

    fn is_safe(node: usize, color: usize, adj: &[Vec<i32>], colors: &[usize]) -> bool {
        for i in 0..adj.len() {
            if adj[node][i] == 1 && colors[i] == color {
                return false;
            }
        }
        true
    }

    fn solve(node: usize, adj: &[Vec<i32>], colors: &mut Vec<usize>, num_colors: usize) -> bool {
        if node == adj.len() {
            return true;
        }
        for c in 1..=num_colors {
            if is_safe(node, c, adj, colors) {
                colors[node] = c;
                if solve(node + 1, adj, colors, num_colors) {
                    return true;
                }
                colors[node] = 0;
            }
        }
        false
    }

    if solve(0, adj, &mut colors, num_colors) {
        Some(colors)
    } else {
        None
    }
}

// Approach 2: Adjacency list
fn graph_coloring_list(adj: &[Vec<usize>], num_colors: usize) -> Option<Vec<usize>> {
    let n = adj.len();
    let mut colors = vec![0usize; n];

    fn is_safe(node: usize, color: usize, adj: &[Vec<usize>], colors: &[usize]) -> bool {
        adj[node].iter().all(|&neighbor| colors[neighbor] != color)
    }

    fn solve(node: usize, adj: &[Vec<usize>], colors: &mut Vec<usize>, num_colors: usize) -> bool {
        if node == adj.len() {
            return true;
        }
        for c in 1..=num_colors {
            if is_safe(node, c, adj, colors) {
                colors[node] = c;
                if solve(node + 1, adj, colors, num_colors) {
                    return true;
                }
                colors[node] = 0;
            }
        }
        false
    }

    if solve(0, adj, &mut colors, num_colors) {
        Some(colors)
    } else {
        None
    }
}

// Approach 3: Greedy coloring (not optimal but fast)
fn greedy_coloring(adj: &[Vec<usize>]) -> Vec<usize> {
    let n = adj.len();
    let mut colors = vec![0usize; n];
    for node in 0..n {
        let used: std::collections::HashSet<usize> = adj[node]
            .iter()
            .filter(|&&nb| colors[nb] > 0)
            .map(|&nb| colors[nb])
            .collect();
        colors[node] = (1..).find(|c| !used.contains(c)).unwrap();
    }
    colors
}

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

    #[test]
    fn test_graph_coloring_possible() {
        let adj = vec![
            vec![0, 1, 1, 1],
            vec![1, 0, 1, 0],
            vec![1, 1, 0, 1],
            vec![1, 0, 1, 0],
        ];
        let colors = graph_coloring(&adj, 3).unwrap();
        assert_eq!(colors.len(), 4);
        // Verify no adjacent nodes share color
        for i in 0..4 {
            for j in 0..4 {
                if adj[i][j] == 1 {
                    assert_ne!(colors[i], colors[j]);
                }
            }
        }
    }

    #[test]
    fn test_graph_coloring_impossible() {
        let adj = vec![
            vec![0, 1, 1, 1],
            vec![1, 0, 1, 0],
            vec![1, 1, 0, 1],
            vec![1, 0, 1, 0],
        ];
        assert!(graph_coloring(&adj, 2).is_none());
    }

    #[test]
    fn test_graph_coloring_list() {
        let adj = vec![vec![1, 2, 3], vec![0, 2], vec![0, 1, 3], vec![0, 2]];
        let colors = graph_coloring_list(&adj, 3).unwrap();
        assert_eq!(colors.len(), 4);
    }

    #[test]
    fn test_greedy() {
        let adj = vec![vec![1, 2, 3], vec![0, 2], vec![0, 1, 3], vec![0, 2]];
        let colors = greedy_coloring(&adj);
        for (node, neighbors) in adj.iter().enumerate() {
            for &nb in neighbors {
                assert_ne!(colors[node], colors[nb]);
            }
        }
    }
}

(* 1069: Graph Coloring — Backtracking *)

(* Approach 1: Basic backtracking *)
let graph_coloring adj_matrix num_colors =
  let n = Array.length adj_matrix in
  let colors = Array.make n 0 in
  let is_safe node color =
    let safe = ref true in
    for i = 0 to n - 1 do
      if adj_matrix.(node).(i) = 1 && colors.(i) = color then
        safe := false
    done;
    !safe
  in
  let rec solve node =
    if node = n then true
    else begin
      let found = ref false in
      for c = 1 to num_colors do
        if not !found && is_safe node c then begin
          colors.(node) <- c;
          if solve (node + 1) then found := true
          else colors.(node) <- 0
        end
      done;
      !found
    end
  in
  if solve 0 then Some (Array.to_list colors) else None

(* Approach 2: With adjacency list *)
let graph_coloring_adj adj_list num_colors n =
  let colors = Array.make n 0 in
  let is_safe node color =
    List.for_all (fun neighbor ->
      colors.(neighbor) <> color
    ) adj_list.(node)
  in
  let rec solve node =
    if node = n then true
    else
      let found = ref false in
      for c = 1 to num_colors do
        if not !found && is_safe node c then begin
          colors.(node) <- c;
          if solve (node + 1) then found := true
          else colors.(node) <- 0
        end
      done;
      !found
  in
  if solve 0 then Some (Array.to_list colors) else None

let () =
  (* Petersen-like graph: 4 nodes, edges: 0-1, 1-2, 2-3, 3-0, 0-2 *)
  let adj = [|
    [|0;1;1;1|];
    [|1;0;1;0|];
    [|1;1;0;1|];
    [|1;0;1;0|]
  |] in
  (match graph_coloring adj 3 with
   | Some colors -> assert (List.length colors = 4)
   | None -> assert false);
  assert (graph_coloring adj 2 = None);

  let adj_list = [|[1;2;3]; [0;2]; [0;1;3]; [0;2]|] in
  (match graph_coloring_adj adj_list 3 4 with
   | Some colors -> assert (List.length colors = 4)
   | None -> assert false);

  Printf.printf "✓ All tests passed\n"

Key Differences

**is_safe complexity**: Rust's is_safe iterates all vertices and checks adj[node][i] == 1; OCaml's Array.for_all2 is equivalent.

Try loop: Rust uses a for c in 1..=num_colors loop; OCaml's tail-recursive try_colors is equivalent.

Return type: Both return Option<Vec<usize>> / option (int list) — None when coloring is impossible.

Bipartite check: 2-colorability can be checked in O(V+E) with BFS; for k > 2, no polynomial algorithm is known (NP-complete).

OCaml Approach

let graph_color adj k =
  let n = Array.length adj in
  let colors = Array.make n 0 in
  let is_safe node color =
    Array.for_all2 (fun neighbor c -> adj.(node).(neighbor) = 0 || c <> color) adj.(node) colors
  in
  let rec solve node =
    if node = n then true
    else
      let rec try_colors c =
        if c > k then false
        else if is_safe node c then begin
          colors.(node) <- c;
          if solve (node + 1) then true
          else begin colors.(node) <- 0; try_colors (c + 1) end
        end else try_colors (c + 1)
      in
      try_colors 1
  in
  if solve 0 then Some (Array.to_list colors) else None

Structurally identical. Both implement the same backtracking search.

Full Source

#![allow(clippy::all)]
// 1069: Graph Coloring — Backtracking

// Approach 1: Adjacency matrix
fn graph_coloring(adj: &[Vec<i32>], num_colors: usize) -> Option<Vec<usize>> {
    let n = adj.len();
    let mut colors = vec![0usize; n];

    fn is_safe(node: usize, color: usize, adj: &[Vec<i32>], colors: &[usize]) -> bool {
        for i in 0..adj.len() {
            if adj[node][i] == 1 && colors[i] == color {
                return false;
            }
        }
        true
    }

    fn solve(node: usize, adj: &[Vec<i32>], colors: &mut Vec<usize>, num_colors: usize) -> bool {
        if node == adj.len() {
            return true;
        }
        for c in 1..=num_colors {
            if is_safe(node, c, adj, colors) {
                colors[node] = c;
                if solve(node + 1, adj, colors, num_colors) {
                    return true;
                }
                colors[node] = 0;
            }
        }
        false
    }

    if solve(0, adj, &mut colors, num_colors) {
        Some(colors)
    } else {
        None
    }
}

// Approach 2: Adjacency list
fn graph_coloring_list(adj: &[Vec<usize>], num_colors: usize) -> Option<Vec<usize>> {
    let n = adj.len();
    let mut colors = vec![0usize; n];

    fn is_safe(node: usize, color: usize, adj: &[Vec<usize>], colors: &[usize]) -> bool {
        adj[node].iter().all(|&neighbor| colors[neighbor] != color)
    }

    fn solve(node: usize, adj: &[Vec<usize>], colors: &mut Vec<usize>, num_colors: usize) -> bool {
        if node == adj.len() {
            return true;
        }
        for c in 1..=num_colors {
            if is_safe(node, c, adj, colors) {
                colors[node] = c;
                if solve(node + 1, adj, colors, num_colors) {
                    return true;
                }
                colors[node] = 0;
            }
        }
        false
    }

    if solve(0, adj, &mut colors, num_colors) {
        Some(colors)
    } else {
        None
    }
}

// Approach 3: Greedy coloring (not optimal but fast)
fn greedy_coloring(adj: &[Vec<usize>]) -> Vec<usize> {
    let n = adj.len();
    let mut colors = vec![0usize; n];
    for node in 0..n {
        let used: std::collections::HashSet<usize> = adj[node]
            .iter()
            .filter(|&&nb| colors[nb] > 0)
            .map(|&nb| colors[nb])
            .collect();
        colors[node] = (1..).find(|c| !used.contains(c)).unwrap();
    }
    colors
}

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

    #[test]
    fn test_graph_coloring_possible() {
        let adj = vec![
            vec![0, 1, 1, 1],
            vec![1, 0, 1, 0],
            vec![1, 1, 0, 1],
            vec![1, 0, 1, 0],
        ];
        let colors = graph_coloring(&adj, 3).unwrap();
        assert_eq!(colors.len(), 4);
        // Verify no adjacent nodes share color
        for i in 0..4 {
            for j in 0..4 {
                if adj[i][j] == 1 {
                    assert_ne!(colors[i], colors[j]);
                }
            }
        }
    }

    #[test]
    fn test_graph_coloring_impossible() {
        let adj = vec![
            vec![0, 1, 1, 1],
            vec![1, 0, 1, 0],
            vec![1, 1, 0, 1],
            vec![1, 0, 1, 0],
        ];
        assert!(graph_coloring(&adj, 2).is_none());
    }

    #[test]
    fn test_graph_coloring_list() {
        let adj = vec![vec![1, 2, 3], vec![0, 2], vec![0, 1, 3], vec![0, 2]];
        let colors = graph_coloring_list(&adj, 3).unwrap();
        assert_eq!(colors.len(), 4);
    }

    #[test]
    fn test_greedy() {
        let adj = vec![vec![1, 2, 3], vec![0, 2], vec![0, 1, 3], vec![0, 2]];
        let colors = greedy_coloring(&adj);
        for (node, neighbors) in adj.iter().enumerate() {
            for &nb in neighbors {
                assert_ne!(colors[node], colors[nb]);
            }
        }
    }
}

(* 1069: Graph Coloring — Backtracking *)

(* Approach 1: Basic backtracking *)
let graph_coloring adj_matrix num_colors =
  let n = Array.length adj_matrix in
  let colors = Array.make n 0 in
  let is_safe node color =
    let safe = ref true in
    for i = 0 to n - 1 do
      if adj_matrix.(node).(i) = 1 && colors.(i) = color then
        safe := false
    done;
    !safe
  in
  let rec solve node =
    if node = n then true
    else begin
      let found = ref false in
      for c = 1 to num_colors do
        if not !found && is_safe node c then begin
          colors.(node) <- c;
          if solve (node + 1) then found := true
          else colors.(node) <- 0
        end
      done;
      !found
    end
  in
  if solve 0 then Some (Array.to_list colors) else None

(* Approach 2: With adjacency list *)
let graph_coloring_adj adj_list num_colors n =
  let colors = Array.make n 0 in
  let is_safe node color =
    List.for_all (fun neighbor ->
      colors.(neighbor) <> color
    ) adj_list.(node)
  in
  let rec solve node =
    if node = n then true
    else
      let found = ref false in
      for c = 1 to num_colors do
        if not !found && is_safe node c then begin
          colors.(node) <- c;
          if solve (node + 1) then found := true
          else colors.(node) <- 0
        end
      done;
      !found
  in
  if solve 0 then Some (Array.to_list colors) else None

let () =
  (* Petersen-like graph: 4 nodes, edges: 0-1, 1-2, 2-3, 3-0, 0-2 *)
  let adj = [|
    [|0;1;1;1|];
    [|1;0;1;0|];
    [|1;1;0;1|];
    [|1;0;1;0|]
  |] in
  (match graph_coloring adj 3 with
   | Some colors -> assert (List.length colors = 4)
   | None -> assert false);
  assert (graph_coloring adj 2 = None);

  let adj_list = [|[1;2;3]; [0;2]; [0;1;3]; [0;2]|] in
  (match graph_coloring_adj adj_list 3 4 with
   | Some colors -> assert (List.length colors = 4)
   | None -> assert false);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_graph_coloring_possible() {
        let adj = vec![
            vec![0, 1, 1, 1],
            vec![1, 0, 1, 0],
            vec![1, 1, 0, 1],
            vec![1, 0, 1, 0],
        ];
        let colors = graph_coloring(&adj, 3).unwrap();
        assert_eq!(colors.len(), 4);
        // Verify no adjacent nodes share color
        for i in 0..4 {
            for j in 0..4 {
                if adj[i][j] == 1 {
                    assert_ne!(colors[i], colors[j]);
                }
            }
        }
    }

    #[test]
    fn test_graph_coloring_impossible() {
        let adj = vec![
            vec![0, 1, 1, 1],
            vec![1, 0, 1, 0],
            vec![1, 1, 0, 1],
            vec![1, 0, 1, 0],
        ];
        assert!(graph_coloring(&adj, 2).is_none());
    }

    #[test]
    fn test_graph_coloring_list() {
        let adj = vec![vec![1, 2, 3], vec![0, 2], vec![0, 1, 3], vec![0, 2]];
        let colors = graph_coloring_list(&adj, 3).unwrap();
        assert_eq!(colors.len(), 4);
    }

    #[test]
    fn test_greedy() {
        let adj = vec![vec![1, 2, 3], vec![0, 2], vec![0, 1, 3], vec![0, 2]];
        let colors = greedy_coloring(&adj);
        for (node, neighbors) in adj.iter().enumerate() {
            for &nb in neighbors {
                assert_ne!(colors[node], colors[nb]);
            }
        }
    }
}

Deep Comparison

Graph Coloring — Comparison

Core Insight

Graph coloring assigns colors to vertices so no edge connects same-colored vertices. Backtracking tries each color, backtracks on conflict. Greedy coloring is fast but may use more colors than optimal.

OCaml Approach

• Array for colors with 0 as uncolored sentinel

• List.for_all for adjacency list safety check

• ref flag for early exit from color loop

Rust Approach

• Vec<usize> for colors, inner fn for recursion

• .iter().all() for adjacency list safety — idiomatic

• HashSet in greedy approach to find first unused color

• (1..).find() — infinite iterator to find smallest available color

Comparison Table

Aspect	OCaml	Rust
Safety check (list)	`List.for_all`	`.iter().all()`
Early exit	`ref` flag + `not !found`	`return true/false`
Greedy first-fit	Would use `List.find`	`(1..).find(\\|c\\| !used.contains(c))`
Graph representation	`int array array` or `int list array`	`Vec<Vec<i32>>` or `Vec<Vec<usize>>`

Exercises

Implement chromatic_number(adj: &[Vec<i32>]) -> usize that finds the minimum number of colors needed by trying k = 1, 2, ... until a valid coloring exists.

Extend to weighted graph coloring where each vertex has a processing time and colors represent time slots — find a valid schedule minimizing the last end time.

Write a is_bipartite(adj: &[Vec<i32>]) -> bool function using BFS 2-coloring as a special case.

Open Source Repos

functional-rust

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

Rust