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::{CreateSpec, ProblemSchemaEntry, VariantDimension};
7use crate::topology::{Graph, SimpleGraph};
8use crate::traits::Problem;
9use crate::variant::{KValue, VariantParam, K1, 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", "K1", "K2", "K3", "K4", "K5"]),
20        ],
21        category: crate::registry::ProblemCategory::Graph,
22        module_path: module_path!(),
23        description: "Find valid k-coloring of a graph",
24        fields: RuntimeKColoringCreateSpec::FIELDS,
25    }
26}
27
28/// The Graph K-Coloring problem.
29///
30/// Given a graph G = (V, E) and K colors, find an assignment of colors
31/// to vertices such that no two adjacent vertices have the same color.
32///
33/// # Type Parameters
34///
35/// * `K` - KValue type representing the number of colors (e.g., K3 for 3-coloring)
36/// * `G` - Graph type (e.g., SimpleGraph, KingsSubgraph)
37///
38/// # Example
39///
40/// ```
41/// use problemreductions::models::graph::KColoring;
42/// use problemreductions::topology::SimpleGraph;
43/// use problemreductions::variant::K3;
44/// use problemreductions::{Problem, BruteForce};
45///
46/// // Triangle graph needs at least 3 colors
47/// let graph = SimpleGraph::new(3, vec![(0, 1), (1, 2), (0, 2)]);
48/// let problem = KColoring::<K3, _>::new(graph);
49///
50/// let solver = BruteForce::new();
51/// let solutions = solver.find_all_witnesses(&problem).unwrap();
52///
53/// // Verify all solutions are valid colorings
54/// for sol in &solutions {
55///     assert!(problem.evaluate(sol).unwrap());
56/// }
57/// ```
58#[derive(Debug, Clone, Serialize, Deserialize)]
59#[serde(bound(deserialize = "G: serde::Deserialize<'de>"))]
60pub struct KColoring<K: KValue, G> {
61    /// The underlying graph.
62    graph: G,
63    /// Runtime number of colors. Always set; for compile-time K types it equals K::K.
64    #[serde(
65        default = "default_num_colors::<K>",
66        deserialize_with = "deserialize_num_colors::<K, _>"
67    )]
68    num_colors: usize,
69    #[serde(skip)]
70    _phantom: std::marker::PhantomData<K>,
71}
72
73#[derive(Debug, Deserialize, crate::CreateSpec)]
74struct FixedKColoringCreateSpec {
75    /// Undirected graph edges.
76    #[create(codec = "edge-list")]
77    graph: Vec<(usize, usize)>,
78    /// Vertex count, needed to preserve isolated vertices.
79    num_vertices: Option<usize>,
80}
81
82#[derive(Debug, Deserialize, crate::CreateSpec)]
83struct RuntimeKColoringCreateSpec {
84    /// Undirected graph edges.
85    #[create(codec = "edge-list")]
86    graph: Vec<(usize, usize)>,
87    /// Vertex count, needed to preserve isolated vertices.
88    num_vertices: Option<usize>,
89    /// Runtime color count.
90    k: usize,
91}
92
93fn simple_graph_from_create(
94    edges: Vec<(usize, usize)>,
95    num_vertices: Option<usize>,
96) -> Result<SimpleGraph, crate::registry::ConstructionError> {
97    if edges.is_empty() && num_vertices.is_none() {
98        return Err("num_vertices is required for an empty graph"
99            .to_string()
100            .into());
101    }
102    for (index, &(u, v)) in edges.iter().enumerate() {
103        if u == v {
104            return Err(format!("graph edge {index} is a self-loop at vertex {u}").into());
105        }
106    }
107    let inferred = edges
108        .iter()
109        .flat_map(|&(u, v)| [u, v])
110        .max()
111        .map(|vertex| vertex.checked_add(1).ok_or("vertex count overflows usize"))
112        .transpose()?
113        .unwrap_or(0);
114    let count = num_vertices.unwrap_or(inferred);
115    if count < inferred {
116        return Err(format!(
117            "num_vertices {count} is too small for graph endpoints; need at least {inferred}"
118        )
119        .into());
120    }
121    Ok(SimpleGraph::new(count, edges))
122}
123
124impl<K: KValue> TryFrom<FixedKColoringCreateSpec> for KColoring<K, SimpleGraph> {
125    type Error = crate::registry::ConstructionError;
126
127    fn try_from(spec: FixedKColoringCreateSpec) -> Result<Self, Self::Error> {
128        let num_colors = K::K.ok_or("runtime KColoring requires k")?;
129        Ok(Self {
130            graph: simple_graph_from_create(spec.graph, spec.num_vertices)?,
131            num_colors,
132            _phantom: std::marker::PhantomData,
133        })
134    }
135}
136
137impl TryFrom<RuntimeKColoringCreateSpec> for KColoring<KN, SimpleGraph> {
138    type Error = crate::registry::ConstructionError;
139
140    fn try_from(spec: RuntimeKColoringCreateSpec) -> Result<Self, Self::Error> {
141        if spec.k == 0 {
142            return Err("k must be positive".to_string().into());
143        }
144        Ok(Self::with_k(
145            simple_graph_from_create(spec.graph, spec.num_vertices)?,
146            spec.k,
147        ))
148    }
149}
150
151// Fixed-K construction and persisted instances must describe the same problem.
152fn deserialize_num_colors<'de, K: KValue, D: serde::Deserializer<'de>>(
153    deserializer: D,
154) -> Result<usize, D::Error> {
155    let num_colors = usize::deserialize(deserializer)?;
156    match K::K {
157        Some(fixed) if num_colors != fixed => Err(serde::de::Error::custom(format!(
158            "fixed K requires {fixed} colors, got {num_colors}"
159        ))),
160        _ => Ok(num_colors),
161    }
162}
163
164fn default_num_colors<K: KValue>() -> usize {
165    K::K.unwrap_or(0)
166}
167
168impl<K: KValue, G: Graph> KColoring<K, G> {
169    /// Create a new K-Coloring problem from a graph.
170    ///
171    /// # Panics
172    /// Panics if `K` is `KN` (use [`KColoring::<KN, G>::with_k`] instead).
173    pub fn new(graph: G) -> Self {
174        Self {
175            graph,
176            num_colors: K::K.expect("KN requires with_k"),
177            _phantom: std::marker::PhantomData,
178        }
179    }
180
181    /// Get a reference to the underlying graph.
182    pub fn graph(&self) -> &G {
183        &self.graph
184    }
185
186    /// Get the number of colors.
187    pub fn num_colors(&self) -> usize {
188        self.num_colors
189    }
190
191    /// Check if a configuration is a valid coloring.
192    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
193        is_valid_coloring(&self.graph, config, self.num_colors)
194    }
195
196    /// Check if a coloring is valid.
197    fn is_valid_coloring(&self, config: &[usize]) -> bool {
198        for (u, v) in self.graph.edges() {
199            let color_u = config.get(u).copied().unwrap_or(0);
200            let color_v = config.get(v).copied().unwrap_or(0);
201            if color_u == color_v {
202                return false;
203            }
204        }
205        true
206    }
207}
208
209impl<G: Graph> KColoring<KN, G> {
210    /// Create a K-Coloring problem with an explicit number of colors.
211    ///
212    /// Only available for `KN` (runtime K). For compile-time K types like
213    /// `K3`, use [`new`](KColoring::new) which derives K from the type
214    /// parameter.
215    pub fn with_k(graph: G, num_colors: usize) -> Self {
216        Self {
217            graph,
218            num_colors,
219            _phantom: std::marker::PhantomData,
220        }
221    }
222}
223
224impl<K: KValue, G: Graph> KColoring<K, G> {
225    /// Get the number of vertices in the underlying graph.
226    pub fn num_vertices(&self) -> usize {
227        self.graph().num_vertices()
228    }
229
230    /// Get the number of edges in the underlying graph.
231    pub fn num_edges(&self) -> usize {
232        self.graph().num_edges()
233    }
234}
235
236impl<K: KValue, G> Problem for KColoring<K, G>
237where
238    G: Graph + VariantParam,
239{
240    const NAME: &'static str = "KColoring";
241    type Solution = Vec<usize>;
242    type Value = crate::types::Or;
243
244    crate::problem_parameters![
245        ("num_edges", num_edges),
246        ("num_vertices", num_vertices),
247        ("num_colors", num_colors),
248    ];
249
250    fn variant() -> Vec<(&'static str, &'static str)> {
251        crate::variant_params![K, G]
252    }
253
254    fn evaluate(
255        &self,
256        config: &Self::Solution,
257    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
258        if config.len() != self.graph.num_vertices() {
259            return Err(crate::traits::EvaluationError::InvalidConfiguration(
260                "color assignment length does not match the graph vertices".into(),
261            ));
262        }
263        if config.iter().any(|&color| color >= self.num_colors) {
264            return Err(crate::traits::EvaluationError::InvalidConfiguration(
265                "color assignment contains an out-of-range color".into(),
266            ));
267        }
268        Ok(crate::types::Or(self.is_valid_coloring(config)))
269    }
270}
271
272impl<K: KValue, G> crate::solvers::BruteForceProblem for KColoring<K, G>
273where
274    G: Graph + VariantParam,
275{
276    fn dimensions(&self) -> Vec<usize> {
277        vec![self.num_colors; self.graph.num_vertices()]
278    }
279}
280
281/// Check if a coloring is valid for a graph.
282///
283/// # Panics
284/// Panics if `coloring.len() != graph.num_vertices()`.
285pub(crate) fn is_valid_coloring<G: Graph>(
286    graph: &G,
287    coloring: &[usize],
288    num_colors: usize,
289) -> bool {
290    assert_eq!(
291        coloring.len(),
292        graph.num_vertices(),
293        "coloring length must match num_vertices"
294    );
295    // Check all colors are valid
296    if coloring.iter().any(|&c| c >= num_colors) {
297        return false;
298    }
299    // Check no adjacent vertices have same color
300    for (u, v) in graph.edges() {
301        if coloring[u] == coloring[v] {
302            return false;
303        }
304    }
305    true
306}
307
308#[cfg(feature = "example-db")]
309pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
310    vec![crate::example_db::specs::ModelExampleSpec {
311        id: "kcoloring_k3_simplegraph",
312        instance: Box::new(KColoring::<K3, _>::new(SimpleGraph::new(
313            5,
314            vec![(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 4)],
315        ))),
316        optimal_config: serde_json::json!(vec![0, 1, 1, 0, 2]),
317        optimal_value: serde_json::json!(true),
318    }]
319}
320
321crate::impl_random_generate!(KColoring<KN, SimpleGraph>, crate::random::ColoringRandomSpec, |spec| {
322    let k = spec.k.unwrap_or(3);
323    if k == 0 {
324        return Err("k must be positive".to_string().into());
325    }
326    Ok(KColoring::with_k(spec.graph()?, k))
327});
328crate::impl_random_generate!(KColoring<K2, SimpleGraph>, crate::random::ColoringRandomSpec, |spec| {
329    if spec.k.is_some_and(|k| k != 2) { return Err("k must match the selected K2 variant".to_string().into()); }
330    Ok(KColoring::new(spec.graph()?))
331});
332crate::impl_random_generate!(KColoring<K3, SimpleGraph>, crate::random::ColoringRandomSpec, |spec| {
333    if spec.k.is_some_and(|k| k != 3) { return Err("k must match the selected K3 variant".to_string().into()); }
334    Ok(KColoring::new(spec.graph()?))
335});
336crate::impl_random_generate!(KColoring<K4, SimpleGraph>, crate::random::ColoringRandomSpec, |spec| {
337    if spec.k.is_some_and(|k| k != 4) { return Err("k must match the selected K4 variant".to_string().into()); }
338    Ok(KColoring::new(spec.graph()?))
339});
340crate::impl_random_generate!(KColoring<K5, SimpleGraph>, crate::random::ColoringRandomSpec, |spec| {
341    if spec.k.is_some_and(|k| k != 5) { return Err("k must match the selected K5 variant".to_string().into()); }
342    Ok(KColoring::new(spec.graph()?))
343});
344
345crate::declare_variants! {
346    default KColoring<KN, SimpleGraph> => "2^num_vertices" create RuntimeKColoringCreateSpec random,
347    KColoring<K1, SimpleGraph> => "num_vertices + num_edges" create FixedKColoringCreateSpec,
348    KColoring<K2, SimpleGraph> => "num_vertices + num_edges" create FixedKColoringCreateSpec random,
349    KColoring<K3, SimpleGraph> => "1.3289^num_vertices" create FixedKColoringCreateSpec random,
350    KColoring<K4, SimpleGraph> => "1.7159^num_vertices" create FixedKColoringCreateSpec random,
351    // Best known: O*((2-ε)^n) for some ε > 0 (Zamir 2021), concrete ε unknown
352    KColoring<K5, SimpleGraph> => "2^num_vertices" create FixedKColoringCreateSpec random,
353}
354
355crate::register_brute_force! {
356    KColoring<KN, SimpleGraph>,
357    KColoring<K1, SimpleGraph>,
358    KColoring<K2, SimpleGraph>,
359    KColoring<K3, SimpleGraph>,
360    KColoring<K4, SimpleGraph>,
361    KColoring<K5, SimpleGraph>,
362}
363
364#[cfg(test)]
365#[path = "../../unit_tests/models/graph/kcoloring.rs"]
366mod tests;
problemreductions/models/graph/kcoloring.rs

problemreductions/models/graph/
kcoloring.rs
