problemreductions/models/graph/
kcoloring.rs

1//! Graph K-Coloring problem implementation.
2//!
3//! The K-Coloring problem asks whether a graph can be colored with K colors
4//! such that no two adjacent vertices have the same color.
5
6use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
7use crate::topology::{Graph, SimpleGraph};
8use crate::traits::Problem;
9use crate::variant::{KValue, VariantParam, K2, K3, K4, K5, KN};
10use serde::{Deserialize, Serialize};
11
12inventory::submit! {
13    ProblemSchemaEntry {
14        name: "KColoring",
15        display_name: "K-Coloring",
16        aliases: &[],
17        dimensions: &[
18            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
19            VariantDimension::new("k", "KN", &["KN", "K2", "K3", "K4", "K5"]),
20        ],
21        module_path: module_path!(),
22        description: "Find valid k-coloring of a graph",
23        fields: &[
24            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
25        ],
26    }
27}
28
29/// The Graph K-Coloring problem.
30///
31/// Given a graph G = (V, E) and K colors, find an assignment of colors
32/// to vertices such that no two adjacent vertices have the same color.
33///
34/// # Type Parameters
35///
36/// * `K` - KValue type representing the number of colors (e.g., K3 for 3-coloring)
37/// * `G` - Graph type (e.g., SimpleGraph, KingsSubgraph)
38///
39/// # Example
40///
41/// ```
42/// use problemreductions::models::graph::KColoring;
43/// use problemreductions::topology::SimpleGraph;
44/// use problemreductions::variant::K3;
45/// use problemreductions::{Problem, Solver, BruteForce};
46///
47/// // Triangle graph needs at least 3 colors
48/// let graph = SimpleGraph::new(3, vec![(0, 1), (1, 2), (0, 2)]);
49/// let problem = KColoring::<K3, _>::new(graph);
50///
51/// let solver = BruteForce::new();
52/// let solutions = solver.find_all_witnesses(&problem);
53///
54/// // Verify all solutions are valid colorings
55/// for sol in &solutions {
56///     assert!(problem.evaluate(sol));
57/// }
58/// ```
59#[derive(Debug, Clone, Serialize, Deserialize)]
60#[serde(bound(deserialize = "G: serde::Deserialize<'de>"))]
61pub struct KColoring<K: KValue, G> {
62    /// The underlying graph.
63    graph: G,
64    /// Runtime number of colors. Always set; for compile-time K types it equals K::K.
65    #[serde(default = "default_num_colors::<K>")]
66    num_colors: usize,
67    #[serde(skip)]
68    _phantom: std::marker::PhantomData<K>,
69}
70
71fn default_num_colors<K: KValue>() -> usize {
72    K::K.unwrap_or(0)
73}
74
75impl<K: KValue, G: Graph> KColoring<K, G> {
76    /// Create a new K-Coloring problem from a graph.
77    ///
78    /// # Panics
79    /// Panics if `K` is `KN` (use [`KColoring::<KN, G>::with_k`] instead).
80    pub fn new(graph: G) -> Self {
81        Self {
82            graph,
83            num_colors: K::K.expect("KN requires with_k"),
84            _phantom: std::marker::PhantomData,
85        }
86    }
87
88    /// Get a reference to the underlying graph.
89    pub fn graph(&self) -> &G {
90        &self.graph
91    }
92
93    /// Get the number of colors.
94    pub fn num_colors(&self) -> usize {
95        self.num_colors
96    }
97
98    /// Check if a configuration is a valid coloring.
99    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
100        is_valid_coloring(&self.graph, config, self.num_colors)
101    }
102
103    /// Check if a coloring is valid.
104    fn is_valid_coloring(&self, config: &[usize]) -> bool {
105        for (u, v) in self.graph.edges() {
106            let color_u = config.get(u).copied().unwrap_or(0);
107            let color_v = config.get(v).copied().unwrap_or(0);
108            if color_u == color_v {
109                return false;
110            }
111        }
112        true
113    }
114}
115
116impl<G: Graph> KColoring<KN, G> {
117    /// Create a K-Coloring problem with an explicit number of colors.
118    ///
119    /// Only available for `KN` (runtime K). For compile-time K types like
120    /// `K3`, use [`new`](KColoring::new) which derives K from the type
121    /// parameter.
122    pub fn with_k(graph: G, num_colors: usize) -> Self {
123        Self {
124            graph,
125            num_colors,
126            _phantom: std::marker::PhantomData,
127        }
128    }
129}
130
131impl<K: KValue, G: Graph> KColoring<K, G> {
132    /// Get the number of vertices in the underlying graph.
133    pub fn num_vertices(&self) -> usize {
134        self.graph().num_vertices()
135    }
136
137    /// Get the number of edges in the underlying graph.
138    pub fn num_edges(&self) -> usize {
139        self.graph().num_edges()
140    }
141}
142
143impl<K: KValue, G> Problem for KColoring<K, G>
144where
145    G: Graph + VariantParam,
146{
147    const NAME: &'static str = "KColoring";
148    type Value = crate::types::Or;
149
150    fn variant() -> Vec<(&'static str, &'static str)> {
151        crate::variant_params![K, G]
152    }
153
154    fn dims(&self) -> Vec<usize> {
155        vec![self.num_colors; self.graph.num_vertices()]
156    }
157
158    fn evaluate(&self, config: &[usize]) -> crate::types::Or {
159        crate::types::Or(self.is_valid_coloring(config))
160    }
161}
162
163/// Check if a coloring is valid for a graph.
164///
165/// # Panics
166/// Panics if `coloring.len() != graph.num_vertices()`.
167pub(crate) fn is_valid_coloring<G: Graph>(
168    graph: &G,
169    coloring: &[usize],
170    num_colors: usize,
171) -> bool {
172    assert_eq!(
173        coloring.len(),
174        graph.num_vertices(),
175        "coloring length must match num_vertices"
176    );
177    // Check all colors are valid
178    if coloring.iter().any(|&c| c >= num_colors) {
179        return false;
180    }
181    // Check no adjacent vertices have same color
182    for (u, v) in graph.edges() {
183        if coloring[u] == coloring[v] {
184            return false;
185        }
186    }
187    true
188}
189
190#[cfg(feature = "example-db")]
191pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
192    vec![crate::example_db::specs::ModelExampleSpec {
193        id: "kcoloring_k3_simplegraph",
194        instance: Box::new(KColoring::<K3, _>::new(SimpleGraph::new(
195            5,
196            vec![(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 4)],
197        ))),
198        optimal_config: vec![0, 1, 1, 0, 2],
199        optimal_value: serde_json::json!(true),
200    }]
201}
202
203crate::declare_variants! {
204    default KColoring<KN, SimpleGraph> => "2^num_vertices",
205    KColoring<K2, SimpleGraph> => "num_vertices + num_edges",
206    KColoring<K3, SimpleGraph> => "1.3289^num_vertices",
207    KColoring<K4, SimpleGraph> => "1.7159^num_vertices",
208    // Best known: O*((2-ε)^n) for some ε > 0 (Zamir 2021), concrete ε unknown
209    KColoring<K5, SimpleGraph> => "2^num_vertices",
210}
211
212#[cfg(test)]
213#[path = "../../unit_tests/models/graph/kcoloring.rs"]
214mod tests;
problemreductions/models/graph/kcoloring.rs

problemreductions/models/graph/
kcoloring.rs
