problemreductions/rules/
kcoloring_clustering.rs

1//! Reduction from 3-Coloring to Clustering.
2//!
3//! Adjacent vertices must land in different clusters, so we encode edges with
4//! distance 1 and non-edges with distance 0, then ask for 3 clusters with
5//! diameter bound 0.
6
7use crate::models::graph::KColoring;
8use crate::models::misc::Clustering;
9use crate::reduction;
10use crate::rules::traits::{ReduceTo, ReductionResult};
11use crate::topology::{Graph, SimpleGraph};
12use crate::variant::K3;
13
14/// Result of reducing KColoring (K=3) to Clustering.
15#[derive(Debug, Clone)]
16pub struct ReductionKColoringToClustering {
17    target: Clustering,
18    source_num_vertices: usize,
19}
20
21impl ReductionResult for ReductionKColoringToClustering {
22    type Source = KColoring<K3, SimpleGraph>;
23    type Target = Clustering;
24
25    fn target_problem(&self) -> &Self::Target {
26        &self.target
27    }
28
29    /// Cluster labels are color labels. The empty-graph corner case uses one
30    /// dummy target element because Clustering forbids empty instances.
31    fn extract_solution(
32        &self,
33        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
34    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
35        crate::rules::traits::validate_target_witness(
36            self.target_problem(),
37            target_solution,
38            |value| value.0,
39            "target witness is not satisfying",
40        )?;
41
42        Ok(target_solution[..self.source_num_vertices].to_vec())
43    }
44}
45
46fn build_distances(graph: &SimpleGraph) -> Vec<Vec<i64>> {
47    let n = graph.num_vertices();
48    if n == 0 {
49        return vec![vec![0]];
50    }
51
52    let mut distances = vec![vec![0; n]; n];
53    for (u, v) in graph.edges() {
54        distances[u][v] = 1;
55        distances[v][u] = 1;
56    }
57    distances
58}
59
60#[crate::aggregate_reduction(identity)]
61impl crate::rules::AggregateReductionResult for ReductionKColoringToClustering {}
62
63#[reduction(
64    transform = upper_bound {
65        num_elements = "num_vertices + 2",
66        num_clusters = "num_colors",
67    }
68)]
69impl ReduceTo<Clustering> for KColoring<K3, SimpleGraph> {
70    type Result = ReductionKColoringToClustering;
71
72    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
73        if self.graph().edges().iter().any(|&(u, v)| u == v) {
74            // A loop is uncolorable. Two separated elements cannot share one
75            // diameter-zero cluster; the target diagonal remains zero.
76            return Ok(ReductionKColoringToClustering {
77                target: Clustering::new(vec![vec![0, 1], vec![1, 0]], 1, 0),
78                source_num_vertices: self.graph().num_vertices(),
79            });
80        }
81        Ok(ReductionKColoringToClustering {
82            target: Clustering::new(build_distances(self.graph()), self.num_colors(), 0),
83            source_num_vertices: self.graph().num_vertices(),
84        })
85    }
86}
87
88#[cfg(feature = "example-db")]
89pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
90    use crate::export::SolutionPair;
91
92    vec![crate::example_db::specs::RuleExampleSpec {
93        id: "kcoloring_to_clustering",
94        build: || {
95            let source = KColoring::<K3, _>::new(SimpleGraph::cycle(5));
96            crate::example_db::specs::rule_example_with_witness::<_, Clustering>(
97                source,
98                SolutionPair {
99                    source_config: serde_json::json!(vec![0, 1, 0, 1, 2]),
100                    target_config: serde_json::json!(vec![0, 1, 0, 1, 2]),
101                },
102            )
103        },
104    }]
105}
106
107#[cfg(test)]
108#[path = "../unit_tests/rules/kcoloring_clustering.rs"]
109mod tests;
problemreductions/rules/kcoloring_clustering.rs

problemreductions/rules/
kcoloring_clustering.rs
