807 Advanced

807-bipartite-check — Bipartite Check

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "807-bipartite-check — Bipartite Check" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. A bipartite graph can be 2-colored: vertices split into two sets where all edges go between sets (no edges within a set). Key difference from OCaml: 1. **BFS queue**: Rust uses `VecDeque<usize>` (FIFO); OCaml uses `Queue.t` — equivalent data structures.

Tutorial

The Problem

A bipartite graph can be 2-colored: vertices split into two sets where all edges go between sets (no edges within a set). BFS-based 2-coloring checks bipartiteness in O(V+E). Applications: job matching (workers and jobs are two sets), recommendation systems (users and items), scheduling (tasks and time slots), and the fundamental theorem that a graph is bipartite if and only if it contains no odd-length cycles.

🎯 Learning Outcomes

• Implement BFS 2-coloring: assign alternating colors to adjacent vertices

• Detect non-bipartiteness: same color on adjacent vertices during BFS

• Handle disconnected graphs: run BFS from every uncolored vertex

• Understand the bipartite-iff-no-odd-cycles theorem

• Apply to matching problems (König's theorem: max matching = min vertex cover in bipartite graphs)

Code Example

#![allow(clippy::all)]
//! # Bipartite Check
pub fn is_bipartite(n: usize, edges: &[(usize, usize)]) -> bool {
    let mut adj = vec![vec![]; n];
    for &(u, v) in edges {
        adj[u].push(v);
        adj[v].push(u);
    }
    let mut color = vec![None; n];
    fn bfs(start: usize, adj: &[Vec<usize>], color: &mut [Option<bool>]) -> bool {
        use std::collections::VecDeque;
        let mut q = VecDeque::new();
        q.push_back(start);
        color[start] = Some(true);
        while let Some(u) = q.pop_front() {
            for &v in &adj[u] {
                if color[v].is_none() {
                    color[v] = Some(!color[u].unwrap());
                    q.push_back(v);
                } else if color[v] == color[u] {
                    return false;
                }
            }
        }
        true
    }
    for v in 0..n {
        if color[v].is_none() && !bfs(v, &adj, &mut color) {
            return false;
        }
    }
    true
}
#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_bipartite() {
        assert!(is_bipartite(4, &[(0, 1), (1, 2), (2, 3), (3, 0)]));
    }
    #[test]
    fn test_not_bipartite() {
        assert!(!is_bipartite(3, &[(0, 1), (1, 2), (2, 0)]));
    }
}

(* Bipartite Check — BFS 2-colouring O(V+E) *)

let is_bipartite adj n =
  let color = Array.make n (-1) in
  let result = ref true in
  let q = Queue.create () in
  for start = 0 to n - 1 do
    if color.(start) = -1 && !result then begin
      color.(start) <- 0;
      Queue.push start q;
      while not (Queue.is_empty q) && !result do
        let u = Queue.pop q in
        List.iter (fun v ->
          if color.(v) = -1 then begin
            color.(v) <- 1 - color.(u);
            Queue.push v q
          end else if color.(v) = color.(u) then
            result := false
        ) adj.(u)
      done
    end
  done;
  if !result then Some color else None

let () =
  let n1  = 4 in
  let adj1 = Array.make n1 [] in
  let add1 u v = adj1.(u) <- v :: adj1.(u); adj1.(v) <- u :: adj1.(v) in
  add1 0 1; add1 1 2; add1 2 3; add1 3 0;  (* 4-cycle — bipartite *)
  (match is_bipartite adj1 n1 with
   | None   -> Printf.printf "4-cycle: NOT bipartite\n"
   | Some c -> Printf.printf "4-cycle: bipartite, colors=[%s]\n"
       (String.concat "," (Array.to_list (Array.map string_of_int c))));

  let n2   = 3 in
  let adj2 = Array.make n2 [] in
  let add2 u v = adj2.(u) <- v :: adj2.(u); adj2.(v) <- u :: adj2.(v) in
  add2 0 1; add2 1 2; add2 2 0;  (* triangle — not bipartite *)
  (match is_bipartite adj2 n2 with
   | None   -> Printf.printf "Triangle: NOT bipartite\n"
   | Some c -> Printf.printf "Triangle: bipartite, colors=[%s]\n"
       (String.concat "," (Array.to_list (Array.map string_of_int c))))

Key Differences

BFS queue: Rust uses VecDeque<usize> (FIFO); OCaml uses Queue.t — equivalent data structures.

