problemreductions/models/graph/
bounded_diameter_spanning_tree.rs

1//! Bounded Diameter Spanning Tree problem implementation.
2//!
3//! Given a graph G = (V, E) with edge weights, a weight bound B, and a diameter
4//! bound D, determine whether G has a spanning tree with total weight at most B
5//! and diameter (longest shortest path in edges) at most D.
6
7use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
8use crate::topology::{Graph, SimpleGraph};
9use crate::traits::Problem;
10use crate::types::WeightElement;
11use crate::variant::VariantParam;
12use num_traits::Zero;
13use serde::{Deserialize, Serialize};
14use std::collections::VecDeque;
15
16inventory::submit! {
17    ProblemSchemaEntry {
18        name: "BoundedDiameterSpanningTree",
19        display_name: "Bounded Diameter Spanning Tree",
20        aliases: &[],
21        dimensions: &[
22            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
23            VariantDimension::new("weight", "i32", &["i32"]),
24        ],
25        module_path: module_path!(),
26        description: "Does G have a spanning tree with total weight <= B and diameter <= D?",
27        fields: &[
28            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
29            FieldInfo { name: "edge_weights", type_name: "Vec<W>", description: "Edge weights w: E -> ZZ_(> 0)" },
30            FieldInfo { name: "weight_bound", type_name: "W::Sum", description: "Upper bound B on total tree weight" },
31            FieldInfo { name: "diameter_bound", type_name: "usize", description: "Upper bound D on tree diameter (in edges)" },
32        ],
33    }
34}
35
36/// Bounded Diameter Spanning Tree problem.
37///
38/// Given an undirected graph G = (V, E) with positive edge weights w(e), a
39/// weight bound B, and a diameter bound D, determine whether G contains a
40/// spanning tree T such that the total weight of T is at most B and the
41/// diameter of T (the longest shortest path measured in number of edges) is
42/// at most D.
43///
44/// Each configuration entry corresponds to an edge (in the order returned by
45/// `graph.edges()`), with value 0 (not selected) or 1 (selected).
46///
47/// # Type Parameters
48///
49/// * `G` - Graph type (e.g., SimpleGraph)
50/// * `W` - Edge weight type (e.g., i32)
51///
52/// # Example
53///
54/// ```
55/// use problemreductions::models::graph::BoundedDiameterSpanningTree;
56/// use problemreductions::topology::SimpleGraph;
57/// use problemreductions::{Problem, Solver, BruteForce};
58///
59/// let graph = SimpleGraph::new(5, vec![(0,1),(0,2),(0,3),(1,2),(1,4),(2,3),(3,4)]);
60/// let problem = BoundedDiameterSpanningTree::new(graph, vec![1,2,1,1,2,1,1], 5, 3);
61///
62/// let solver = BruteForce::new();
63/// let solution = solver.find_witness(&problem);
64/// assert!(solution.is_some());
65/// ```
66#[derive(Debug, Clone, Serialize, Deserialize)]
67#[serde(bound(
68    deserialize = "G: serde::Deserialize<'de>, W: serde::Deserialize<'de>, W::Sum: serde::Deserialize<'de>"
69))]
70pub struct BoundedDiameterSpanningTree<G, W: WeightElement> {
71    /// The underlying graph.
72    graph: G,
73    /// Weight for each edge in graph-edge order.
74    edge_weights: Vec<W>,
75    /// Upper bound B on total tree weight.
76    weight_bound: W::Sum,
77    /// Upper bound D on tree diameter (in edges).
78    diameter_bound: usize,
79    /// Ordered edge list (mirrors `graph.edges()` order).
80    edge_list: Vec<(usize, usize)>,
81}
82
83impl<G: Graph, W: WeightElement> BoundedDiameterSpanningTree<G, W> {
84    /// Create a new Bounded Diameter Spanning Tree instance.
85    ///
86    /// # Panics
87    /// Panics if `edge_weights` length does not match the graph's edge count,
88    /// if any edge weight is not positive, or if `diameter_bound` is zero.
89    pub fn new(
90        graph: G,
91        edge_weights: Vec<W>,
92        weight_bound: W::Sum,
93        diameter_bound: usize,
94    ) -> Self {
95        assert_eq!(
96            edge_weights.len(),
97            graph.num_edges(),
98            "edge_weights length must match num_edges"
99        );
100        let zero = W::Sum::zero();
101        assert!(
102            edge_weights.iter().all(|w| w.to_sum() > zero.clone()),
103            "All edge weights must be positive (> 0)"
104        );
105        assert!(weight_bound > zero, "weight_bound must be positive (> 0)");
106        assert!(diameter_bound >= 1, "diameter_bound must be at least 1");
107        let edge_list = graph.edges();
108        Self {
109            graph,
110            edge_weights,
111            weight_bound,
112            diameter_bound,
113            edge_list,
114        }
115    }
116
117    /// Get a reference to the underlying graph.
118    pub fn graph(&self) -> &G {
119        &self.graph
120    }
121
122    /// Get the edge weights.
123    pub fn edge_weights(&self) -> &[W] {
124        &self.edge_weights
125    }
126
127    /// Set new edge weights.
128    pub fn set_weights(&mut self, edge_weights: Vec<W>) {
129        assert_eq!(
130            edge_weights.len(),
131            self.graph.num_edges(),
132            "edge_weights length must match num_edges"
133        );
134        let zero = W::Sum::zero();
135        assert!(
136            edge_weights.iter().all(|w| w.to_sum() > zero.clone()),
137            "All edge weights must be positive (> 0)"
138        );
139        self.edge_weights = edge_weights;
140    }
141
142    /// Get the weight bound B.
143    pub fn weight_bound(&self) -> &W::Sum {
144        &self.weight_bound
145    }
146
147    /// Get the diameter bound D.
148    pub fn diameter_bound(&self) -> usize {
149        self.diameter_bound
150    }
151
152    /// Get the number of vertices in the underlying graph.
153    pub fn num_vertices(&self) -> usize {
154        self.graph.num_vertices()
155    }
156
157    /// Get the number of edges in the underlying graph.
158    pub fn num_edges(&self) -> usize {
159        self.graph.num_edges()
160    }
161
162    /// Get the ordered edge list.
163    pub fn edge_list(&self) -> &[(usize, usize)] {
164        &self.edge_list
165    }
166
167    /// Check whether this problem uses a non-unit weight type.
168    pub fn is_weighted(&self) -> bool {
169        !W::IS_UNIT
170    }
171
172    /// Compute the diameter of a tree given its adjacency list.
173    /// The diameter is the length (in number of edges) of the longest shortest
174    /// path between any two vertices in the tree.
175    fn tree_diameter(adj: &[Vec<usize>], n: usize) -> usize {
176        let mut max_dist = 0;
177        for start in 0..n {
178            if adj[start].is_empty() {
179                continue;
180            }
181            let mut dist = vec![usize::MAX; n];
182            dist[start] = 0;
183            let mut queue = VecDeque::new();
184            queue.push_back(start);
185            while let Some(v) = queue.pop_front() {
186                for &u in &adj[v] {
187                    if dist[u] == usize::MAX {
188                        dist[u] = dist[v] + 1;
189                        if dist[u] > max_dist {
190                            max_dist = dist[u];
191                        }
192                        queue.push_back(u);
193                    }
194                }
195            }
196        }
197        max_dist
198    }
199}
200
201impl<G, W> Problem for BoundedDiameterSpanningTree<G, W>
202where
203    G: Graph + VariantParam,
204    W: WeightElement + VariantParam,
205{
206    const NAME: &'static str = "BoundedDiameterSpanningTree";
207    type Value = crate::types::Or;
208
209    fn variant() -> Vec<(&'static str, &'static str)> {
210        crate::variant_params![G, W]
211    }
212
213    fn dims(&self) -> Vec<usize> {
214        vec![2; self.edge_list.len()]
215    }
216
217    fn evaluate(&self, config: &[usize]) -> crate::types::Or {
218        crate::types::Or({
219            let n = self.graph.num_vertices();
220            if config.len() != self.edge_list.len() {
221                return crate::types::Or(false);
222            }
223
224            // Collect selected edges
225            let selected_indices: Vec<usize> = config
226                .iter()
227                .enumerate()
228                .filter(|(_, &v)| v == 1)
229                .map(|(i, _)| i)
230                .collect();
231
232            // A spanning tree on n vertices must have exactly n-1 edges
233            if n == 0 {
234                return crate::types::Or(selected_indices.is_empty());
235            }
236            if selected_indices.len() != n - 1 {
237                return crate::types::Or(false);
238            }
239
240            // Build adjacency list and compute total weight
241            let mut adj: Vec<Vec<usize>> = vec![Vec::new(); n];
242            let mut total_weight = W::Sum::zero();
243            for &idx in &selected_indices {
244                let (u, v) = self.edge_list[idx];
245                adj[u].push(v);
246                adj[v].push(u);
247                total_weight += self.edge_weights[idx].to_sum();
248            }
249
250            // Check weight bound
251            if total_weight > self.weight_bound.clone() {
252                return crate::types::Or(false);
253            }
254
255            // Check connectivity using BFS
256            let mut visited = vec![false; n];
257            let mut queue = VecDeque::new();
258            visited[0] = true;
259            queue.push_back(0);
260            let mut count = 1;
261            while let Some(v) = queue.pop_front() {
262                for &u in &adj[v] {
263                    if !visited[u] {
264                        visited[u] = true;
265                        count += 1;
266                        queue.push_back(u);
267                    }
268                }
269            }
270
271            if count != n {
272                return crate::types::Or(false);
273            }
274
275            // Check diameter bound (BFS from each vertex)
276            let diameter = Self::tree_diameter(&adj, n);
277            diameter <= self.diameter_bound
278        })
279    }
280}
281
282crate::declare_variants! {
283    default BoundedDiameterSpanningTree<SimpleGraph, i32> => "num_vertices ^ num_vertices",
284}
285
286#[cfg(feature = "example-db")]
287pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
288    // 5 vertices, 7 edges with weights: (0,1,1),(0,2,2),(0,3,1),(1,2,1),(1,4,2),(2,3,1),(3,4,1)
289    // B=5, D=3
290    // Tree: edges (0,1),(0,3),(2,3),(3,4) → edge indices 0,2,5,6
291    // Config: [1,0,1,0,0,1,1] → weight = 1+1+1+1 = 4 ≤ 5, diameter = 3 ≤ 3
292    vec![crate::example_db::specs::ModelExampleSpec {
293        id: "bounded_diameter_spanning_tree_simplegraph_i32",
294        instance: Box::new(BoundedDiameterSpanningTree::new(
295            SimpleGraph::new(
296                5,
297                vec![(0, 1), (0, 2), (0, 3), (1, 2), (1, 4), (2, 3), (3, 4)],
298            ),
299            vec![1, 2, 1, 1, 2, 1, 1],
300            5,
301            3,
302        )),
303        optimal_config: vec![1, 0, 1, 0, 0, 1, 1],
304        optimal_value: serde_json::json!(true),
305    }]
306}
307
308#[cfg(test)]
309#[path = "../../unit_tests/models/graph/bounded_diameter_spanning_tree.rs"]
310mod tests;
problemreductions/models/graph/bounded_diameter_spanning_tree.rs

problemreductions/models/graph/
bounded_diameter_spanning_tree.rs
