problemreductions/models/graph/
minimum_capacitated_spanning_tree.rs

1//! Minimum Capacitated Spanning Tree problem implementation.
2//!
3//! Given a weighted graph with a designated root vertex, vertex requirements,
4//! and a capacity bound, find a minimum-weight spanning tree rooted at the root
5//! such that for each edge, the sum of requirements in its subtree (on the
6//! non-root side) does not exceed the capacity.
7
8use num_traits::Zero;
9use serde::{Deserialize, Serialize};
10
11use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
12use crate::topology::{Graph, SimpleGraph};
13use crate::traits::Problem;
14use crate::types::{Min, WeightElement};
15
16inventory::submit! {
17    ProblemSchemaEntry {
18        name: "MinimumCapacitatedSpanningTree",
19        display_name: "Minimum Capacitated Spanning Tree",
20        aliases: &["MCST"],
21        dimensions: &[
22            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
23            VariantDimension::new("weight", "i32", &["i32"]),
24        ],
25        module_path: module_path!(),
26        description: "Find minimum weight spanning tree with subtree capacity constraints",
27        fields: &[
28            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
29            FieldInfo { name: "weights", type_name: "Vec<W>", description: "Edge weights w: E -> R" },
30            FieldInfo { name: "root", type_name: "usize", description: "Root vertex" },
31            FieldInfo { name: "requirements", type_name: "Vec<W>", description: "Vertex requirements r: V -> R (root has 0)" },
32            FieldInfo { name: "capacity", type_name: "W::Sum", description: "Subtree capacity bound" },
33        ],
34    }
35}
36
37/// The Minimum Capacitated Spanning Tree problem.
38///
39/// Given a weighted graph G = (V, E), edge weights w_e, a root vertex v0,
40/// vertex requirements r_v (with r_{v0} = 0), and a capacity C, find a
41/// spanning tree T rooted at v0 such that:
42/// - For each edge e in T, the sum of requirements of all vertices in the
43///   subtree on the non-root side of e is at most C.
44/// - The total weight of T is minimized.
45///
46/// # Representation
47///
48/// Each edge is assigned a binary variable:
49/// - 0: edge is not in the spanning tree
50/// - 1: edge is in the spanning tree
51///
52/// # Type Parameters
53///
54/// * `G` - The graph type (e.g., `SimpleGraph`)
55/// * `W` - The weight type for edges and requirements (e.g., `i32`)
56#[derive(Debug, Clone, Serialize, Deserialize)]
57pub struct MinimumCapacitatedSpanningTree<G, W: WeightElement> {
58    /// The underlying graph.
59    graph: G,
60    /// Weights for each edge (in edge index order).
61    weights: Vec<W>,
62    /// Root vertex index.
63    root: usize,
64    /// Vertex requirements (root has requirement 0).
65    requirements: Vec<W>,
66    /// Subtree capacity bound.
67    capacity: W::Sum,
68}
69
70impl<G: Graph, W: WeightElement> MinimumCapacitatedSpanningTree<G, W> {
71    /// Create a MinimumCapacitatedSpanningTree problem.
72    ///
73    /// # Panics
74    /// - If `weights.len() != graph.num_edges()`
75    /// - If `requirements.len() != graph.num_vertices()`
76    /// - If `root >= graph.num_vertices()`
77    /// - If `graph.num_vertices() < 2`
78    pub fn new(
79        graph: G,
80        weights: Vec<W>,
81        root: usize,
82        requirements: Vec<W>,
83        capacity: W::Sum,
84    ) -> Self {
85        assert_eq!(
86            weights.len(),
87            graph.num_edges(),
88            "weights length must match num_edges"
89        );
90        assert_eq!(
91            requirements.len(),
92            graph.num_vertices(),
93            "requirements length must match num_vertices"
94        );
95        assert!(
96            root < graph.num_vertices(),
97            "root {root} out of range (num_vertices = {})",
98            graph.num_vertices()
99        );
100        assert!(
101            graph.num_vertices() >= 2,
102            "graph must have at least 2 vertices"
103        );
104        Self {
105            graph,
106            weights,
107            root,
108            requirements,
109            capacity,
110        }
111    }
112
113    /// Get a reference to the underlying graph.
114    pub fn graph(&self) -> &G {
115        &self.graph
116    }
117
118    /// Get the edge weights.
119    pub fn weights(&self) -> &[W] {
120        &self.weights
121    }
122
123    /// Set new edge weights.
124    pub fn set_weights(&mut self, weights: Vec<W>) {
125        assert_eq!(weights.len(), self.graph.num_edges());
126        self.weights = weights;
127    }
128
129    /// Check if the problem uses a non-unit weight type.
130    pub fn is_weighted(&self) -> bool {
131        !W::IS_UNIT
132    }
133
134    /// Get the root vertex.
135    pub fn root(&self) -> usize {
136        self.root
137    }
138
139    /// Get the vertex requirements.
140    pub fn requirements(&self) -> &[W] {
141        &self.requirements
142    }
143
144    /// Get the capacity bound.
145    pub fn capacity(&self) -> &W::Sum {
146        &self.capacity
147    }
148
149    /// Get the number of vertices in the underlying graph.
150    pub fn num_vertices(&self) -> usize {
151        self.graph.num_vertices()
152    }
153
154    /// Get the number of edges in the underlying graph.
155    pub fn num_edges(&self) -> usize {
156        self.graph.num_edges()
157    }
158
159    /// Check if a configuration is a valid capacitated spanning tree.
160    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
161        is_valid_capacitated_spanning_tree(
162            &self.graph,
163            &self.requirements,
164            self.root,
165            &self.capacity,
166            config,
167        )
168    }
169}
170
171/// Check if a configuration forms a valid spanning tree:
172/// 1. Exactly n-1 edges selected
173/// 2. Selected edges form a connected subgraph
174fn is_spanning_tree<G: Graph>(graph: &G, config: &[usize]) -> bool {
175    let n = graph.num_vertices();
176    let edges = graph.edges();
177    if config.len() != edges.len() {
178        return false;
179    }
180
181    let selected_count: usize = config.iter().sum();
182    if selected_count != n - 1 {
183        return false;
184    }
185
186    // Build adjacency and BFS from vertex 0
187    let mut adj: Vec<Vec<usize>> = vec![vec![]; n];
188    for (idx, &sel) in config.iter().enumerate() {
189        if sel == 1 {
190            let (u, v) = edges[idx];
191            adj[u].push(v);
192            adj[v].push(u);
193        }
194    }
195
196    let mut visited = vec![false; n];
197    let mut queue = std::collections::VecDeque::new();
198    visited[0] = true;
199    queue.push_back(0);
200    while let Some(v) = queue.pop_front() {
201        for &u in &adj[v] {
202            if !visited[u] {
203                visited[u] = true;
204                queue.push_back(u);
205            }
206        }
207    }
208
209    visited.iter().all(|&v| v)
210}
211
212/// Compute the subtree requirement sum for each edge in the tree rooted at `root`.
213/// Returns None if the tree is invalid, otherwise returns the max subtree sum.
214fn check_capacity<G: Graph, W: WeightElement>(
215    graph: &G,
216    requirements: &[W],
217    root: usize,
218    capacity: &W::Sum,
219    config: &[usize],
220) -> bool {
221    let n = graph.num_vertices();
222    let edges = graph.edges();
223
224    // Build adjacency list with edge indices
225    let mut adj: Vec<Vec<(usize, usize)>> = vec![vec![]; n]; // (neighbor, edge_idx)
226    for (idx, &sel) in config.iter().enumerate() {
227        if sel == 1 {
228            let (u, v) = edges[idx];
229            adj[u].push((v, idx));
230            adj[v].push((u, idx));
231        }
232    }
233
234    // Root the tree using BFS from root
235    let mut parent = vec![usize::MAX; n];
236    let mut order = Vec::with_capacity(n);
237    let mut visited = vec![false; n];
238    let mut queue = std::collections::VecDeque::new();
239    visited[root] = true;
240    parent[root] = root;
241    queue.push_back(root);
242    while let Some(v) = queue.pop_front() {
243        order.push(v);
244        for &(u, _) in &adj[v] {
245            if !visited[u] {
246                visited[u] = true;
247                parent[u] = v;
248                queue.push_back(u);
249            }
250        }
251    }
252
253    // Compute subtree sums bottom-up
254    let mut subtree_sum: Vec<W::Sum> = requirements.iter().map(|r| r.to_sum()).collect();
255    for &v in order.iter().rev() {
256        if v != root {
257            let p = parent[v];
258            let sv = subtree_sum[v].clone();
259            subtree_sum[p] += sv;
260        }
261    }
262
263    // Check capacity for each non-root vertex (its subtree sum is the flow on its parent edge)
264    for (v, sum) in subtree_sum.iter().enumerate() {
265        if v != root && *sum > *capacity {
266            return false;
267        }
268    }
269
270    true
271}
272
273/// Check if a configuration forms a valid capacitated spanning tree.
274fn is_valid_capacitated_spanning_tree<G: Graph, W: WeightElement>(
275    graph: &G,
276    requirements: &[W],
277    root: usize,
278    capacity: &W::Sum,
279    config: &[usize],
280) -> bool {
281    if !is_spanning_tree(graph, config) {
282        return false;
283    }
284    check_capacity(graph, requirements, root, capacity, config)
285}
286
287impl<G, W> Problem for MinimumCapacitatedSpanningTree<G, W>
288where
289    G: Graph + crate::variant::VariantParam,
290    W: WeightElement + crate::variant::VariantParam,
291{
292    const NAME: &'static str = "MinimumCapacitatedSpanningTree";
293    type Value = Min<W::Sum>;
294
295    fn variant() -> Vec<(&'static str, &'static str)> {
296        crate::variant_params![G, W]
297    }
298
299    fn dims(&self) -> Vec<usize> {
300        vec![2; self.graph.num_edges()]
301    }
302
303    fn evaluate(&self, config: &[usize]) -> Min<W::Sum> {
304        if !is_valid_capacitated_spanning_tree(
305            &self.graph,
306            &self.requirements,
307            self.root,
308            &self.capacity,
309            config,
310        ) {
311            return Min(None);
312        }
313        let mut total = W::Sum::zero();
314        for (idx, &selected) in config.iter().enumerate() {
315            if selected == 1 {
316                if let Some(w) = self.weights.get(idx) {
317                    total += w.to_sum();
318                }
319            }
320        }
321        Min(Some(total))
322    }
323}
324
325crate::declare_variants! {
326    default MinimumCapacitatedSpanningTree<SimpleGraph, i32> => "2^num_edges",
327}
328
329#[cfg(feature = "example-db")]
330pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
331    vec![crate::example_db::specs::ModelExampleSpec {
332        id: "minimum_capacitated_spanning_tree_simplegraph_i32",
333        instance: Box::new(MinimumCapacitatedSpanningTree::new(
334            SimpleGraph::new(
335                5,
336                vec![
337                    (0, 1),
338                    (0, 2),
339                    (0, 3),
340                    (1, 2),
341                    (1, 4),
342                    (2, 3),
343                    (2, 4),
344                    (3, 4),
345                ],
346            ),
347            vec![2, 1, 4, 3, 1, 2, 3, 1], // edge weights
348            0,                            // root
349            vec![0, 1, 1, 1, 1],          // requirements (root=0)
350            3,                            // capacity
351        )),
352        // Optimal: edges {(0,1),(0,2),(1,4),(3,4)} = indices {0,1,4,7}
353        // Weight = 2+1+1+1 = 5
354        // Subtree sums: subtree(1)={1,4}->req=2<=3, subtree(2)={2}->req=1<=3,
355        //   subtree(4)={4}->req=1<=3, subtree(3)={3}->req=1<=3
356        optimal_config: vec![1, 1, 0, 0, 1, 0, 0, 1],
357        optimal_value: serde_json::json!(5),
358    }]
359}
360
361#[cfg(test)]
362#[path = "../../unit_tests/models/graph/minimum_capacitated_spanning_tree.rs"]
363mod tests;
problemreductions/models/graph/minimum_capacitated_spanning_tree.rs

problemreductions/models/graph/
minimum_capacitated_spanning_tree.rs
