rust_igraph/algorithms/properties/
graph_coloring.rs

1//! Greedy vertex coloring and chromatic bounds (ALGO-TR-028).
2//!
3//! - **Greedy coloring**: assign the smallest available colour to each
4//!   vertex, processing vertices in the given order. The number of
5//!   colours used depends on the vertex ordering.
6//! - **Greedy coloring (largest-first)**: process vertices in
7//!   descending degree order — a simple heuristic that often uses
8//!   fewer colours.
9//! - **Chromatic number upper bound**: the greedy largest-first
10//!   colouring provides `χ(G) ≤ greedy_colors`.
11//! - **Chromatic number lower bound**: `χ(G) ≥ max clique size`
12//!   (clique number); approximated here via the largest clique found
13//!   by a greedy search.
14
15#![allow(
16    clippy::cast_possible_truncation,
17    clippy::cast_precision_loss,
18    clippy::many_single_char_names,
19    clippy::needless_range_loop,
20    clippy::too_many_lines
21)]
22
23use crate::core::{Graph, IgraphError, IgraphResult};
24
25/// Greedy vertex coloring in natural vertex order.
26///
27/// Assigns each vertex the smallest colour (0-based) not used by any
28/// of its already-coloured neighbours. Returns the colour assignment
29/// as a `Vec<u32>` indexed by vertex id.
30///
31/// Works for both directed and undirected graphs (for directed graphs,
32/// both in- and out-neighbours are considered as "adjacent").
33///
34/// # Examples
35///
36/// ```
37/// use rust_igraph::{Graph, greedy_coloring};
38///
39/// // Path 0-1-2: greedy gives {0, 1, 0}
40/// let g = Graph::from_edges(&[(0,1),(1,2)], false, Some(3)).unwrap();
41/// let c = greedy_coloring(&g).unwrap();
42/// assert_eq!(c, vec![0, 1, 0]);
43/// ```
44pub fn greedy_coloring(graph: &Graph) -> IgraphResult<Vec<u32>> {
45    greedy_coloring_with_order(graph, None)
46}
47
48/// Greedy vertex coloring with a custom vertex processing order.
49///
50/// If `order` is `None`, processes vertices in natural order (0, 1, …).
51/// Otherwise, processes vertices in the order given by the slice.
52///
53/// # Examples
54///
55/// ```
56/// use rust_igraph::{Graph, greedy_coloring_with_order};
57///
58/// let g = Graph::from_edges(&[(0,1),(1,2),(0,2)], false, Some(3)).unwrap();
59/// let c = greedy_coloring_with_order(&g, Some(&[2, 1, 0])).unwrap();
60/// // All three are mutually adjacent, so 3 colors needed regardless of order
61/// let num_colors = *c.iter().max().unwrap() + 1;
62/// assert_eq!(num_colors, 3);
63/// ```
64pub fn greedy_coloring_with_order(graph: &Graph, order: Option<&[u32]>) -> IgraphResult<Vec<u32>> {
65    let n = graph.vcount() as usize;
66    if n == 0 {
67        return Ok(Vec::new());
68    }
69
70    if let Some(ord) = order {
71        if ord.len() != n {
72            return Err(IgraphError::InvalidArgument(
73                "greedy_coloring_with_order: order length must equal vertex count".into(),
74            ));
75        }
76    }
77
78    let mut colors = vec![u32::MAX; n];
79    let mut used = vec![false; n + 1];
80
81    for idx in 0..n {
82        let v = if let Some(ord) = order {
83            ord[idx] as usize
84        } else {
85            idx
86        };
87
88        let nbrs = neighbors_both(graph, v as u32)?;
89        for &u in &nbrs {
90            let ui = u as usize;
91            if colors[ui] != u32::MAX {
92                let c = colors[ui] as usize;
93                if c < used.len() {
94                    used[c] = true;
95                }
96            }
97        }
98
99        let mut c = 0_u32;
100        while (c as usize) < used.len() && used[c as usize] {
101            c = c.saturating_add(1);
102        }
103        colors[v] = c;
104
105        for &u in &nbrs {
106            let ui = u as usize;
107            if colors[ui] != u32::MAX {
108                let cu = colors[ui] as usize;
109                if cu < used.len() {
110                    used[cu] = false;
111                }
112            }
113        }
114    }
115
116    Ok(colors)
117}
118
119/// Greedy coloring with largest-first (LF) ordering.
120///
121/// Processes vertices in decreasing degree order (ties broken by
122/// vertex id). Often produces better colourings than natural order.
123///
124/// # Examples
125///
126/// ```
127/// use rust_igraph::{Graph, greedy_coloring_largest_first};
128///
129/// // Cycle C_5: chromatic number is 3
130/// let g = Graph::from_edges(
131///     &[(0,1),(1,2),(2,3),(3,4),(4,0)], false, Some(5)
132/// ).unwrap();
133/// let c = greedy_coloring_largest_first(&g).unwrap();
134/// let num_colors = *c.iter().max().unwrap() + 1;
135/// assert!(num_colors <= 3);
136/// ```
137pub fn greedy_coloring_largest_first(graph: &Graph) -> IgraphResult<Vec<u32>> {
138    let n = graph.vcount() as usize;
139    if n == 0 {
140        return Ok(Vec::new());
141    }
142
143    let mut deg_order: Vec<(usize, u32)> = (0..n)
144        .map(|v| {
145            let d = degree_both(graph, v as u32);
146            (d, v as u32)
147        })
148        .collect();
149    deg_order.sort_by(|a, b| b.0.cmp(&a.0).then(a.1.cmp(&b.1)));
150
151    let order: Vec<u32> = deg_order.iter().map(|&(_, v)| v).collect();
152    greedy_coloring_with_order(graph, Some(&order))
153}
154
155/// Count the number of colors used in a coloring.
156///
157/// # Examples
158///
159/// ```
160/// use rust_igraph::{Graph, greedy_coloring, chromatic_number_greedy};
161///
162/// let g = Graph::from_edges(&[(0,1),(1,2),(0,2)], false, Some(3)).unwrap();
163/// let c = greedy_coloring(&g).unwrap();
164/// assert_eq!(chromatic_number_greedy(&c), 3);
165/// ```
166pub fn chromatic_number_greedy(coloring: &[u32]) -> u32 {
167    if coloring.is_empty() {
168        return 0;
169    }
170    coloring.iter().max().map_or(0, |&m| m + 1)
171}
172
173/// Check whether a coloring is valid (proper).
174///
175/// A proper coloring assigns colours such that no two adjacent vertices
176/// share the same colour.
177///
178/// # Examples
179///
180/// ```
181/// use rust_igraph::{Graph, greedy_coloring, is_proper_coloring};
182///
183/// let g = Graph::from_edges(&[(0,1),(1,2)], false, Some(3)).unwrap();
184/// let c = greedy_coloring(&g).unwrap();
185/// assert!(is_proper_coloring(&g, &c).unwrap());
186/// ```
187pub fn is_proper_coloring(graph: &Graph, coloring: &[u32]) -> IgraphResult<bool> {
188    let n = graph.vcount() as usize;
189    if coloring.len() != n {
190        return Err(IgraphError::InvalidArgument(
191            "is_proper_coloring: coloring length must equal vertex count".into(),
192        ));
193    }
194
195    for (u, v) in graph.edges() {
196        let ui = u as usize;
197        let vi = v as usize;
198        if coloring[ui] == coloring[vi] {
199            return Ok(false);
200        }
201    }
202    Ok(true)
203}
204
205/// Compute the greedy clique number (lower bound on chromatic number).
206///
207/// Uses a greedy approach: iteratively pick an uncoloured vertex with
208/// the most uncoloured neighbours and add it to a clique if it's
209/// adjacent to all current clique members. This gives `ω(G) ≤ χ(G)`.
210///
211/// # Examples
212///
213/// ```
214/// use rust_igraph::{Graph, greedy_clique_number};
215///
216/// // K_4: clique number is 4
217/// let g = Graph::from_edges(
218///     &[(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)], false, Some(4)
219/// ).unwrap();
220/// assert_eq!(greedy_clique_number(&g).unwrap(), 4);
221/// ```
222pub fn greedy_clique_number(graph: &Graph) -> IgraphResult<u32> {
223    if graph.is_directed() {
224        return Err(IgraphError::InvalidArgument(
225            "greedy_clique_number is defined for undirected graphs only".into(),
226        ));
227    }
228
229    let n = graph.vcount() as usize;
230    if n == 0 {
231        return Ok(0);
232    }
233
234    let adj = build_adj_set(graph);
235
236    let mut best_clique = 0_u32;
237    let mut used = vec![false; n];
238
239    for _ in 0..n {
240        let mut clique: Vec<u32> = Vec::new();
241        let mut candidates: Vec<u32> = (0..n as u32).filter(|&v| !used[v as usize]).collect();
242
243        while !candidates.is_empty() {
244            let mut scored: Vec<(usize, u32)> = candidates
245                .iter()
246                .map(|&v| {
247                    let d = candidates
248                        .iter()
249                        .filter(|&&c| c != v && is_adj(&adj, n, v, c))
250                        .count();
251                    (d, v)
252                })
253                .collect();
254            scored.sort_by(|a, b| b.0.cmp(&a.0).then(a.1.cmp(&b.1)));
255
256            let v = scored[0].1;
257            clique.push(v);
258            candidates.retain(|&c| c != v && is_adj(&adj, n, v, c));
259        }
260
261        if clique.len() as u32 > best_clique {
262            best_clique = clique.len() as u32;
263        }
264
265        if let Some(&first) = clique.first() {
266            used[first as usize] = true;
267        } else {
268            break;
269        }
270    }
271
272    Ok(best_clique)
273}
274
275fn build_adj_set(graph: &Graph) -> Vec<bool> {
276    let n = graph.vcount() as usize;
277    let mut adj = vec![false; n * n];
278    for (u, v) in graph.edges() {
279        let ui = u as usize;
280        let vi = v as usize;
281        adj[ui * n + vi] = true;
282        adj[vi * n + ui] = true;
283    }
284    adj
285}
286
287fn is_adj(adj: &[bool], n: usize, u: u32, v: u32) -> bool {
288    adj[u as usize * n + v as usize]
289}
290
291fn neighbors_both(graph: &Graph, v: u32) -> IgraphResult<Vec<u32>> {
292    if graph.is_directed() {
293        let mut nbrs = graph.neighbors(v)?;
294        if let Ok(in_nbrs) = graph.in_neighbors_vec(v) {
295            for u in in_nbrs {
296                if !nbrs.contains(&u) {
297                    nbrs.push(u);
298                }
299            }
300        }
301        Ok(nbrs)
302    } else {
303        graph.neighbors(v)
304    }
305}
306
307fn degree_both(graph: &Graph, v: u32) -> usize {
308    neighbors_both(graph, v).map_or(0, |n| n.len())
309}
310
311#[cfg(test)]
312mod tests {
313    use super::*;
314
315    fn path3() -> Graph {
316        Graph::from_edges(&[(0, 1), (1, 2)], false, Some(3)).unwrap()
317    }
318
319    fn k3() -> Graph {
320        Graph::from_edges(&[(0, 1), (1, 2), (0, 2)], false, Some(3)).unwrap()
321    }
322
323    fn k4() -> Graph {
324        Graph::from_edges(
325            &[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)],
326            false,
327            Some(4),
328        )
329        .unwrap()
330    }
331
332    fn cycle5() -> Graph {
333        Graph::from_edges(&[(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)], false, Some(5)).unwrap()
334    }
335
336    fn star4() -> Graph {
337        Graph::from_edges(&[(0, 1), (0, 2), (0, 3)], false, Some(4)).unwrap()
338    }
339
340    fn petersen() -> Graph {
341        Graph::from_edges(
342            &[
343                (0, 1),
344                (1, 2),
345                (2, 3),
346                (3, 4),
347                (4, 0),
348                (0, 5),
349                (1, 6),
350                (2, 7),
351                (3, 8),
352                (4, 9),
353                (5, 7),
354                (7, 9),
355                (9, 6),
356                (6, 8),
357                (8, 5),
358            ],
359            false,
360            Some(10),
361        )
362        .unwrap()
363    }
364
365    fn bipartite_k23() -> Graph {
366        Graph::from_edges(
367            &[(0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4)],
368            false,
369            Some(5),
370        )
371        .unwrap()
372    }
373
374    // --- greedy_coloring ---
375
376    #[test]
377    fn gc_empty() {
378        let g = Graph::with_vertices(0);
379        let c = greedy_coloring(&g).unwrap();
380        assert!(c.is_empty());
381    }
382
383    #[test]
384    fn gc_single() {
385        let g = Graph::with_vertices(1);
386        let c = greedy_coloring(&g).unwrap();
387        assert_eq!(c, vec![0]);
388    }
389
390    #[test]
391    fn gc_isolated() {
392        let g = Graph::with_vertices(5);
393        let c = greedy_coloring(&g).unwrap();
394        assert_eq!(c, vec![0, 0, 0, 0, 0]);
395    }
396
397    #[test]
398    fn gc_path3() {
399        let g = path3();
400        let c = greedy_coloring(&g).unwrap();
401        assert_eq!(c, vec![0, 1, 0]);
402        assert!(is_proper_coloring(&g, &c).unwrap());
403    }
404
405    #[test]
406    fn gc_k3() {
407        let g = k3();
408        let c = greedy_coloring(&g).unwrap();
409        assert_eq!(chromatic_number_greedy(&c), 3);
410        assert!(is_proper_coloring(&g, &c).unwrap());
411    }
412
413    #[test]
414    fn gc_k4() {
415        let g = k4();
416        let c = greedy_coloring(&g).unwrap();
417        assert_eq!(chromatic_number_greedy(&c), 4);
418        assert!(is_proper_coloring(&g, &c).unwrap());
419    }
420
421    #[test]
422    fn gc_bipartite() {
423        let g = bipartite_k23();
424        let c = greedy_coloring(&g).unwrap();
425        assert!(chromatic_number_greedy(&c) <= 3);
426        assert!(is_proper_coloring(&g, &c).unwrap());
427    }
428
429    #[test]
430    fn gc_star() {
431        let g = star4();
432        let c = greedy_coloring(&g).unwrap();
433        assert_eq!(chromatic_number_greedy(&c), 2);
434        assert!(is_proper_coloring(&g, &c).unwrap());
435    }
436
437    // --- greedy_coloring_largest_first ---
438
439    #[test]
440    fn gclf_k3() {
441        let g = k3();
442        let c = greedy_coloring_largest_first(&g).unwrap();
443        assert_eq!(chromatic_number_greedy(&c), 3);
444        assert!(is_proper_coloring(&g, &c).unwrap());
445    }
446
447    #[test]
448    fn gclf_cycle5() {
449        let g = cycle5();
450        let c = greedy_coloring_largest_first(&g).unwrap();
451        assert!(chromatic_number_greedy(&c) <= 3);
452        assert!(is_proper_coloring(&g, &c).unwrap());
453    }
454
455    #[test]
456    fn gclf_bipartite() {
457        let g = bipartite_k23();
458        let c = greedy_coloring_largest_first(&g).unwrap();
459        assert_eq!(chromatic_number_greedy(&c), 2);
460        assert!(is_proper_coloring(&g, &c).unwrap());
461    }
462
463    #[test]
464    fn gclf_petersen() {
465        let g = petersen();
466        let c = greedy_coloring_largest_first(&g).unwrap();
467        // Petersen graph: χ = 3; greedy LF should use ≤ 4
468        assert!(chromatic_number_greedy(&c) <= 4);
469        assert!(is_proper_coloring(&g, &c).unwrap());
470    }
471
472    // --- greedy_coloring_with_order ---
473
474    #[test]
475    fn gcwo_custom_order() {
476        let g = path3();
477        let c = greedy_coloring_with_order(&g, Some(&[2, 0, 1])).unwrap();
478        assert!(is_proper_coloring(&g, &c).unwrap());
479        assert_eq!(chromatic_number_greedy(&c), 2);
480    }
481
482    #[test]
483    fn gcwo_wrong_length() {
484        let g = path3();
485        assert!(greedy_coloring_with_order(&g, Some(&[0, 1])).is_err());
486    }
487
488    // --- chromatic_number_greedy ---
489
490    #[test]
491    fn cng_empty() {
492        assert_eq!(chromatic_number_greedy(&[]), 0);
493    }
494
495    #[test]
496    fn cng_single() {
497        assert_eq!(chromatic_number_greedy(&[0]), 1);
498    }
499
500    // --- is_proper_coloring ---
501
502    #[test]
503    fn ipc_valid() {
504        let g = k3();
505        assert!(is_proper_coloring(&g, &[0, 1, 2]).unwrap());
506    }
507
508    #[test]
509    fn ipc_invalid() {
510        let g = k3();
511        assert!(!is_proper_coloring(&g, &[0, 1, 0]).unwrap());
512    }
513
514    #[test]
515    fn ipc_wrong_length() {
516        let g = k3();
517        assert!(is_proper_coloring(&g, &[0, 1]).is_err());
518    }
519
520    // --- greedy_clique_number ---
521
522    #[test]
523    fn gcn_empty() {
524        let g = Graph::with_vertices(0);
525        assert_eq!(greedy_clique_number(&g).unwrap(), 0);
526    }
527
528    #[test]
529    fn gcn_single() {
530        let g = Graph::with_vertices(1);
531        assert_eq!(greedy_clique_number(&g).unwrap(), 1);
532    }
533
534    #[test]
535    fn gcn_k4() {
536        let g = k4();
537        assert_eq!(greedy_clique_number(&g).unwrap(), 4);
538    }
539
540    #[test]
541    fn gcn_cycle5() {
542        let g = cycle5();
543        let cn = greedy_clique_number(&g).unwrap();
544        assert_eq!(cn, 2);
545    }
546
547    #[test]
548    fn gcn_petersen() {
549        let g = petersen();
550        let cn = greedy_clique_number(&g).unwrap();
551        assert_eq!(cn, 2);
552    }
553
554    #[test]
555    fn gcn_directed_error() {
556        let g = Graph::from_edges(&[(0, 1)], true, Some(2)).unwrap();
557        assert!(greedy_clique_number(&g).is_err());
558    }
559
560    // --- cross-consistency ---
561
562    #[test]
563    fn coloring_always_proper() {
564        for g in &[path3(), k3(), k4(), cycle5(), star4(), petersen()] {
565            let c = greedy_coloring(g).unwrap();
566            assert!(is_proper_coloring(g, &c).unwrap());
567        }
568    }
569
570    #[test]
571    fn lf_never_worse_than_max_degree_plus_one() {
572        for g in &[path3(), k3(), k4(), cycle5(), star4(), petersen()] {
573            let c = greedy_coloring_largest_first(g).unwrap();
574            let num_colors = chromatic_number_greedy(&c);
575            let max_deg = (0..g.vcount())
576                .map(|v| degree_both(g, v) as u32)
577                .max()
578                .unwrap_or(0);
579            assert!(
580                num_colors <= max_deg + 1,
581                "greedy LF used {num_colors} colors but Δ+1 = {}",
582                max_deg + 1
583            );
584        }
585    }
586
587    #[test]
588    fn clique_bound_vs_coloring() {
589        for g in &[k3(), k4(), cycle5(), petersen()] {
590            let cn = greedy_clique_number(g).unwrap();
591            let c = greedy_coloring_largest_first(g).unwrap();
592            let chi = chromatic_number_greedy(&c);
593            assert!(cn <= chi, "clique number {cn} > chromatic bound {chi}");
594        }
595    }
596
597    // --- directed graph coloring ---
598
599    #[test]
600    fn gc_directed() {
601        let g = Graph::from_edges(&[(0, 1), (1, 2), (2, 0)], true, Some(3)).unwrap();
602        let c = greedy_coloring(&g).unwrap();
603        assert_eq!(chromatic_number_greedy(&c), 3);
604        assert!(is_proper_coloring(&g, &c).unwrap());
605    }
606}
rust_igraph/algorithms/properties/graph_coloring.rs

rust_igraph/algorithms/properties/
graph_coloring.rs
