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(&self, target_solution: &[usize]) -> Vec<usize> {
32        target_solution[..self.source_num_vertices.min(target_solution.len())].to_vec()
33    }
34}
35
36fn build_distances(graph: &SimpleGraph) -> Vec<Vec<u64>> {
37    let n = graph.num_vertices();
38    if n == 0 {
39        return vec![vec![0]];
40    }
41
42    let mut distances = vec![vec![0; n]; n];
43    for (u, v) in graph.edges() {
44        distances[u][v] = 1;
45        distances[v][u] = 1;
46    }
47    distances
48}
49
50#[reduction(overhead = {
51    num_elements = "num_vertices",
52})]
53impl ReduceTo<Clustering> for KColoring<K3, SimpleGraph> {
54    type Result = ReductionKColoringToClustering;
55
56    fn reduce_to(&self) -> Self::Result {
57        ReductionKColoringToClustering {
58            target: Clustering::new(build_distances(self.graph()), self.num_colors(), 0),
59            source_num_vertices: self.graph().num_vertices(),
60        }
61    }
62}
63
64#[cfg(feature = "example-db")]
65pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
66    use crate::export::SolutionPair;
67
68    vec![crate::example_db::specs::RuleExampleSpec {
69        id: "kcoloring_to_clustering",
70        build: || {
71            let source = KColoring::<K3, _>::new(SimpleGraph::cycle(5));
72            crate::example_db::specs::rule_example_with_witness::<_, Clustering>(
73                source,
74                SolutionPair {
75                    source_config: vec![0, 1, 0, 1, 2],
76                    target_config: vec![0, 1, 0, 1, 2],
77                },
78            )
79        },
80    }]
81}
82
83#[cfg(test)]
84#[path = "../unit_tests/rules/kcoloring_clustering.rs"]
85mod tests;
problemreductions/rules/kcoloring_clustering.rs

problemreductions/rules/
kcoloring_clustering.rs
