Coloring — the two-versus-three cliff

Two-coloring is cheap. Three-coloring is famously expensive. The boundary appears in scheduling, register allocation, and frequency assignment.

1. 01
   petgraph's is_bipartite_undirected answers the two-color question in linear time — a BFS that two-colors as it walks. For three or more colors, encode "vertex v gets color c" as Boolean variables and hand the formula to splr.

   use petgraph::algo::is_bipartite_undirected;
   use petgraph::graph::UnGraph;
   
   fn two_colorable(g: &UnGraph<&str, ()>) -> bool {
       if let Some(start) = g.node_indices().next() {
           is_bipartite_undirected(g, start)
       } else { true }
   }
   
   // Three or more colors: build CNF and dispatch to splr (page 23).
   // At least one color per vertex, at most one color per vertex,
   // adjacent vertices differ.  Linear in the encoding, exponential
   // in the search — but solvers handle real instances at scale.

2. 02
   if let is matching" data-term="pattern matching">pattern matching used as a conditional. Read the syntax as: "if the value on the right matches the pattern on the left, bind the names and run the if block; otherwise run the else block (which is optional)." It is sugar for a match with one explicit arm and a wildcard fallthrough — same logic, less ceremony. On this page, g.node_indices().next() returns Option<NodeIndex> — None if the graph has no nodes, Some(first) otherwise. The if let Some(start) = … form unwraps the Some directly and binds start for the body of the if; the else branch handles the empty-graph case (returns true vacuously, since a graph with no nodes is trivially 2-colorable). The same control flow with match would be three more lines and a leftover wildcard arm.

   // if let — pattern match as a conditional.
   //
   //   if let PATTERN = EXPRESSION {
   //       /* runs when PATTERN matches; bindings are in scope here */
   //   } else {
   //       /* runs otherwise (else is optional) */
   //   }
   
   // Equivalent match expression:
   //   match EXPRESSION {
   //       PATTERN => { /* matched branch */ },
   //       _       => { /* fallthrough */ },
   //   }
   
   
   // Common case: peel apart an Option.
   let maybe_name: Option<&str> = Some("Alice");
   
   if let Some(name) = maybe_name {
       println!("hello, {}", name);
   } else {
       println!("no name");
   }
   
   // Same logic with match — more lines, more brackets:
   match maybe_name {
       Some(name) => println!("hello, {}", name),
       None       => println!("no name"),
   }
   
   
   // Works for any pattern, not just Option/Result:
   enum Event { Click { x: i32, y: i32 }, Scroll(i32), Quit }
   
   let e = Event::Click { x: 10, y: 20 };
   
   if let Event::Click { x, y } = e {
       println!("click at ({}, {})", x, y);
   }
   // (no else — the other variants are silently ignored.)
   
   
   // Companion forms in the same family:
   
   // let-else (Rust 1.65+) — eager unwrap with mandatory diverging branch.
   let Some(name) = maybe_name else {
       return;   // or break, continue, panic, ...
   };
   println!("hello, {}", name);            // `name` is in scope from here
   
   // while let — loop variant.  Iterate as long as the pattern matches.
   let mut stack = vec![1, 2, 3];
   while let Some(top) = stack.pop() {
       println!("{}", top);
   }
   // prints 3, 2, 1; stops automatically when pop() returns None.
   
   
   // Page 28's specific use — handle the empty-graph case:
   fn two_colorable(g: &UnGraph<&str, ()>) -> bool {
       if let Some(start) = g.node_indices().next() {
           is_bipartite_undirected(g, start)         // graph has nodes — check it
       } else {
           true                                       // empty graph — vacuously 2-colorable
       }
   }
   
   // Without if-let, the same logic looks like this:
   fn two_colorable_match(g: &UnGraph<&str, ()>) -> bool {
       match g.node_indices().next() {
           Some(start) => is_bipartite_undirected(g, start),
           None        => true,
       }
   }
   // Same behavior — if-let is just the shorter, idiomatic spelling when
   // only one variant carries interesting work.