Color representation: Rust uses Option<bool> (uncolored / colored); OCaml uses int option or bool option similarly.

Disconnected graphs: Both check all vertices to handle disconnected graphs — the for v in 0..n outer loop is identical.

Matching connection: Bipartite check is a prerequisite for maximum bipartite matching (Hopcroft-Karp); both languages use the same foundation.

OCaml Approach

OCaml implements BFS with Queue.t and a color: bool option array. The Queue.add / Queue.pop pattern drives the BFS. OCaml's Option.map applies color flipping functionally. The Ocamlgraph library provides Coloring.check_bipartite. OCaml's for v in adj.(u) do ... is idiomatic for adjacency list traversal.

Full Source

#![allow(clippy::all)]
//! # Bipartite Check
pub fn is_bipartite(n: usize, edges: &[(usize, usize)]) -> bool {
    let mut adj = vec![vec![]; n];
    for &(u, v) in edges {
        adj[u].push(v);
        adj[v].push(u);
    }
    let mut color = vec![None; n];
    fn bfs(start: usize, adj: &[Vec<usize>], color: &mut [Option<bool>]) -> bool {
        use std::collections::VecDeque;
        let mut q = VecDeque::new();
        q.push_back(start);
        color[start] = Some(true);
        while let Some(u) = q.pop_front() {
            for &v in &adj[u] {
                if color[v].is_none() {
                    color[v] = Some(!color[u].unwrap());
                    q.push_back(v);
                } else if color[v] == color[u] {
                    return false;
                }
            }
        }
        true
    }
    for v in 0..n {
        if color[v].is_none() && !bfs(v, &adj, &mut color) {
            return false;
        }
    }
    true
}
#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_bipartite() {
        assert!(is_bipartite(4, &[(0, 1), (1, 2), (2, 3), (3, 0)]));
    }
    #[test]
    fn test_not_bipartite() {
        assert!(!is_bipartite(3, &[(0, 1), (1, 2), (2, 0)]));
    }
}

(* Bipartite Check — BFS 2-colouring O(V+E) *)

let is_bipartite adj n =
  let color = Array.make n (-1) in
  let result = ref true in
  let q = Queue.create () in
  for start = 0 to n - 1 do
    if color.(start) = -1 && !result then begin
      color.(start) <- 0;
      Queue.push start q;
      while not (Queue.is_empty q) && !result do
        let u = Queue.pop q in
        List.iter (fun v ->
          if color.(v) = -1 then begin
            color.(v) <- 1 - color.(u);
            Queue.push v q
          end else if color.(v) = color.(u) then
            result := false
        ) adj.(u)
      done
    end
  done;
  if !result then Some color else None

let () =
  let n1  = 4 in
  let adj1 = Array.make n1 [] in
  let add1 u v = adj1.(u) <- v :: adj1.(u); adj1.(v) <- u :: adj1.(v) in
  add1 0 1; add1 1 2; add1 2 3; add1 3 0;  (* 4-cycle — bipartite *)
  (match is_bipartite adj1 n1 with
   | None   -> Printf.printf "4-cycle: NOT bipartite\n"
   | Some c -> Printf.printf "4-cycle: bipartite, colors=[%s]\n"
       (String.concat "," (Array.to_list (Array.map string_of_int c))));

  let n2   = 3 in
  let adj2 = Array.make n2 [] in
  let add2 u v = adj2.(u) <- v :: adj2.(u); adj2.(v) <- u :: adj2.(v) in
  add2 0 1; add2 1 2; add2 2 0;  (* triangle — not bipartite *)
  (match is_bipartite adj2 n2 with
   | None   -> Printf.printf "Triangle: NOT bipartite\n"
   | Some c -> Printf.printf "Triangle: bipartite, colors=[%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_bipartite() {
        assert!(is_bipartite(4, &[(0, 1), (1, 2), (2, 3), (3, 0)]));
    }
    #[test]
    fn test_not_bipartite() {
        assert!(!is_bipartite(3, &[(0, 1), (1, 2), (2, 0)]));
    }
}

Deep Comparison

OCaml vs Rust: Bipartite Check

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 bipartite_partition(n, edges) -> Option<(Vec<usize>, Vec<usize>)> that returns the two vertex sets if bipartite, or None if not.

Find the shortest odd cycle in a non-bipartite graph using BFS level tracking — the cycle length is the graph's "odd girth."

Implement maximum bipartite matching using the augmenting path algorithm (Hungarian / Hopcroft-Karp), building on the bipartite check.

Open Source Repos

functional-rust

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

Rust