problemreductions/models/misc/
optimum_communication_spanning_tree.rs

1//! Optimum Communication Spanning Tree problem implementation.
2//!
3//! Given a complete graph K_n with edge weights w(e) and communication
4//! requirements r(u,v) for each vertex pair, find a spanning tree T that
5//! minimizes the total communication cost: sum_{u<v} r(u,v) * W_T(u,v),
6//! where W_T(u,v) is the sum of edge weights on the unique path from u to v in T.
7
8use crate::registry::{CreateSpec, ProblemSchemaEntry};
9use crate::traits::Problem;
10use crate::types::Min;
11use serde::{Deserialize, Serialize};
12use std::collections::VecDeque;
13
14inventory::submit! {
15    ProblemSchemaEntry {
16        name: "OptimumCommunicationSpanningTree",
17        display_name: "Optimum Communication Spanning Tree",
18        aliases: &["OCST"],
19        dimensions: &[],
20        category: crate::registry::ProblemCategory::Misc,
21        module_path: module_path!(),
22        description: "Find spanning tree minimizing total weighted communication cost",
23        fields: OptimumCommunicationSpanningTreeCreateSpec::FIELDS,
24    }
25}
26
27/// The Optimum Communication Spanning Tree problem.
28///
29/// Given a complete graph K_n with edge weights w(e) >= 0 and communication
30/// requirements r(u,v) >= 0 for each vertex pair, find a spanning tree T
31/// minimizing the total communication cost:
32///
33///   sum_{u < v} r(u,v) * W_T(u,v)
34///
35/// where W_T(u,v) is the weight of the unique path between u and v in T.
36///
37/// # Representation
38///
39/// Each edge of K_n is assigned a binary variable (0 = not in tree, 1 = in tree).
40/// Edges are ordered lexicographically: (0,1), (0,2), ..., (0,n-1), (1,2), ..., (n-2,n-1).
41/// A valid spanning tree has exactly n-1 selected edges forming a connected subgraph.
42///
43/// # Example
44///
45/// ```
46/// use problemreductions::models::misc::OptimumCommunicationSpanningTree;
47/// use problemreductions::{Problem, BruteForce};
48///
49/// let problem = OptimumCommunicationSpanningTree::new(
50///     vec![
51///         vec![0, 1, 2],
52///         vec![1, 0, 3],
53///         vec![2, 3, 0],
54///     ],
55///     vec![
56///         vec![0, 1, 1],
57///         vec![1, 0, 1],
58///         vec![1, 1, 0],
59///     ],
60/// );
61/// let solver = BruteForce::new();
62/// let solution = solver.solve(&problem).unwrap();
63/// assert!(solution.is_some());
64/// ```
65#[derive(Debug, Clone, Serialize, Deserialize)]
66pub struct OptimumCommunicationSpanningTree {
67    num_vertices: usize,
68    edge_weights: Vec<Vec<i64>>,
69    requirements: Vec<Vec<i64>>,
70}
71
72#[derive(Debug, Deserialize, crate::CreateSpec)]
73struct OptimumCommunicationSpanningTreeCreateSpec {
74    /// Number of vertices.
75    num_vertices: usize,
76    /// Symmetric weight matrix; defaults to unit off-diagonal weights.
77    edge_weights: Option<Vec<Vec<i64>>>,
78    /// Symmetric communication requirement matrix.
79    requirements: Vec<Vec<i64>>,
80}
81impl TryFrom<OptimumCommunicationSpanningTreeCreateSpec> for OptimumCommunicationSpanningTree {
82    type Error = crate::registry::ConstructionError;
83    fn try_from(spec: OptimumCommunicationSpanningTreeCreateSpec) -> Result<Self, Self::Error> {
84        let n = spec.num_vertices;
85        if n < 2 {
86            return Err("must have at least two vertices".to_string().into());
87        }
88        let edge_weights = spec.edge_weights.unwrap_or_else(|| {
89            (0..n)
90                .map(|i| (0..n).map(|j| i64::from(i != j)).collect())
91                .collect()
92        });
93        for (name, matrix) in [
94            ("edge_weights", &edge_weights),
95            ("requirements", &spec.requirements),
96        ] {
97            if matrix.len() != n || matrix.iter().any(|row| row.len() != n) {
98                return Err(format!("{name} must be a {n} x {n} matrix").into());
99            }
100            for (i, row) in matrix.iter().enumerate() {
101                if row[i] != 0 {
102                    return Err(format!("{name} diagonal must be zero").into());
103                }
104                for (j, &value) in row.iter().enumerate().skip(i + 1) {
105                    if value != matrix[j][i] || value < 0 {
106                        return Err(format!("{name} must be symmetric and nonnegative").into());
107                    }
108                }
109            }
110        }
111        Ok(Self::new(edge_weights, spec.requirements))
112    }
113}
114
115impl OptimumCommunicationSpanningTree {
116    /// Create a new OptimumCommunicationSpanningTree instance.
117    ///
118    /// # Arguments
119    ///
120    /// * `edge_weights` - Symmetric n x n matrix with w(i,i) = 0 and w(i,j) >= 0.
121    /// * `requirements` - Symmetric n x n matrix with r(i,i) = 0 and r(i,j) >= 0.
122    ///
123    /// # Panics
124    ///
125    /// Panics if the matrices are not square, not the same size, have nonzero
126    /// diagonals, are not symmetric, or contain negative entries.
127    pub fn new(edge_weights: Vec<Vec<i64>>, requirements: Vec<Vec<i64>>) -> Self {
128        let n = edge_weights.len();
129        assert!(n >= 2, "must have at least 2 vertices");
130        assert_eq!(
131            requirements.len(),
132            n,
133            "requirements matrix must have same size as edge_weights"
134        );
135
136        for (i, row) in edge_weights.iter().enumerate() {
137            assert_eq!(
138                row.len(),
139                n,
140                "edge_weights must be square: row {i} has length {} but expected {n}",
141                row.len()
142            );
143            assert_eq!(
144                row[i], 0,
145                "diagonal of edge_weights must be zero: edge_weights[{i}][{i}] = {}",
146                row[i]
147            );
148        }
149
150        for (i, row) in requirements.iter().enumerate() {
151            assert_eq!(
152                row.len(),
153                n,
154                "requirements must be square: row {i} has length {} but expected {n}",
155                row.len()
156            );
157            assert_eq!(
158                row[i], 0,
159                "diagonal of requirements must be zero: requirements[{i}][{i}] = {}",
160                row[i]
161            );
162        }
163
164        // Check symmetry and non-negativity
165        for i in 0..n {
166            for j in (i + 1)..n {
167                assert_eq!(
168                    edge_weights[i][j], edge_weights[j][i],
169                    "edge_weights must be symmetric: w[{i}][{j}]={} != w[{j}][{i}]={}",
170                    edge_weights[i][j], edge_weights[j][i]
171                );
172                assert!(
173                    edge_weights[i][j] >= 0,
174                    "edge_weights must be non-negative: w[{i}][{j}]={}",
175                    edge_weights[i][j]
176                );
177                assert_eq!(
178                    requirements[i][j], requirements[j][i],
179                    "requirements must be symmetric: r[{i}][{j}]={} != r[{j}][{i}]={}",
180                    requirements[i][j], requirements[j][i]
181                );
182                assert!(
183                    requirements[i][j] >= 0,
184                    "requirements must be non-negative: r[{i}][{j}]={}",
185                    requirements[i][j]
186                );
187            }
188        }
189
190        Self {
191            num_vertices: n,
192            edge_weights,
193            requirements,
194        }
195    }
196
197    /// Returns the number of vertices.
198    pub fn num_vertices(&self) -> usize {
199        self.num_vertices
200    }
201
202    /// Returns the number of edges in the complete graph K_n.
203    pub fn num_edges(&self) -> usize {
204        self.num_vertices * (self.num_vertices - 1) / 2
205    }
206
207    /// Returns the edge weight matrix.
208    pub fn edge_weights(&self) -> &Vec<Vec<i64>> {
209        &self.edge_weights
210    }
211
212    /// Returns the requirements matrix.
213    pub fn requirements(&self) -> &Vec<Vec<i64>> {
214        &self.requirements
215    }
216
217    /// Returns the list of edges in lexicographic order: (0,1), (0,2), ..., (n-2,n-1).
218    pub fn edges(&self) -> Vec<(usize, usize)> {
219        let n = self.num_vertices;
220        let mut edges = Vec::with_capacity(self.num_edges());
221        for i in 0..n {
222            for j in (i + 1)..n {
223                edges.push((i, j));
224            }
225        }
226        edges
227    }
228
229    /// Map a pair (i, j) with i < j to its edge index.
230    pub fn edge_index(i: usize, j: usize, n: usize) -> usize {
231        debug_assert!(i < j && j < n);
232        i * n - i * (i + 1) / 2 + (j - i - 1)
233    }
234}
235
236/// Check if a configuration forms a valid spanning tree of K_n.
237fn is_valid_spanning_tree(n: usize, edges: &[(usize, usize)], config: &[bool]) -> bool {
238    if config.len() != edges.len() {
239        return false;
240    }
241
242    // Count selected edges: must be exactly n-1
243    let selected_count = config.iter().filter(|&&selected| selected).count();
244    if selected_count != n - 1 {
245        return false;
246    }
247
248    // Build adjacency and check connectivity via BFS
249    let mut adj: Vec<Vec<usize>> = vec![vec![]; n];
250    for (idx, &sel) in config.iter().enumerate() {
251        if sel {
252            let (u, v) = edges[idx];
253            adj[u].push(v);
254            adj[v].push(u);
255        }
256    }
257
258    let mut visited = vec![false; n];
259    let mut queue = VecDeque::new();
260    visited[0] = true;
261    queue.push_back(0);
262    while let Some(v) = queue.pop_front() {
263        for &u in &adj[v] {
264            if !visited[u] {
265                visited[u] = true;
266                queue.push_back(u);
267            }
268        }
269    }
270
271    visited.iter().all(|&v| v)
272}
273
274/// Compute the communication cost of a spanning tree.
275///
276/// For each pair (u, v) with u < v, compute W_T(u,v) via BFS in the tree,
277/// then accumulate r(u,v) * W_T(u,v).
278fn communication_cost(
279    n: usize,
280    edges: &[(usize, usize)],
281    config: &[bool],
282    edge_weights: &[Vec<i64>],
283    requirements: &[Vec<i64>],
284) -> Result<i64, crate::traits::EvaluationError> {
285    // Build weighted adjacency list for the tree
286    let mut adj: Vec<Vec<(usize, i64)>> = vec![vec![]; n];
287    for (idx, &sel) in config.iter().enumerate() {
288        if sel {
289            let (u, v) = edges[idx];
290            let w = edge_weights[u][v];
291            adj[u].push((v, w));
292            adj[v].push((u, w));
293        }
294    }
295
296    let mut total_cost: i64 = 0;
297
298    // For each source vertex, BFS to find path weights to all other vertices
299    for src in 0..n {
300        let mut dist = vec![-1i64; n];
301        dist[src] = 0;
302        let mut queue = VecDeque::new();
303        queue.push_back(src);
304        while let Some(u) = queue.pop_front() {
305            for &(v, w) in &adj[u] {
306                if dist[v] < 0 {
307                    dist[v] = dist[u].checked_add(w).ok_or_else(|| {
308                        crate::traits::EvaluationError::IntegerOverflow(
309                            "summing communication-tree path weights".to_string(),
310                        )
311                    })?;
312                    queue.push_back(v);
313                }
314            }
315        }
316
317        // Accumulate r(src, dst) * W_T(src, dst) for dst > src
318        for (dst, &d) in dist.iter().enumerate().skip(src + 1) {
319            let term = requirements[src][dst].checked_mul(d).ok_or_else(|| {
320                crate::traits::EvaluationError::IntegerOverflow(
321                    "multiplying communication requirement by path weight".to_string(),
322                )
323            })?;
324            total_cost = total_cost.checked_add(term).ok_or_else(|| {
325                crate::traits::EvaluationError::IntegerOverflow(
326                    "summing communication-tree costs".to_string(),
327                )
328            })?;
329        }
330    }
331
332    Ok(total_cost)
333}
334
335impl Problem for OptimumCommunicationSpanningTree {
336    const NAME: &'static str = "OptimumCommunicationSpanningTree";
337    type Solution = Vec<bool>;
338    type Value = Min<i64>;
339
340    crate::problem_parameters![("num_edges", num_edges), ("num_vertices", num_vertices),];
341
342    fn variant() -> Vec<(&'static str, &'static str)> {
343        crate::variant_params![]
344    }
345
346    fn evaluate(
347        &self,
348        config: &Self::Solution,
349    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
350        if config.len() != self.edges().len() {
351            return Err(crate::traits::EvaluationError::InvalidConfiguration(
352                "edge-selection length does not match the complete graph".into(),
353            ));
354        }
355        Ok({
356            let edges = self.edges();
357            if !is_valid_spanning_tree(self.num_vertices, &edges, config) {
358                return Ok(Min(None));
359            }
360            Min(Some(communication_cost(
361                self.num_vertices,
362                &edges,
363                config,
364                &self.edge_weights,
365                &self.requirements,
366            )?))
367        })
368    }
369}
370
371impl crate::solvers::BruteForceProblem for OptimumCommunicationSpanningTree {
372    fn dimensions(&self) -> Vec<usize> {
373        vec![2; self.num_edges()]
374    }
375}
376
377crate::declare_variants! {
378    default OptimumCommunicationSpanningTree => "2^num_edges" create OptimumCommunicationSpanningTreeCreateSpec,
379}
380
381crate::register_brute_force! {
382    OptimumCommunicationSpanningTree decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
383}
384
385#[cfg(feature = "example-db")]
386pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
387    // K4 example from issue #906
388    // Edge weights:
389    //   w(0,1)=1, w(0,2)=3, w(0,3)=2, w(1,2)=2, w(1,3)=4, w(2,3)=1
390    // Requirements:
391    //   r(0,1)=2, r(0,2)=1, r(0,3)=3, r(1,2)=1, r(1,3)=1, r(2,3)=2
392    // Optimal tree: {(0,1), (0,3), (2,3)} = edges at indices 0, 2, 5
393    // Optimal cost: 20
394    let edge_weights = vec![
395        vec![0, 1, 3, 2],
396        vec![1, 0, 2, 4],
397        vec![3, 2, 0, 1],
398        vec![2, 4, 1, 0],
399    ];
400    let requirements = vec![
401        vec![0, 2, 1, 3],
402        vec![2, 0, 1, 1],
403        vec![1, 1, 0, 2],
404        vec![3, 1, 2, 0],
405    ];
406    // Edges in lex order: (0,1)=idx0, (0,2)=idx1, (0,3)=idx2, (1,2)=idx3, (1,3)=idx4, (2,3)=idx5
407    // Optimal tree: {(0,1), (0,3), (2,3)} -> config = [1, 0, 1, 0, 0, 1]
408    vec![crate::example_db::specs::ModelExampleSpec {
409        id: "optimum_communication_spanning_tree",
410        instance: Box::new(OptimumCommunicationSpanningTree::new(
411            edge_weights,
412            requirements,
413        )),
414        optimal_config: serde_json::json!(vec![true, false, true, false, false, true]),
415        optimal_value: serde_json::json!(20),
416    }]
417}
418
419#[cfg(test)]
420#[path = "../../unit_tests/models/misc/optimum_communication_spanning_tree.rs"]
421mod tests;
problemreductions/models/misc/optimum_communication_spanning_tree.rs

problemreductions/models/misc/
optimum_communication_spanning_tree.rs
