competitive/algorithm/
chromatic_number.rs

1/// The smallest number of colors needed to color an undirected graph.
2pub fn chromatic_number(n: usize, edges: &[(usize, usize)]) -> usize {
3    assert!(n < usize::BITS as usize);
4    if n == 0 {
5        return 0;
6    }
7    let mut g = vec![0usize; n];
8    for &(u, v) in edges {
9        g[u] |= 1 << v;
10        g[v] |= 1 << u;
11    }
12    let deg: Vec<_> = g.iter().map(|g| g.count_ones()).collect();
13    let mut best = greedy_coloring(&g, &deg);
14    search_coloring(&g, &deg, &mut vec![0; n], (1 << n) - 1, 0, &mut best);
15    best
16}
17
18fn select_vertex(mut cand: usize, deg: &[u32], sat: &[usize]) -> usize {
19    let mut v = cand.trailing_zeros() as usize;
20    cand &= cand - 1;
21    let mut key = (sat[v].count_ones(), deg[v]);
22    while cand != 0 {
23        let u = cand.trailing_zeros() as usize;
24        cand &= cand - 1;
25        let next = (sat[u].count_ones(), deg[u]);
26        if next > key {
27            key = next;
28            v = u;
29        }
30    }
31    v
32}
33
34fn greedy_coloring(g: &[usize], deg: &[u32]) -> usize {
35    let n = g.len();
36    let mut rem = (1usize << n) - 1;
37    let mut sat = vec![0usize; n];
38    let mut used = 0;
39    while rem != 0 {
40        let v = select_vertex(rem, deg, &sat);
41        let c = (!sat[v]).trailing_zeros() as usize;
42        used = used.max(c + 1);
43        rem &= !(1 << v);
44        let mut next = g[v] & rem;
45        while next != 0 {
46            let u = next.trailing_zeros() as usize;
47            next &= next - 1;
48            sat[u] |= 1 << c;
49        }
50    }
51    used
52}
53
54fn search_coloring(
55    g: &[usize],
56    deg: &[u32],
57    sat: &mut [usize],
58    rem: usize,
59    used: usize,
60    best: &mut usize,
61) {
62    if rem == 0 {
63        *best = used;
64        return;
65    }
66    if used >= *best {
67        return;
68    }
69    let v = select_vertex(rem, deg, sat);
70    let rem = rem & !(1 << v);
71    let mut colors = ((1 << used) - 1) & !sat[v];
72    if used + 1 < *best {
73        colors |= 1 << used;
74    }
75    while colors != 0 {
76        let color = colors & colors.wrapping_neg();
77        colors ^= color;
78        let mut next = g[v] & rem;
79        let mut changed = 0usize;
80        while next != 0 {
81            let u = next.trailing_zeros() as usize;
82            next &= next - 1;
83            if sat[u] & color == 0 {
84                sat[u] |= color;
85                changed |= 1 << u;
86            }
87        }
88        search_coloring(
89            g,
90            deg,
91            sat,
92            rem,
93            used.max(color.trailing_zeros() as usize + 1),
94            best,
95        );
96        while changed != 0 {
97            let u = changed.trailing_zeros() as usize;
98            changed &= changed - 1;
99            sat[u] ^= color;
100        }
101    }
102}
103
104#[cfg(test)]
105mod tests {
106    use super::*;
107    use crate::tools::Xorshift;
108
109    #[test]
110    fn test_chromatic_number() {
111        let mut rng = Xorshift::default();
112        for _ in 0..100 {
113            let n = rng.random(0..=12);
114            let mut edges = Vec::new();
115            for u in 0..n {
116                for v in u + 1..n {
117                    if rng.gen_bool(0.5) {
118                        edges.push((u, v));
119                    }
120                }
121            }
122            let mut g = vec![0usize; n];
123            for &(u, v) in &edges {
124                g[u] |= 1 << v;
125                g[v] |= 1 << u;
126            }
127            let mut independent = vec![true; 1 << n];
128            for s in 1usize..1 << n {
129                let v = s.trailing_zeros() as usize;
130                independent[s] = independent[s ^ (1 << v)] && g[v] & s == 0;
131            }
132            let mut dp = vec![n; 1 << n];
133            dp[0] = 0;
134            for s in 1usize..1 << n {
135                let first = 1 << s.trailing_zeros();
136                let mut subset = s;
137                while subset != 0 {
138                    if subset & first != 0 && independent[subset] {
139                        dp[s] = dp[s].min(dp[s ^ subset] + 1);
140                    }
141                    subset = (subset - 1) & s;
142                }
143            }
144            assert_eq!(dp[(1 << n) - 1], chromatic_number(n, &edges));
145        }
146    }
147}
competitive/algorithm/chromatic_number.rs

competitive/algorithm/
chromatic_number.rs
