problemreductions/models/misc/
clustering.rs

1//! Clustering problem implementation.
2//!
3//! Given a distance matrix over n elements, a cluster count bound K,
4//! and a diameter bound B, determine whether the elements can be partitioned
5//! into at most K non-empty clusters such that all intra-cluster pairwise
6//! distances are at most B.
7
8use crate::registry::{FieldInfo, ProblemSchemaEntry};
9use crate::traits::Problem;
10use serde::{Deserialize, Serialize};
11
12inventory::submit! {
13    ProblemSchemaEntry {
14        name: "Clustering",
15        display_name: "Clustering",
16        aliases: &[],
17        dimensions: &[],
18        category: crate::registry::ProblemCategory::Misc,
19        module_path: module_path!(),
20        description: "Partition elements into at most K clusters where all intra-cluster distances are at most B",
21        fields: &[
22            FieldInfo { name: "distances", type_name: "Vec<Vec<i64>>", description: "Symmetric distance matrix with zero diagonal" },
23            FieldInfo { name: "num_clusters", type_name: "usize", description: "Maximum number of clusters K" },
24            FieldInfo { name: "diameter_bound", type_name: "i64", description: "Maximum allowed intra-cluster pairwise distance B" },
25        ],
26    }
27}
28
29/// The Clustering problem.
30///
31/// Given a set of `n` elements with pairwise distances, a cluster count
32/// bound `K`, and a diameter bound `B`, determine whether there exists
33/// a partition of the elements into at most `K` non-empty clusters such
34/// that for every cluster, all pairwise distances within that cluster
35/// are at most `B`.
36///
37/// # Representation
38///
39/// Each element `i` is assigned a cluster index `config[i] ∈ {0, ..., K-1}`.
40/// The problem is satisfiable iff every non-empty cluster has all pairwise
41/// distances ≤ B.
42///
43/// # Example
44///
45/// ```
46/// use problemreductions::models::misc::Clustering;
47/// use problemreductions::{Problem, BruteForce};
48///
49/// // 4 elements, 2 clusters, diameter bound 1
50/// let distances = vec![
51///     vec![0, 1, 3, 3],
52///     vec![1, 0, 3, 3],
53///     vec![3, 3, 0, 1],
54///     vec![3, 3, 1, 0],
55/// ];
56/// let problem = Clustering::new(distances, 2, 1);
57/// let solver = BruteForce::new();
58/// let solution = solver.solve(&problem).unwrap();
59/// assert!(solution.is_some());
60/// ```
61#[derive(Debug, Clone, Serialize, Deserialize)]
62#[serde(try_from = "ClusteringData")]
63pub struct Clustering {
64    /// Symmetric distance matrix with zero diagonal.
65    distances: Vec<Vec<i64>>,
66    /// Maximum number of clusters K.
67    num_clusters: usize,
68    /// Maximum allowed intra-cluster pairwise distance B.
69    diameter_bound: i64,
70}
71
72#[derive(Deserialize)]
73struct ClusteringData {
74    distances: Vec<Vec<i64>>,
75    num_clusters: usize,
76    diameter_bound: i64,
77}
78
79impl TryFrom<ClusteringData> for Clustering {
80    type Error = crate::registry::ConstructionError;
81
82    fn try_from(data: ClusteringData) -> Result<Self, Self::Error> {
83        Self::try_new(data.distances, data.num_clusters, data.diameter_bound)
84    }
85}
86
87impl Clustering {
88    /// Create a new Clustering instance.
89    ///
90    /// # Panics
91    ///
92    /// Panics if:
93    /// - `distances` is empty
94    /// - `distances` is not square
95    /// - `distances` is not symmetric
96    /// - diagonal entries are not zero
97    /// - `num_clusters` is zero
98    pub fn new(distances: Vec<Vec<i64>>, num_clusters: usize, diameter_bound: i64) -> Self {
99        Self::try_new(distances, num_clusters, diameter_bound)
100            .unwrap_or_else(|error| panic!("{error}"))
101    }
102
103    fn try_new(
104        distances: Vec<Vec<i64>>,
105        num_clusters: usize,
106        diameter_bound: i64,
107    ) -> Result<Self, crate::registry::ConstructionError> {
108        let n = distances.len();
109        if n == 0 {
110            return Err("Clustering requires at least one element".into());
111        }
112        if num_clusters == 0 {
113            return Err("num_clusters must be at least 1".into());
114        }
115        for (i, row) in distances.iter().enumerate() {
116            if row.len() != n {
117                return Err(format!(
118                    "Distance matrix must be square: row {i} has {} columns, expected {n}",
119                    row.len()
120                )
121                .into());
122            }
123            if distances[i][i] != 0 {
124                return Err(format!("Diagonal entry distances[{i}][{i}] must be 0").into());
125            }
126        }
127        for (i, row_i) in distances.iter().enumerate() {
128            for j in (i + 1)..n {
129                if row_i[j] != distances[j][i] {
130                    return Err(format!("Distance matrix must be symmetric: distances[{i}][{j}] = {} != distances[{j}][{i}] = {}", row_i[j], distances[j][i]).into());
131                }
132            }
133        }
134        Ok(Self {
135            distances,
136            num_clusters,
137            diameter_bound,
138        })
139    }
140
141    /// Returns the distance matrix.
142    pub fn distances(&self) -> &[Vec<i64>] {
143        &self.distances
144    }
145
146    /// Returns the number of elements.
147    pub fn num_elements(&self) -> usize {
148        self.distances.len()
149    }
150
151    /// Returns the maximum number of clusters K.
152    pub fn num_clusters(&self) -> usize {
153        self.num_clusters
154    }
155
156    /// Returns the diameter bound B.
157    pub fn diameter_bound(&self) -> i64 {
158        self.diameter_bound
159    }
160
161    /// Check if a configuration is a valid clustering.
162    fn is_valid_partition(&self, config: &[usize]) -> bool {
163        let n = self.num_elements();
164        if config.len() != n {
165            return false;
166        }
167        if config.iter().any(|&c| c >= self.num_clusters) {
168            return false;
169        }
170        // Group elements by cluster in a single pass
171        let mut clusters: Vec<Vec<usize>> = vec![vec![]; self.num_clusters];
172        for (i, &c) in config.iter().enumerate() {
173            clusters[c].push(i);
174        }
175        // Check all intra-cluster pairwise distances ≤ B
176        for members in &clusters {
177            for a in 0..members.len() {
178                for b in (a + 1)..members.len() {
179                    if self.distances[members[a]][members[b]] > self.diameter_bound {
180                        return false;
181                    }
182                }
183            }
184        }
185        true
186    }
187}
188
189impl Problem for Clustering {
190    const NAME: &'static str = "Clustering";
191    type Solution = Vec<usize>;
192    type Value = crate::types::Or;
193
194    crate::problem_parameters![
195        ("num_clusters", num_clusters),
196        ("num_elements", num_elements),
197    ];
198
199    fn variant() -> Vec<(&'static str, &'static str)> {
200        crate::variant_params![]
201    }
202
203    fn evaluate(
204        &self,
205        config: &Self::Solution,
206    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
207        if config.len() != self.num_elements() {
208            return Err(crate::traits::EvaluationError::InvalidConfiguration(
209                "cluster assignment length does not match the elements".into(),
210            ));
211        }
212        if config.iter().any(|&cluster| cluster >= self.num_clusters) {
213            return Err(crate::traits::EvaluationError::InvalidConfiguration(
214                "cluster assignment contains an out-of-range cluster".into(),
215            ));
216        }
217        Ok(crate::types::Or(self.is_valid_partition(config)))
218    }
219}
220
221impl crate::solvers::BruteForceProblem for Clustering {
222    fn dimensions(&self) -> Vec<usize> {
223        vec![self.num_clusters; self.num_elements()]
224    }
225}
226
227crate::declare_variants! {
228    default Clustering => "num_clusters^num_elements",
229}
230
231crate::register_brute_force! {
232    Clustering,
233}
234
235#[cfg(feature = "example-db")]
236pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
237    // 6 elements in two tight groups {0,1,2} and {3,4,5}
238    // Intra-group distance = 1, inter-group distance = 3
239    // K=2, B=1
240    let distances = vec![
241        vec![0, 1, 1, 3, 3, 3],
242        vec![1, 0, 1, 3, 3, 3],
243        vec![1, 1, 0, 3, 3, 3],
244        vec![3, 3, 3, 0, 1, 1],
245        vec![3, 3, 3, 1, 0, 1],
246        vec![3, 3, 3, 1, 1, 0],
247    ];
248    vec![crate::example_db::specs::ModelExampleSpec {
249        id: "clustering",
250        instance: Box::new(Clustering::new(distances, 2, 1)),
251        optimal_config: serde_json::json!(vec![0, 0, 0, 1, 1, 1]),
252        optimal_value: serde_json::json!(true),
253    }]
254}
255
256#[cfg(test)]
257#[path = "../../unit_tests/models/misc/clustering.rs"]
258mod tests;
problemreductions/models/misc/clustering.rs

problemreductions/models/misc/
clustering.rs
