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

problemreductions/rules/
kcoloring_clustering.rs
