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, K2, K3, 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"]),
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        Ok(Self::with_k(
142            simple_graph_from_create(spec.graph, spec.num_vertices)?,
143            spec.k,
144        ))
145    }
146}
147
148// Fixed-K construction and persisted instances must describe the same problem.
149fn deserialize_num_colors<'de, K: KValue, D: serde::Deserializer<'de>>(
150    deserializer: D,
151) -> Result<usize, D::Error> {
152    let num_colors = usize::deserialize(deserializer)?;
153    match K::K {
154        Some(fixed) if num_colors != fixed => Err(serde::de::Error::custom(format!(
155            "fixed K requires {fixed} colors, got {num_colors}"
156        ))),
157        _ => Ok(num_colors),
158    }
159}
160
161fn default_num_colors<K: KValue>() -> usize {
162    K::K.unwrap_or(0)
163}
164
165impl<K: KValue, G: Graph> KColoring<K, G> {
166    /// Create a new K-Coloring problem from a graph.
167    ///
168    /// # Panics
169    /// Panics if `K` is `KN` (use [`KColoring::<KN, G>::with_k`] instead).
170    pub fn new(graph: G) -> Self {
171        Self {
172            graph,
173            num_colors: K::K.expect("KN requires with_k"),
174            _phantom: std::marker::PhantomData,
175        }
176    }
177
178    /// Get a reference to the underlying graph.
179    pub fn graph(&self) -> &G {
180        &self.graph
181    }
182
183    /// Get the number of colors.
184    pub fn num_colors(&self) -> usize {
185        self.num_colors
186    }
187
188    /// Check if a configuration is a valid coloring.
189    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
190        is_valid_coloring(&self.graph, config, self.num_colors)
191    }
192
193    /// Check if a coloring is valid.
194    fn is_valid_coloring(&self, config: &[usize]) -> bool {
195        for (u, v) in self.graph.edges() {
196            let color_u = config.get(u).copied().unwrap_or(0);
197            let color_v = config.get(v).copied().unwrap_or(0);
198            if color_u == color_v {
199                return false;
200            }
201        }
202        true
203    }
204}
205
206impl<G: Graph> KColoring<KN, G> {
207    /// Create a K-Coloring problem with an explicit number of colors.
208    ///
209    /// Only available for `KN` (runtime K). For compile-time K types like
210    /// `K3`, use [`new`](KColoring::new) which derives K from the type
211    /// parameter.
212    pub fn with_k(graph: G, num_colors: usize) -> Self {
213        Self {
214            graph,
215            num_colors,
216            _phantom: std::marker::PhantomData,
217        }
218    }
219}
220
221impl<K: KValue, G: Graph> KColoring<K, G> {
222    /// Get the number of vertices in the underlying graph.
223    pub fn num_vertices(&self) -> usize {
224        self.graph().num_vertices()
225    }
226
227    /// Get the number of edges in the underlying graph.
228    pub fn num_edges(&self) -> usize {
229        self.graph().num_edges()
230    }
231}
232
233impl<K: KValue, G> Problem for KColoring<K, G>
234where
235    G: Graph + VariantParam,
236{
237    const NAME: &'static str = "KColoring";
238    type Solution = Vec<usize>;
239    type Value = crate::types::Or;
240
241    crate::problem_parameters![
242        ("num_edges", num_edges),
243        ("num_vertices", num_vertices),
244        ("num_colors", num_colors),
245    ];
246
247    fn variant() -> Vec<(&'static str, &'static str)> {
248        crate::variant_params![K, G]
249    }
250
251    fn evaluate(
252        &self,
253        config: &Self::Solution,
254    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
255        if config.len() != self.graph.num_vertices() {
256            return Err(crate::traits::EvaluationError::InvalidConfiguration(
257                "color assignment length does not match the graph vertices".into(),
258            ));
259        }
260        if config.iter().any(|&color| color >= self.num_colors) {
261            return Err(crate::traits::EvaluationError::InvalidConfiguration(
262                "color assignment contains an out-of-range color".into(),
263            ));
264        }
265        Ok(crate::types::Or(self.is_valid_coloring(config)))
266    }
267}
268
269impl<K: KValue, G> crate::solvers::BruteForceProblem for KColoring<K, G>
270where
271    G: Graph + VariantParam,
272{
273    fn dimensions(&self) -> Vec<usize> {
274        vec![self.num_colors; self.graph.num_vertices()]
275    }
276}
277
278/// Check if a coloring is valid for a graph.
279///
280/// # Panics
281/// Panics if `coloring.len() != graph.num_vertices()`.
282pub(crate) fn is_valid_coloring<G: Graph>(
283    graph: &G,
284    coloring: &[usize],
285    num_colors: usize,
286) -> bool {
287    assert_eq!(
288        coloring.len(),
289        graph.num_vertices(),
290        "coloring length must match num_vertices"
291    );
292    // Check all colors are valid
293    if coloring.iter().any(|&c| c >= num_colors) {
294        return false;
295    }
296    // Check no adjacent vertices have same color
297    for (u, v) in graph.edges() {
298        if coloring[u] == coloring[v] {
299            return false;
300        }
301    }
302    true
303}
304
305#[cfg(feature = "example-db")]
306pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
307    vec![crate::example_db::specs::ModelExampleSpec {
308        id: "kcoloring_k3_simplegraph",
309        instance: Box::new(KColoring::<K3, _>::new(SimpleGraph::new(
310            5,
311            vec![(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 4)],
312        ))),
313        optimal_config: serde_json::json!(vec![0, 1, 1, 0, 2]),
314        optimal_value: serde_json::json!(true),
315    }]
316}
317
318crate::impl_random_generate!(KColoring<KN, SimpleGraph>, crate::random::ColoringRandomSpec, |spec| {
319    let k = spec.k.unwrap_or(3);
320    Ok(KColoring::with_k(spec.graph()?, k))
321});
322crate::impl_random_generate!(KColoring<K2, SimpleGraph>, crate::random::ColoringRandomSpec, |spec| {
323    if spec.k.is_some_and(|k| k != 2) { return Err("k must match the selected K2 variant".to_string().into()); }
324    Ok(KColoring::new(spec.graph()?))
325});
326crate::impl_random_generate!(KColoring<K3, SimpleGraph>, crate::random::ColoringRandomSpec, |spec| {
327    if spec.k.is_some_and(|k| k != 3) { return Err("k must match the selected K3 variant".to_string().into()); }
328    Ok(KColoring::new(spec.graph()?))
329});
330
331crate::declare_variants! {
332    default KColoring<KN, SimpleGraph> => "2^num_vertices" create RuntimeKColoringCreateSpec random,
333    KColoring<K2, SimpleGraph> => "num_vertices + num_edges" create FixedKColoringCreateSpec random,
334    KColoring<K3, SimpleGraph> => "1.3289^num_vertices" create FixedKColoringCreateSpec random,
335}
336
337crate::register_brute_force! {
338    KColoring<KN, SimpleGraph>,
339    KColoring<K2, SimpleGraph>,
340    KColoring<K3, SimpleGraph>,
341}
342
343#[cfg(test)]
344#[path = "../../unit_tests/models/graph/kcoloring.rs"]
345mod tests;
problemreductions/models/graph/kcoloring.rs

problemreductions/models/graph/
kcoloring.rs
