Skip to main content

search_coloring

competitive::algorithm::chromatic_number

Function search_coloring 

Source 
fn search_coloring(
    g: &[usize],
    deg: &[u32],
    sat: &mut [usize],
    rem: usize,
    used: usize,
    best: &mut usize,
)
Examples found in repository?
crates/competitive/src/algorithm/chromatic_number.rs (line 14)
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}