problemreductions/models/graph/
degree_constrained_spanning_tree.rs

1//! Degree-Constrained Spanning Tree problem implementation.
2//!
3//! Given a graph G = (V, E) and a positive integer K, determine whether G has
4//! a spanning tree in which every vertex has degree at most K.
5
6use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
7use crate::topology::{Graph, SimpleGraph};
8use crate::traits::Problem;
9use crate::variant::VariantParam;
10use serde::{Deserialize, Serialize};
11use std::collections::VecDeque;
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "DegreeConstrainedSpanningTree",
16        display_name: "Degree-Constrained Spanning Tree",
17        aliases: &[],
18        dimensions: &[
19            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
20        ],
21        category: crate::registry::ProblemCategory::Graph,
22        module_path: module_path!(),
23        description: "Does G have a spanning tree with maximum vertex degree at most K?",
24        fields: &[
25            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
26            FieldInfo { name: "max_degree", type_name: "usize", description: "max_degree: maximum allowed vertex degree K (>= 1)" },
27        ],
28    }
29}
30
31/// Degree-Constrained Spanning Tree problem.
32///
33/// Given an undirected graph G = (V, E) and a positive integer K, determine
34/// whether G contains a spanning tree T such that every vertex in T has degree
35/// at most K.
36///
37/// Each configuration entry corresponds to an edge (in the order returned by
38/// `graph.edges()`), with value 0 (not selected) or 1 (selected).
39///
40/// # Type Parameters
41///
42/// * `G` - Graph type (e.g., SimpleGraph)
43///
44/// # Example
45///
46/// ```
47/// use problemreductions::models::graph::DegreeConstrainedSpanningTree;
48/// use problemreductions::topology::SimpleGraph;
49/// use problemreductions::{Problem, BruteForce};
50///
51/// let graph = SimpleGraph::new(4, vec![(0,1),(1,2),(2,3),(0,3)]);
52/// let problem = DegreeConstrainedSpanningTree::new(graph, 2);
53///
54/// let solver = BruteForce::new();
55/// let solution = solver.solve(&problem).unwrap();
56/// assert!(solution.is_some());
57/// ```
58#[derive(Debug, Clone, Serialize, Deserialize)]
59#[serde(try_from = "DegreeConstrainedSpanningTreeData<G>")]
60#[serde(bound(deserialize = "G: Graph + Deserialize<'de>"))]
61pub struct DegreeConstrainedSpanningTree<G> {
62    /// The underlying graph.
63    graph: G,
64    /// Maximum allowed vertex degree in the spanning tree.
65    max_degree: usize,
66    /// Ordered edge list (mirrors `graph.edges()` order).
67    edge_list: Vec<(usize, usize)>,
68}
69
70#[derive(Deserialize)]
71#[serde(bound(deserialize = "G: Graph + Deserialize<'de>"))]
72struct DegreeConstrainedSpanningTreeData<G> {
73    graph: G,
74    max_degree: usize,
75}
76
77impl<G> TryFrom<DegreeConstrainedSpanningTreeData<G>> for DegreeConstrainedSpanningTree<G>
78where
79    G: Graph,
80{
81    type Error = crate::registry::ConstructionError;
82
83    fn try_from(data: DegreeConstrainedSpanningTreeData<G>) -> Result<Self, Self::Error> {
84        Self::try_new(data.graph, data.max_degree)
85    }
86}
87
88impl<G: Graph> DegreeConstrainedSpanningTree<G> {
89    /// Create a new Degree-Constrained Spanning Tree instance.
90    ///
91    /// # Panics
92    /// Panics if `max_degree` is zero.
93    pub fn new(graph: G, max_degree: usize) -> Self {
94        Self::try_new(graph, max_degree).unwrap_or_else(|error| panic!("{error}"))
95    }
96
97    fn try_new(graph: G, max_degree: usize) -> Result<Self, crate::registry::ConstructionError> {
98        if max_degree == 0 {
99            return Err("max_degree must be at least 1".into());
100        }
101        let edge_list = graph.edges();
102        Ok(Self {
103            graph,
104            max_degree,
105            edge_list,
106        })
107    }
108
109    /// Get a reference to the underlying graph.
110    pub fn graph(&self) -> &G {
111        &self.graph
112    }
113
114    /// Get the max_degree parameter K.
115    pub fn max_degree(&self) -> usize {
116        self.max_degree
117    }
118
119    /// Get the number of vertices in the underlying graph.
120    pub fn num_vertices(&self) -> usize {
121        self.graph.num_vertices()
122    }
123
124    /// Get the number of edges in the underlying graph.
125    pub fn num_edges(&self) -> usize {
126        self.graph.num_edges()
127    }
128
129    /// Get the ordered edge list.
130    pub fn edge_list(&self) -> &[(usize, usize)] {
131        &self.edge_list
132    }
133}
134
135impl<G> Problem for DegreeConstrainedSpanningTree<G>
136where
137    G: Graph + VariantParam,
138{
139    const NAME: &'static str = "DegreeConstrainedSpanningTree";
140    type Solution = Vec<bool>;
141    type Value = crate::types::Or;
142
143    crate::problem_parameters![("num_edges", num_edges), ("num_vertices", num_vertices),];
144
145    fn variant() -> Vec<(&'static str, &'static str)> {
146        crate::variant_params![G]
147    }
148
149    fn evaluate(
150        &self,
151        config: &Self::Solution,
152    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
153        Ok({
154            crate::types::Or({
155                let n = self.graph.num_vertices();
156                if config.len() != self.edge_list.len() {
157                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
158                        "edge-selection length does not match the graph".into(),
159                    ));
160                }
161
162                // Collect selected edges
163                let selected: Vec<(usize, usize)> = config
164                    .iter()
165                    .enumerate()
166                    .filter(|(_, &v)| v)
167                    .map(|(i, _)| self.edge_list[i])
168                    .collect();
169
170                // A spanning tree on n vertices must have exactly n-1 edges
171                if n == 0 {
172                    return Ok(crate::types::Or(selected.is_empty()));
173                }
174                if selected.len() != n - 1 {
175                    return Ok(crate::types::Or(false));
176                }
177
178                // Check connectivity using BFS on selected edges
179                let mut adj: Vec<Vec<usize>> = vec![Vec::new(); n];
180                let mut degree = vec![0usize; n];
181                for &(u, v) in &selected {
182                    adj[u].push(v);
183                    adj[v].push(u);
184                    degree[u] += 1;
185                    degree[v] += 1;
186                }
187
188                // Check max degree constraint
189                if degree.iter().any(|&d| d > self.max_degree) {
190                    return Ok(crate::types::Or(false));
191                }
192
193                // BFS to check connectivity
194                let mut visited = vec![false; n];
195                let mut queue = VecDeque::new();
196                visited[0] = true;
197                queue.push_back(0);
198                let mut count = 1;
199                while let Some(v) = queue.pop_front() {
200                    for &u in &adj[v] {
201                        if !visited[u] {
202                            visited[u] = true;
203                            count += 1;
204                            queue.push_back(u);
205                        }
206                    }
207                }
208
209                count == n
210            })
211        })
212    }
213}
214
215impl<G> crate::solvers::BruteForceProblem for DegreeConstrainedSpanningTree<G>
216where
217    G: Graph + VariantParam,
218{
219    fn dimensions(&self) -> Vec<usize> {
220        vec![2; self.edge_list.len()]
221    }
222}
223
224crate::declare_variants! {
225    default DegreeConstrainedSpanningTree<SimpleGraph> => "2^num_vertices",
226}
227
228crate::register_brute_force! {
229    DegreeConstrainedSpanningTree<SimpleGraph> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
230}
231
232#[cfg(feature = "example-db")]
233pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
234    // 5 vertices, 7 edges: (0,1),(0,2),(0,3),(1,2),(1,4),(2,3),(3,4), K=2
235    // Spanning tree with max degree 2: edges (0,2),(0,3),(1,2),(1,4)
236    //   indices: 1,2,3,4 → config [0,1,1,1,1,0,0]
237    //   Degrees: 0→{2,3}=2, 1→{2,4}=2, 2→{0,1}=2, 3→{0}=1, 4→{1}=1
238    vec![crate::example_db::specs::ModelExampleSpec {
239        id: "degree_constrained_spanning_tree_simplegraph",
240        instance: Box::new(DegreeConstrainedSpanningTree::new(
241            SimpleGraph::new(
242                5,
243                vec![(0, 1), (0, 2), (0, 3), (1, 2), (1, 4), (2, 3), (3, 4)],
244            ),
245            2,
246        )),
247        optimal_config: serde_json::json!(vec![false, true, true, true, true, false, false]),
248        optimal_value: serde_json::json!(true),
249    }]
250}
251
252#[cfg(test)]
253#[path = "../../unit_tests/models/graph/degree_constrained_spanning_tree.rs"]
254mod tests;
problemreductions/models/graph/degree_constrained_spanning_tree.rs

problemreductions/models/graph/
degree_constrained_spanning_tree.rs
