Rust, 8,7
in 3 minutes on the Rust playground
use std::time::Instant;
use std::{
collections::HashMap,
hash::Hash,
sync::atomic::{AtomicU32, Ordering},
};
use rayon::prelude::*;
const MAX_THREADS: usize = 4;
static NUM_TASKS: AtomicU32 = AtomicU32::new(0);
#[derive(Clone, Copy, Debug)]
struct Edge {
opposite_edge: u32,
opposite_color: u32,
opposite_vertex: u16,
}
#[repr(C)]
#[derive(Clone, Copy)]
struct Color {
up: u32,
down: u32,
vertex: u16,
last_edge: u32,
}
#[repr(C)]
#[derive(Clone, Copy)]
struct Vertex {
up: u32,
down: u32,
left: u16,
right: u16,
count_colors: u16,
count_edges: u16,
}
#[repr(C)]
#[derive(Clone, Copy)]
struct Root {
padding_1: u64,
left: u16,
right: u16,
padding_2: u32,
}
impl Root {
fn new() -> Self {
Self {
padding_1: 0,
left: 0,
right: 0,
padding_2: 0,
}
}
}
// the reason for repr(C) is so color/vertex up/down are in the same locations
#[repr(C, align(16))]
#[derive(Clone, Copy)]
union Node {
edge: Edge,
color: Color,
vertex: Vertex,
root: Root,
}
impl Default for Node {
fn default() -> Self {
Self { root: Root::new() }
}
}
#[derive(Clone)]
struct GraphColoring {
nodes: Vec<Node>,
allowance: u32,
// num_checks: u64,
max_colors: u32,
}
impl GraphColoring {
fn edge_mut(&mut self, idx: u32) -> &mut Edge {
unsafe { &mut self.nodes.get_mut(idx as usize).unwrap_unchecked().edge }
}
fn color_mut(&mut self, idx: u32) -> &mut Color {
unsafe { &mut self.nodes.get_mut(idx as usize).unwrap_unchecked().color }
}
fn vertex_mut(&mut self, idx: u16) -> &mut Vertex {
unsafe { &mut self.nodes.get_mut(idx as usize).unwrap_unchecked().vertex }
}
fn edge(&self, idx: u32) -> Edge {
unsafe { self.nodes.get(idx as usize).unwrap_unchecked().edge }
}
fn color(&self, idx: u32) -> Color {
unsafe { self.nodes.get(idx as usize).unwrap_unchecked().color }
}
fn vertex(&self, idx: u16) -> Vertex {
unsafe { self.nodes.get(idx as usize).unwrap_unchecked().vertex }
}
fn pick_min_vertex(&self) -> Option<(u16, u16)> {
let mut idx = self.vertex(0).right;
if idx == 0 {
return None;
}
let mut fewest_colors = self.max_colors as _;
let mut most_edges = 0;
let mut bestidx = idx;
loop {
let vertex = self.vertex(idx);
if vertex.count_colors < fewest_colors
|| (vertex.count_colors == fewest_colors && vertex.count_edges > most_edges)
{
if vertex.count_colors == 0 {
return Some((0, 0));
}
if vertex.count_colors == 1 {
return Some((idx, 1));
}
fewest_colors = vertex.count_colors;
most_edges = vertex.count_edges;
bestidx = idx;
}
idx = vertex.right;
if idx == 0 {
break;
}
}
Some((bestidx, fewest_colors))
}
fn disconnect_color(&mut self, color_idx: u32, color: Color) {
for idx in color_idx + 1..=color.last_edge {
let edge = self.edge(idx);
let opposite_edge_idx = edge.opposite_edge;
let opposite_color_idx = edge.opposite_color;
let opposite_color = self.color(opposite_color_idx);
debug_assert!(opposite_edge_idx <= opposite_color.last_edge);
debug_assert!(opposite_edge_idx >= opposite_color_idx);
if opposite_edge_idx < opposite_color.last_edge {
// swap nodes at opposite_edge_idx and opposite_color.last_edge
// that means our pointer has to change, as well as last_edges oppoosite_edge has to change
let last_edge_idx = opposite_color.last_edge;
let last_edge = self.edge(last_edge_idx);
let last_edge_opposite_idx = last_edge.opposite_edge;
self.edge_mut(last_edge_opposite_idx).opposite_edge = opposite_edge_idx;
*self.edge_mut(opposite_edge_idx) = Edge {
opposite_edge: last_edge_opposite_idx,
opposite_color: last_edge.opposite_color,
opposite_vertex: last_edge.opposite_vertex,
};
*self.edge_mut(last_edge_idx) = Edge {
opposite_edge: idx,
opposite_color: color_idx,
opposite_vertex: color.vertex,
};
// self.edge_mut(last_edge_idx).opposite_edge = idx;
// self.edge_mut(last_edge_idx).opposite_color = color_idx;
self.edge_mut(idx).opposite_edge = last_edge_idx;
}
self.color_mut(opposite_color_idx).last_edge -= 1;
self.vertex_mut(opposite_color.vertex).count_edges -= 1;
debug_assert_eq!(
self.edge(idx).opposite_edge,
self.color(edge.opposite_color).last_edge + 1
);
}
}
fn reconnect_color(&mut self, color_idx: u32, color: Color) {
for edge_idx in (color_idx + 1..=color.last_edge).rev() {
let edge = self.edge(edge_idx);
debug_assert_eq!(
edge.opposite_edge,
self.color(edge.opposite_color).last_edge + 1
);
self.color_mut(edge.opposite_color).last_edge += 1;
let color = self.color(edge.opposite_color);
self.vertex_mut(color.vertex).count_edges += 1;
}
}
#[inline]
fn remove_adjacent(&mut self, color_idx: u32, color: Color) {
for edge_idx in (color_idx + 1..=color.last_edge).rev() {
let edge = self.edge(edge_idx);
let color1_idx = edge.opposite_color;
let color1 = self.color(color1_idx);
self.disconnect_color(color1_idx, color1);
self.color_mut(color1.up).down = color1.down;
self.color_mut(color1.down).up = color1.up;
let vertex = self.vertex_mut(color1.vertex);
vertex.count_colors -= 1;
vertex.count_edges -= (color1.last_edge - color1_idx) as u16;
}
}
fn reconnect_adjacent(&mut self, color_idx: u32, color: Color) {
for edge_idx in color_idx + 1..=color.last_edge {
let edge = self.edge(edge_idx);
let color1_idx = edge.opposite_color;
let color1 = self.color(color1_idx);
self.reconnect_color(color1_idx, color1);
self.color_mut(color1.up).down = color1_idx;
self.color_mut(color1.down).up = color1_idx;
let vertex = self.vertex_mut(color1.vertex);
vertex.count_colors += 1;
vertex.count_edges += (color1.last_edge - color1_idx) as u16;
}
}
fn check(&mut self) -> bool {
let (vertex_idx, count) = match self.pick_min_vertex() {
None => {
return true;
}
Some(x) => x,
};
if count == 0 {
return false;
}
// self.num_checks += 1;
let vertex_idx = vertex_idx as u32;
let mut idx = self.color(vertex_idx).down;
while idx != vertex_idx {
let color = self.color(idx);
self.disconnect_color(idx, color);
idx = color.down;
}
let mut allowance = count as u32 - self.allowance;
let vertex = self.vertex(vertex_idx as _);
self.vertex_mut(vertex.left).right = vertex.right;
self.vertex_mut(vertex.right).left = vertex.left;
idx = vertex.down;
let has_allowance = self.allowance > 0;
let x = count as u32 - self.allowance.saturating_sub(1);
let num_tasks = NUM_TASKS.load(Ordering::Relaxed);
let parallel = num_tasks < MAX_THREADS as u32
&& NUM_TASKS
.compare_exchange_weak(
num_tasks,
num_tasks + x - 1,
Ordering::SeqCst,
Ordering::Relaxed,
)
.is_ok();
if parallel {
let mut tasks = Vec::new();
while idx != vertex_idx {
let color = self.color(idx);
if has_allowance && allowance == 0 {
self.allowance -= 1;
}
if (idx + 1..=color.last_edge).all(|edge_idx| {
self.vertex(self.edge(edge_idx).opposite_vertex)
.count_colors
> 1
}) {
self.remove_adjacent(idx, color);
tasks.push(self.clone());
self.reconnect_adjacent(idx, color);
}
if has_allowance && allowance == 0 {
self.allowance += 1;
break;
}
idx = self.color(idx).down;
allowance -= 1;
}
idx = self.color(vertex_idx).up;
while idx != vertex_idx {
let color = self.color(idx);
self.reconnect_color(idx, color);
idx = color.up;
}
self.vertex_mut(vertex.left).right = vertex_idx as _;
self.vertex_mut(vertex.right).left = vertex_idx as _;
let o = tasks.par_drain(..).any(|mut i| i.check());
NUM_TASKS.fetch_sub(x - 1, Ordering::Relaxed);
o
} else {
while idx != vertex_idx {
let color = self.color(idx);
if has_allowance && allowance == 0 {
self.allowance -= 1;
}
if (idx + 1..=color.last_edge).all(|edge_idx| {
self.vertex(self.edge(edge_idx).opposite_vertex)
.count_colors
> 1
}) {
self.remove_adjacent(idx, color);
if self.check() {
return true;
}
self.reconnect_adjacent(idx, color);
}
if has_allowance && allowance == 0 {
self.allowance += 1;
break;
}
idx = self.color(idx).down;
allowance -= 1;
}
idx = self.color(vertex_idx).up;
while idx != vertex_idx {
let color = self.color(idx);
self.reconnect_color(idx, color);
idx = color.up;
}
self.vertex_mut(vertex.left).right = vertex_idx as _;
self.vertex_mut(vertex.right).left = vertex_idx as _;
false
}
}
fn new<T, F>(vertices: &Vec<T>, adjacent: F, max_colors: u32) -> GraphColoring
where
F: Fn(T, T) -> bool,
T: Hash + Eq + Copy,
{
let mut this = GraphColoring {
nodes: vec![Node::default()],
allowance: max_colors,
// num_checks: 0,
max_colors,
};
let mut vertex_idxs = HashMap::new();
// add vertex nodes
for &v in vertices {
let vertex_idx = this.nodes.len() as u16;
let left_idx = vertex_idx - 1;
let right_idx = 0;
let vertex = Vertex {
up: vertex_idx as _,
down: vertex_idx as _,
left: left_idx,
right: right_idx,
count_colors: 0,
count_edges: 0,
};
vertex_idxs.insert(v, vertex_idx);
this.nodes.push(Node { vertex });
this.vertex_mut(left_idx).right = vertex_idx;
this.vertex_mut(right_idx).left = vertex_idx;
}
let mut edge_to_idx = HashMap::new();
// add colors
for &a in vertices {
let vertex_a_idx = vertex_idxs[&a];
for k in 0..max_colors {
let color_a_idx = this.nodes.len() as _;
let up_idx = this.vertex(vertex_a_idx).up;
let down_idx = vertex_a_idx as _;
let color_a = Color {
up: up_idx,
down: down_idx,
vertex: vertex_a_idx,
last_edge: color_a_idx,
};
this.nodes.push(Node { color: color_a });
this.color_mut(up_idx).down = color_a_idx;
this.color_mut(down_idx).up = color_a_idx;
this.vertex_mut(vertex_a_idx).count_colors += 1;
// and edges
for &b in vertices {
if a == b {
continue;
}
if adjacent(a, b) {
let edge_a_idx = this.nodes.len() as _;
let edge_a = match edge_to_idx.get(&(b, a, k)) {
Some(&(edge_b_idx, color_b_idx, vertex_b_idx)) => {
this.edge_mut(edge_b_idx).opposite_color = color_a_idx;
this.edge_mut(edge_b_idx).opposite_edge = edge_a_idx;
this.edge_mut(edge_b_idx).opposite_vertex = vertex_a_idx;
Node {
edge: Edge {
opposite_color: color_b_idx,
opposite_edge: edge_b_idx,
opposite_vertex: vertex_b_idx,
},
}
}
None => {
edge_to_idx
.insert((a, b, k), (edge_a_idx, color_a_idx, vertex_a_idx));
Node::default()
}
};
this.nodes.push(edge_a);
this.color_mut(color_a_idx).last_edge = edge_a_idx;
this.vertex_mut(vertex_a_idx).count_edges += 1;
}
}
}
}
this
}
fn chromatic_number(n: u32, d: u32, max_colors: u32) -> bool {
if d % 2 == 1 {
return max_colors >= 2;
}
let mut g = GraphColoring::new(
&(0_u32..1 << n)
.filter(|&i| i.count_ones() % 2 == 0)
.collect(),
|a, b| (a ^ b).count_ones() == d,
max_colors,
);
let out = g.check();
// println!("Num checks: {}", g.num_checks);
out
}
}
fn chromatic(n: u32, d: u32) -> u32 {
for k in 2.. {
if GraphColoring::chromatic_number(n, d, k) {
return k;
}
}
panic!("You're never gonna reach this");
}
fn main() {
let start = Instant::now();
rayon::ThreadPoolBuilder::new()
.num_threads(MAX_THREADS)
.build_global()
.unwrap();
for n in 2..=8 {
for d in 1..n {
println!("{},{} -> {}", n, d, chromatic(n, d));
}
}
println!("Finished in: {:?}", start.elapsed());
}
Try it online!
Formulates the decision problem as an exact cover problem and then uses dancing links to solve it.
Specifically, rows correspond to coloring a vertex a color. The columns correspond to the conditions that each vertex is covered by exactly one color, and that each edge has at most one vertex for any given color.
There are two graph coloring specific optimizations:
Colors are chosen in order. That is, when choosing the color for a vertex, only one of the colors that haven't yet been chosen must be considered. Without this optimization, proving that f(8,6)
is not 5
takes 415 million steps, with the optimization it takes around 1 million steps (and it's presumably even more effective for proving the chromatic number is not 6, since it's pruning more colors in that case).
Ties are broken by finding the vertex with the maximum number of unassigned neighbors. This is also a pretty good optimization, without it (but with the previous) 4,225,666,594 steps are required to prove the chromatic number is not 6, with it only 299,285,005 steps are necessary.
If you run it on your own computer, make sure to run cargo add rayon
and compile with the RUSTFLAGS=-Ctarget-cpu=native
environment variable.
9,2
to be13
. The calculations apparently took 5650 days of CPU time on a single core, which doesn't bode well for harder cases. (In fact, @Bubbler, that's a case where the fractional chromatic number bound (12.8) is tight) \$\endgroup\$